ตัวอย่างการเรียงสับเปลี่ยนของประตูกลที่ปรับปรุงแล้ว (Enhanced TDP)

ฉันกำลังอ่านเกี่ยวกับ Trapdoor Permutations (TDP) ในขณะที่ฉันสามารถเข้าใจและนึกถึงตัวอย่างของ TDP ได้ทั้งหมด ฉันไม่สามารถนึกถึงตัวอย่างของ Enhanced TDP คำจำกัดความของทั้ง TDP และ Enhanced TDP แสดงไว้ด้านล่าง:

คอลเลกชันเรียงสับเปลี่ยนประตูกลมาตรฐาน : มันคือชุดของการเรียงสับเปลี่ยนที่ จำกัด ซึ่งแสดงแทน $\left\{f_{\alpha}: D_{\alpha} \rightarrow\right.$ $\left.D_{\alpha}\right\}$ซึ่งมาพร้อมกับอัลกอริทึมเวลาพหุนามที่น่าจะเป็นสี่ตัว แสดงแทน $I, S, F$ และ $B$ (สำหรับดัชนี ตัวอย่าง ไปข้างหน้าและข้างหลัง) เพื่อให้มีเงื่อนไข (วากยสัมพันธ์) ต่อไปนี้:

1. เมื่อป้อนข้อมูล $1^{n}$อัลกอริทึม $I$ เลือกโดยการสุ่ม $n$- ดัชนียาวบิต $\alpha$ (ไม่จำเป็นต้องสม่ำเสมอ) ของการเรียงสับเปลี่ยน $f_{\alpha}$พร้อมกับประตูกลที่สอดคล้องกัน $\tau$;
2. เมื่อป้อนข้อมูล $\alpha$อัลกอริทึม $S$ ตัวอย่างโดเมนของ $f_{\alpha}$ส่งคืนองค์ประกอบที่กระจายเกือบสม่ำเสมอในนั้น
3. สำหรับใดๆ $x$ ในโดเมนของ $f_{\alpha}$, ที่ให้ไว้ $\alpha$ และ $x$อัลกอริทึม $F$ ผลตอบแทน $f_{\alpha}(x)$ (เช่น., $\left.F(\alpha, x)=f_{\alpha}(x)\right)$;
4. สำหรับใดๆ $y$ ในช่วงของ $f_{\alpha}$ ถ้า $(\alpha, \tau)$ เป็นผลลัพธ์ที่เป็นไปได้ของ $I\left(1^{n}\right)$แล้วให้ $\tau$ และ $y$อัลกอริทึม $B$ ผลตอบแทน $f_{\alpha}^{-1}(y)$ (เช่น., $\left.B(\tau, y)=f_{\alpha}^{-1}(y)\right)$.

อนุญาต $I_{1}\left(1^{n}\right)$ หมายถึงองค์ประกอบแรกในผลลัพธ์ของ $I\left(1^{n}\right)$ (เช่น ดัชนี) จำเป็นสำหรับทุกอัลกอริธึมเวลาพหุนามเชิงความน่าจะเป็น $A$ (เช่น วงจรขนาดพหุนามทุกตระกูลที่ไม่สม่ำเสมอ $A=\left\{A_{n}\right\}_{n}$ ), เรามี $$ \underset{\substack{\alpha \leftarrow I_{1}\left(1^{n}\right) \ x \leftarrow S(\alpha)}}{\operatorname{Pr}}\left[A\left (\alpha, f_{\alpha}(x)\right)=x\right]=\mu(n), $$

หรือเทียบเท่า

$$ \underset{\substack{\alpha \leftarrow I_{1}\left(1^{n}\right) \ r \leftarrow R_{n}}}{\operatorname{Pr}}\left[A(\alpha , S(\alpha ; r))=f_{\alpha}^{-1}(S(\alpha ; r))\right]=\mu(n) $$

คอลเลกชันเรียงสับเปลี่ยนประตู Trapdoor ที่ได้รับการปรับปรุง : สิ่งเดียวที่เปลี่ยนเงื่อนไขสุดท้ายที่ฝ่ายตรงข้ามสามารถเข้าถึงเหรียญสุ่มของ $S$ $$ \underset{\substack{\alpha \leftarrow I_{1}\left(1^{n}\right) \ r \leftarrow R_n}}{\operatorname{Pr}}\left[A(\alpha, r) =f_{\alpha}^{-1}(S(\alpha ; r))\right]=\mu(n), $$