Even-Mansour Cipher: อัลกอริธึมที่มีประสิทธิภาพสำหรับการสุ่มตัวอย่างการเรียงสับเปลี่ยน

Even-Mansour เป็นแบบจำลองเชิงทฤษฎีเพื่อพิสูจน์ผลลัพธ์ด้านความปลอดภัย เราจะต้องสุ่มตัวอย่างการเรียงสับเปลี่ยนของ $n$ บิตพูดสำหรับ $n=128,$ เนื่องจากพื้นที่ผลลัพธ์ของ $N=2^n$ วัตถุจะมีขนาดใหญ่เกินไปที่จะเก็บหรือจัดการ สิ่งนี้คล้ายกับความจริงที่ว่าไม่มีใครใช้การแจกแจงแบบสุ่มอย่างหมดจดและ i.i.d. ลำดับของบิตเป็นคีย์สตรีมในโหมด OTP ในการเข้ารหัสสมัยใหม่ มันช้าเกินไป

อย่างไรก็ตาม อัลกอริทึมต่อไปนี้ให้การเปลี่ยนลำดับแบบสุ่ม $\{1,2,\ldots, N\}.$ ไม่มีการเรียกร้องประสิทธิภาพที่เหมาะสมที่สุดที่นี่

รหัสสำหรับการเรียงสับเปลี่ยนแบบสุ่มของรายการขนาดเล็ก

ป้อนข้อมูล: รายการ $A=[1,2,\ldots, N]$ ของ $N=2^n$ รายการ

งาน: เปลี่ยนค่าเป็น $A$ สุ่ม.

อนุญาต $S:=\{u: u \in A\}.$ อนุญาต $B:=A$

แต่ละ $i=1,\ldots,N$ ทำ

$\สี่เหลี่ยม$ เลือกจำนวนเต็มแบบสุ่ม $j \ใน S$

$\สี่เหลี่ยม$ เปลี่ยนอาร์เรย์ $B$ ทาง $B[j]:=A[i]$

$\สี่เหลี่ยม$ ลบ $เจ$ จากชุด $S$

จบสำหรับ อัลกอริทึมนี้เลือก $N,$ แล้ว $N-1$, แล้ว $N-2$ ฯลฯ วัตถุที่เหมือนกันและสามารถสร้างการเรียงสับเปลี่ยนแต่ละครั้งด้วยความน่าจะเป็นที่เท่ากัน เนื่องจากมันสร้าง $N\!$ ทางเลือก เอาท์พุต: รายการ $A$ ตอนนี้เป็นแบบสุ่ม

มีวิธีที่มีประสิทธิภาพมากขึ้นในการสุ่มตัวอย่างการเรียงสับเปลี่ยนแบบสุ่ม ดูตัวอย่าง Jens Gustedt, "Efficient sampling ofrandom permutations", วารสารอัลกอริทึมที่ไม่ต่อเนื่องฉบับ 6 ฉบับที่ 1 ปี 2549 ลองดู Fisher-Yates shuffle และ Knuth Shuffle ด้วย Google คือเพื่อนของคุณ

อัลกอริทึมด้านล่างยังไปไม่ถึง ขอบคุณ @kelalaka สำหรับการแก้ไข

ป้อนข้อมูล: รายการ $A=\{1,2,\ldots, N\}$ ของ $N=2^n$ รายการ

งาน: เปลี่ยนค่าเป็น $A$ สุ่ม.

แต่ละ $i=0,\ldots,N-1$ ทำ

$\สี่เหลี่ยม$ เลือกจำนวนเต็มแบบสุ่ม $เจ$ กับ $i<j<N.$

$\สี่เหลี่ยม$ สลับรายการ $เอ[i]$ และ $ก[ญ].$

จบสำหรับ

เอาท์พุต: รายการ $A$ ตอนนี้เป็นแบบสุ่ม