มีวิธีออนไลน์ในการใช้ block cipher เพื่อสร้างบิต $n$ ที่ไม่ซ้ำกันซึ่งรับประกันการปราศจากการชนกันเป็นเวลา $2^n$ หรือไม่

$n$ เป็นตัวแปรรันไทม์ที่เลือกในแต่ละครั้งที่ผู้ใช้รันการใช้งาน

วิธีหนึ่งที่ฉันคิดได้คือใช้รหัสบล็อกใด ๆ เช่น AES เป็น CSPRNG ที่เมล็ดเพื่อสุ่มรายการตัวเลขแบบสุ่ม $0, 1, \ldots, 2^n-1$. ด้วยวิธีนี้ฉันรับประกันการปราศจากการชนกันได้ถึง $2^n$ ตัวเลข แต่วิธีการนี้แพงเกินไปเพราะจะต้องเปลี่ยน $2^n$ ตัวเลข

อีกวิธีหนึ่งที่ฉันคิดได้คือการใช้ block cipher เพื่อสร้าง ciphertext $c = \mathrm{enc}(\mathrm{0x000}\ldots, \mathrm{key})$, ที่ไหน $\mathrm{len}(c) \ge n$. แล้วเอาที่ 1 $n$ หลายบิตของ $ค$; มาเรียกมันว่า $c_n$. จากนั้นทำ: $c_n \oplus 0, c_n \oplus 1, \ldots, c_n \oplus 2^n-1$. สิ่งนี้มีประสิทธิภาพ แต่ปัญหาคือ ฉันคิดว่าลำดับไม่สุ่ม เช่น. $c_n \oบวก 0$ โดยทั่วไปจะใกล้เคียงกับ $c_n \oบวก 1$ กว่าพูด $c_n \oบวก 100$.

คำถาม: มีวิธีไหนเร็วกว่านี้ไหม ที่ฉันสามารถใช้รหัสบล็อกใดๆ ก็ได้เพียงครั้งเดียว เพื่อสร้างตัวเลขถัดไป เช่นนั้น เมื่อฉันทำกระบวนการซ้ำ ฉันจะได้รับ $2^n$ ตัวเลขที่ไม่ซ้ำกันมากมายโดยไม่มีการชนกัน?

ในแง่หนึ่ง ฉันเดาว่าฉันอาจเรียกมันว่า: เวอร์ชั่นออนไลน์ของการสับตัวเลข $0, 1, \ldots, 2^n-1$โดยไม่จำเป็นต้องเก็บรายการไว้ในหน่วยความจำนั่นคือ $2^n$ ยาว.

ตามหลักการแล้ว หากพบการสุ่มออนไลน์ที่สมบูรณ์แบบ จะต้องมีการกระจายนี้ (โดยที่ $i$ เป็นเลขใดใน $\{0, 1, \ldots, 2^n-1\}$ และ $N_j$ เป็นตัวแปรสุ่มที่จะรับค่าของตัวเลขในชุดนั้นมาไว้ใน $j^{th}$ การโทรของ shuffler ออนไลน์ในอุดมคติ):

$$\begin{แยก} \Pr(N_0 = ผม) &= 1/2^n \ \Pr(N_1 = ผม) &= 1/(2^n - 1) \ \Pr(N_2 = ผม) &= 1/(2^n - 2) \ \vจุด & \ \Pr(N_{2^n-1} = i) &= 1/(2^n - (2^n-1)) = 1\ \end{แยก}$$