เหตุใดการเรียงสับเปลี่ยนแบบคงที่จึงไม่เป็นแบบทางเดียว

นี่อาจไม่ใช่คำถามที่ดี แต่ฉันเพิ่งเริ่มเรียนรู้การเข้ารหัส ฉันต้องการถามว่าทำไมการแก้ไขการเรียงสับเปลี่ยนไม่ใช่วิธีเดียว

ฝ่ายตรงข้ามจะได้รับ y=f(x) และพยายามสลับ y, x และ y เป็น n บิต

ในความคิดของฉัน ฝ่ายตรงข้ามที่มีประสิทธิภาพสามารถค้นหาพหุนามเพื่อเปลี่ยนรูปได้เท่านั้น และจะประสบความสำเร็จได้ก็ต่อเมื่อสร้างแบบสอบถาม x ถึง f()

ดังนั้นความน่าจะเป็นที่ฝ่ายตรงข้ามจะประสบความสำเร็จจึงเป็นเพียง p(n)*(1/(2^n)) ซึ่งน้อยมาก มีอะไรผิดปกติกับคำพูดของฉันหรือไม่?

[แก้ไข] ให้ฉันให้รายละเอียดเพิ่มเติม นี่เป็นปัญหาของ 7.5(a) ของ Katz/Lindell ให้การสุ่มตัวอย่างการเปลี่ยนแปลง F แสดงว่า f(x,y) = $F_x (ย)$ ไม่ใช่ทางเดียว

ฉันต้องการถามว่าทำไมการแก้ไขการเรียงสับเปลี่ยนไม่ใช่วิธีเดียว

ไม่ว่าจะเป็นทางเดียวหรือไม่นั้นขึ้นอยู่กับว่าคุณกำหนดปัญหาอย่างไร

หากคุณได้รับสิทธิ์ให้ Oracle เข้าถึงการเปลี่ยนรูปแบบทางเดียว นั่นคือ คุณจะได้รับอนุญาตให้ระบุข้อความค้นหาจำนวนหนึ่ง $x$ และ Oracle ให้คุณประเมิน $F(x)$เราหวังว่า (สมมติว่าขนาดใหญ่) จะเป็นทางเดียว ท้ายที่สุดถ้าเรากำหนด $F$ เป็นการเข้ารหัสบล็อก AES โดยใช้รหัสลับ (เช่น $n = 2^{128}$) กระบวนทัศน์ของ Oracle นี้เป็นการโจมตีแบบ CPA มาตรฐานทุกประการ และเราหวังว่า AES จะปลอดภัยจากการโจมตีดังกล่าว และแน่นอนว่าสามารถพิสูจน์ได้อย่างเป็นทางการแล้วว่าความน่าจะเป็นที่จะสำเร็จสำหรับการเรียงสับเปลี่ยนแบบสุ่มนั้นใกล้เคียง (ความน่าจะเป็นในขอบเขตบนจริงนั้นสูงกว่าเล็กน้อย เนื่องจากผู้โจมตีสามารถคาดเดาข้อมูลที่เขาไม่ได้ให้กับ Oracle ทำให้โอกาสสำเร็จของเขาลดลงเล็กน้อย ).

ในทางกลับกัน หากคุณได้รับคำอธิบายของ $F$จะกลายเป็นปัญหามากขึ้น วิธีที่ง่ายที่สุด (และพบได้บ่อยที่สุด) ในการสร้างการเรียงสับเปลี่ยนที่ชัดเจนคือการใช้ชุดการเรียงสับเปลี่ยนที่อ่อนแอ (กลม) และต่อเข้าด้วยกัน นี่เป็นแนวทางที่ Keccak (SHA-3) ใช้ วิธีนี้ใช้ได้ผล แต่ง่ายต่อการกลับด้าน (เพียงคำนวณค่าผกผันของการเรียงสับเปลี่ยนที่อ่อนแอในลำดับที่ตรงกันข้าม)

ในทางกลับกัน นั่นไม่ใช่วิธีเดียวในการกำหนดการเรียงสับเปลี่ยน ตัวอย่างของวิธีอื่นคือการกำหนดการเรียงสับเปลี่ยน $F(x) = x^e \bmod n$ สำหรับโมดูลัส RSA $n$ และเลขยกกำลังสาธารณะ $e$. นี่คือการเปลี่ยนแปลงของ $x \ใน [0 ... n-1]$, และถ้า $n, e$ ถูกเลือกมาอย่างดี มันยากที่จะกลับค่าแม้จะได้รับค่า $n, e$ (หรืออย่างนั้นเราหวังว่า มิฉะนั้น RSA จะไม่ปลอดภัย)