คำถามบางข้อเกี่ยวกับการสร้างการเรียงสับเปลี่ยนจากฟังก์ชันบูลีน
ฉันเคยเห็นหลายตัวอย่างของฟังก์ชันบูลีนที่ใช้เป็นการเปลี่ยนแปลง
ตัวอย่างเช่นฟังก์ชัน Keccak Chi: 2.3.1 :
จาก https://keccak.team/figures.html
หรือเป็นสูตร: สำหรับ $i=\{0..4\}$ $A_i=a_i \oplus (\neg a_{i+1} \wedge a_{i+2})$ ด้วยดัชนีคำนวณโมดูโล 5
คำถามแรกคืออะไรคือเหตุผล (หรือข้อพิสูจน์) ว่าทำไมจึงเป็นการเปลี่ยนแปลง?
ประการที่สองที่เกี่ยวข้อง: คุณสมบัติคืออะไรฟังก์ชันบูลีนต้องตอบสนองที่ส่งผลให้เกิดการเปลี่ยนแปลง?
และตอนนี้เกี่ยวกับการผกผันของการเปลี่ยนแปลงดังกล่าว
มีวิธีการ / อัลกอริทึมทั่วไปในการค้นหาสิ่งที่ตรงกันข้ามของสิ่งก่อสร้างดังกล่าวหรือไม่?
นอกจากนี้อะไรคือปัจจัยที่ทำให้เกิดความซับซ้อนของการผกผัน (จำนวนตัวแปรระดับพีชคณิต ฯลฯ )?
และหากวิธีการดังกล่าวถูกนำไปใช้กับอินพุตที่ใหญ่ขึ้น - พูด $i=\{0..127\}$, ค่าผกผันยากกว่าในการคำนวณหรือไม่ถ้าฟังก์ชันมีเพียงไม่กี่ตัว (เช่น 3 สำหรับ Chi) หรือหลายตัวเช่น 128 ตัวแปรอินพุต?
คำตอบ / คำแนะนำใด ๆ จะได้รับการชื่นชม
คำตอบ
คำถามทั่วไปเกี่ยวกับพีชคณิตมีหลายแง่มุมและอาจค่อนข้างซับซ้อน บางส่วนขึ้นอยู่กับพื้นที่เวกเตอร์บางส่วนขึ้นอยู่กับคุณสมบัติของฟิลด์ส่วนขยาย
ดังที่ได้กล่าวไว้ในความคิดเห็นการตรวจสอบคุณสมบัติสามารถทำได้ง่ายกว่า
ฉันตอบคำถามที่เกี่ยวข้องตัวอย่างของฟังก์ชันบูลีนแบบสมดุลบิตเอาต์พุตหลายบิต
บทความของ Nyberg ที่กล่าวถึงมี
K. Nyberg การแมปที่แตกต่างกันสำหรับการเข้ารหัส , 1993 และ
K Nyberg, กล่อง S แบบไม่เชิงเส้นที่สมบูรณ์แบบ , 1992
ทั้งสองค้นหาได้อย่างง่ายดายใน google scholar
แก้ไข : keccak$\chi$ แผนที่ $\{0,1\}^5$ กับตัวเอง
ฉันจะใช้ $a_i$ เป็นอินพุตและ $A_i$ เป็นตัวแปรเอาต์พุตเช่นเดียวกับคำถามที่แก้ไข
การนับดัชนีโมดูโล 5 ถ้าไม่มี $i$ ดังนั้น $(a_i,a_{i+2})=(0,1)$ แล้ว $\chi$มีจุดคงที่สำหรับอินพุตนั้น ปล่อย$W=\{i: (a_i,a_{i+2})=(0,1)\},$ จากนั้นการทำแผนที่ทั่วไปจะสลับบิตที่เป็นของ $i.$
สังเกตว่าชุด $J_i,J_j$ ที่ไหน $J_i=\{i,i+2\}$ ไม่ปะติดปะต่อยกเว้นเมื่อ $j=i+2$ หรือ $i=j+2.$ดังนั้นจึงไม่มีความคลุมเครือในการกำหนดค่าผกผันเว้นแต่เราจะอยู่ในกรณีพิเศษนี้ดังนั้นจึงมีการผกผันยกเว้นในกรณีพิเศษนี้ แต่ถึงแม้ในกรณีนี้รูปแบบ$(a_i,a_{i+2},a_{i+4})$ ซึ่งส่งผลให้ bitflips ไม่คลุมเครือ
ถ้า $(a_i,a_{i+2},a_{i+4})=(1,0,0)$ แล้ว $a_{i+1}$ จะพลิก แต่ไม่ใช่ $a_{i+3}$. ดังนั้น$A_{i+1}=1\oplus a_{i+1},$ และ $A_{i+3}=a_{i+3}.$
ถ้า $(a_i,a_{i+2},a_{i+4})=(1,0,1)$ แล้ว $a_{i+1}$ จะพลิก แต่ไม่จำเป็น $a_{i+3}$ซึ่งจะขึ้นอยู่กับค่าของ $a_{i+6}=a_{i+1}$. แต่บิตนั้นไม่ได้รับผลกระทบจากอาร์กิวเมนต์ก่อนหน้าตั้งแต่นั้นเป็นต้นมา$J_i$ และ $J_j$ ไม่ปะติดปะต่อถ้า $i=j+1\pmod 2.$
ดังนั้นการทำแผนที่ผกผันที่ไม่ซ้ำกันจึงมีอยู่
หมายเหตุ : โดยทั่วไปการใช้ระหว่างสูตรฟิลด์ส่วนขยาย "พื้นฐานอิสระ" ของการเรียงสับเปลี่ยนกับการเรียงสับเปลี่ยนบิตเวกเตอร์ "ตามพื้นฐาน" นั้นแทบจะไม่ตรงไปตรงมา ฉันไม่เห็นการกำหนดฟิลด์ส่วนขยายที่เป็นอิสระในทันทีสำหรับการเปลี่ยนแปลงนี้และตามที่ระบุไว้ในความคิดเห็นของคำถามสูตรดังกล่าวที่ได้รับ (พูด) โดยการแก้ไข Lagrange อาจค่อนข้างซับซ้อนและมีระดับสูง
$\chi$ฟังก์ชันถูกกำหนดและวิเคราะห์ใน Joan Daemen Ph.D. วิทยานิพนธ์
- กลยุทธ์การออกแบบฟังก์ชันการเข้ารหัสและแฮชตามการเข้ารหัสเชิงเส้นและเชิงอนุพันธ์, 1995
บทที่ 6: Shift-Invariant Transformations (SIT) เป็นที่ที่กล่าวถึงทฤษฎี ฉันจะให้ข้อมูลคร่าวๆ (คำจำกัดความและผลลัพธ์มากมาย)
คุณสมบัติของ SIT ที่ทำให้เกิดประโยชน์
- ในฮาร์ดแวร์การแปลงเหล่านี้สามารถนำไปใช้เป็นอาร์เรย์ที่เชื่อมต่อกันของ "โปรเซสเซอร์" เอาต์พุต 1 บิตที่เหมือนกัน
- shift-invariance ช่วยให้มั่นใจได้ว่าภาระการคำนวณมีการกระจายอย่างเหมาะสมที่สุด
- ในซอฟต์แวร์ความสม่ำเสมอของซอฟต์แวร์ช่วยให้สามารถใช้งานได้อย่างมีประสิทธิภาพโดยใช้การดำเนินการเชิงตรรกะในระดับบิต
- ยิ่งไปกว่านั้นการแปลงไบนารีกะ - ไม่แปรเปลี่ยนสามารถระบุได้ด้วยฟังก์ชันบูลีนเดียว
SIT มีความเกี่ยวข้องอย่างมากกับออโตมาตาเซลล์ จำกัด ซึ่งมุ่งเน้นไปที่โครงสร้างและรูปแบบในระยะยาวในช่วงเวลาหนึ่งงานนี้มุ่งเน้นไปที่แง่มุมระยะสั้นของการกลับตัวไม่ได้และคุณสมบัติการแพร่กระจายและความสัมพันธ์ในท้องถิ่น
คำจำกัดความ 6.1:การเปลี่ยนแปลง$\phi: \mathcal{A} \to \mathcal{A}$เป็นกะคงที่หาก
$$\forall a \in \mathcal{A}, \forall r\in\mathbb{Z}: \phi(\tau_r(a)) = \tau(\phi(a))$$ ที่ไหน $\mathcal{A}$ เป็นสถานะที่เป็นไปได้ทั้งหมด
จากนั้นจึงกำหนดแผนที่ท้องถิ่นโดยภาพขึ้นอยู่กับอินพุตบางส่วนเท่านั้น
ทฤษฎีบท 6.1 (D. Richardson) หากมีการเปลี่ยนแปลง$\phi$ ด้วยการ จำกัด $\nu$ กลับด้านแล้วผกผัน $\phi^{−1}$ คือการเปลี่ยนแปลงที่ไม่แปรเปลี่ยนกะโดยมีข้อ จำกัด $\nu$.
ที่ไหน $\nu$กำหนดเขตให้ดู6.3 แผนที่ในท้องถิ่น ทฤษฎีบทนี้ไม่ได้จัดเตรียมการผกผันอย่างชัดเจน
ส่วนที่ 6.6 การแปลงแบบไม่เชิงเส้นที่มีข้อ จำกัด $\nu$ เป็นจุดเริ่มต้นของการดำเนินการ
ที่นี่แผนที่ท้องถิ่นระบุโดยชุดของรูปแบบที่เรียกว่าภูมิทัศน์เสริม (CL) ค่าของส่วนประกอบจะเสริมหากพื้นที่ใกล้เคียงใช้รูปแบบใดรูปแบบหนึ่งเหล่านี้ แนวนอนคือรูปแบบที่ประกอบด้วยสัญลักษณ์$1, 0$และ $\textbf{-}$ แสดงว่า "ไม่สนใจ" ซึ่งอยู่ในตำแหน่งที่สัมพันธ์กับจุดเริ่มต้นซึ่งแสดงโดย $∗$. ในบริบทนี้สถานะศูนย์ทั้งหมดจะแสดงด้วย$0^*$ และรัฐแบบครบวงจรโดย $1^*$.
ผกผันของ $\chi$มีการพูดคุยในส่วนการกลับตัวไม่ได้ในท้องถิ่นและทั่วโลกซึ่งต้องใช้ทฤษฎีที่ลึกซึ้งกว่านี้ อ่านเพื่อเรียนรู้หากคุณต้องการ
ดังที่ฉันได้กล่าวไว้ในความคิดเห็นเราสามารถค้นหาการเรียงสับเปลี่ยนที่เป็นไปได้ทั้งหมดเพื่อดูคุณสมบัติที่ต้องการหรือดูตามทฤษฎีอย่างที่ Daemen ทำ พวกเขาใช้ทฤษฎีนี้หลายปีต่อมาในการสร้างฟองน้ำที่$\chi$ เป็นส่วนเดียวที่ไม่ใช่เชิงเส้นของ SHA-3
เนื่องจากคำถามแรกของฉันได้รับคำตอบโดยละเอียดในคำตอบของ kodlu และ kelalaka ฉันจึงต้องการแบ่งปันผลลัพธ์ที่ฉันรวบรวมในคำถามที่สองของฉันตั้งแต่โพสต์:
คุณสมบัติบูลีนมีคุณสมบัติอย่างไรเพื่อตอบสนองผลลัพธ์ของการเปลี่ยนแปลง?
ในระหว่างการอ่านเพิ่มเติมมากมายฉันค้นพบว่าสิ่งนี้ดูเหมือนจะเป็นทรัพย์สินที่รู้จักกันดี (แต่ไม่แพร่หลาย) ตัวอย่างที่ระบุและพิสูจน์แล้วในVectorial Boolean Functions for Cryptographyบทที่ 2.3.1 เป็นข้อเสนอที่ 2:
ฟังก์ชัน (n, m) จะสมดุลก็ต่อเมื่อฟังก์ชันส่วนประกอบมีความสมดุลนั่นคือถ้าและเฉพาะในกรณีที่สำหรับทุก v ที่ไม่ใช่ศูนย์∈ $F^2_m$ฟังก์ชันบูลีน v · F มีความสมดุล
ด้วยข้อเท็จจริงเพิ่มเติมจากบทที่ 2.3:
ฟังก์ชัน balanced (n, n) คือการเรียงสับเปลี่ยนบน $F^2_n$
ดังนั้นฟังก์ชัน an (n, n) คือการเปลี่ยนแปลงถ้ามีความสมดุลตามคำจำกัดความข้างต้นเท่านั้น
กล่าวอีกนัยหนึ่งฟังก์ชันส่วนประกอบทุกอย่างจะต้องมีความสมดุลเช่นเดียวกับการผสมผสานฟังก์ชันส่วนประกอบที่เป็นไปได้รวมถึง ฟังก์ชั่นทั้งหมดในครั้งเดียวจะต้องมีความสมดุล
อย่างไรก็ตามคุณสมบัตินี้ยังระบุไว้อย่างชัดเจนน้อยกว่าในCipher and Hash Function Design Strategies ตามการเข้ารหัสเชิงเส้นและเชิงอนุพันธ์ 1995 Theorem 5.1
นอกจากนี้ยังหมายความว่าการตรวจสอบคุณสมบัตินี้สำหรับกรณีทั่วไปสำหรับฟังก์ชันที่ใหญ่กว่าเช่นความกว้าง 64 บิต (n = 64) เป็นไปไม่ได้เนื่องจากจะต้องมีการตรวจสอบความสมดุลสำหรับชุดค่าผสมที่แตกต่างกัน 2 ^ 64 - 1 ชุด (สำหรับ 2 ^ 64 อินพุตที่เป็นไปได้แต่ละรายการ) . ดังนั้นจึงจำเป็นต้องใช้เทคนิคหรือทางลัดบางอย่าง