อัปเดต 20220330: คำตอบใหม่หลังจากการชี้แจงคำถาม คำตอบเก่ายังคงอยู่เพื่อให้เข้าใจถึงความคิดเห็น
ฉันคิดว่าสิ่งที่คุณถามคือบิตของ $y$ ทำหน้าที่เป็นฟังก์ชันฮาร์ดคอร์ในส่วนผกผันของฟังก์ชันทางเดียว (ในกรณีนี้ โมดูโลฟังก์ชันลอการิทึมแบบไม่ต่อเนื่อง $n$).สำหรับพื้นหลังของฟังก์ชันฮาร์ดคอร์ ดูตัวอย่างในหัวข้อ 2.4 สำหรับ รากฐานของการเข้ารหัส). อย่างไรก็ตาม หากการผกผันของฟังก์ชันทางเดียวนั้นง่ายต่อการคำนวณ (ซึ่งเป็นจริงในกรณีของคุณ เนื่องจากฟังก์ชันการยกกำลังสามารถคำนวณได้ในเวลาพหุนาม) แสดงว่าไม่มีฟังก์ชันฮาร์ดคอร์
นักเข้ารหัสไม่ได้นิยามสิ่งนี้ในแง่ของการแจกแจงแบบสม่ำเสมอ แต่ในแง่ของการจำแนกที่สามารถคำนวณได้ในเวลาพหุนามและให้ข้อได้เปรียบที่ไม่สำคัญ (ดูคำจำกัดความ 2.4 ของหมายเหตุ) พวกเขาบอกว่าภาคแสดง $ข(ย)$ เป็นฮาร์ดคอร์สำหรับ $f$ ถ้าสำหรับตัวจำแนกเวลาพหุนามทั้งหมดที่เรามี
$$\mathbb P(A(f(U_n)),1^n)=b(U_n)<1/2+1/p(n).$$
ในกรณีของคุณ $f$ เป็นฟังก์ชัน $y=g^x\mod n\mapsto x$ และหน้าที่ของคุณ $ข$ คือ $i$บิตของ $y=g^x\mod n$. อย่างไรก็ตาม ฉันมีตัวอย่างการแบ่งแยก $ก(z,1^n)$ ซึ่งก็คือการคำนวณ $g^z\mod n$ (ในเวลาพหุนาม) และดูที่ $i$บิต สิ่งนี้แยกแยะคำตอบด้วยความน่าจะเป็น 1 เพราะมีข้อโต้แย้งแรก $f(y)=x$ มันกลับมา $ข(ย)$.
กล่าวอีกนัยหนึ่งคือไม่มีความสม่ำเสมอที่ตรวจสอบได้ทางคอมพิวเตอร์เพราะฉันสามารถทดสอบได้อย่างรวดเร็ว $x$ ค่าเพื่อดูว่าพวกเขาสร้างผลลัพธ์ที่อยู่ในนั้นหรือไม่ $Y'$.
คำตอบเก่า
ใช่. อนุญาต $|Y'|=M$ และปล่อยให้ $z$ เป็นองค์ประกอบใด ๆ ของ $Y'$ แล้วทฤษฎีบทของเบส์บอกเราว่า
$$\mathbb P(g^x\mod n=z|g^x\mod n\in Y')=\frac{\mathbb P(g^x\mod n=z)\mathbb P(g^x \mod n\in Y'|g^c\mod n=z)}{\mathbb P(g^x\mod n\in Y')}.$$
ตอนนี้เราทราบว่า $\mathbb P(g^x\mod n=z)=1/\phi(n)$ (โดยความสม่ำเสมอที่ระบุไว้ในคำถาม) $\mathbb P(g^x\mod n\in Y'|g^c\mod n=z)=1$ และนั่น $\mathbb P(g^x\mod n\in Y')=M/\phi(n)$ (อีกครั้งโดยความสม่ำเสมอในคำถาม) ดังนั้น
$$\mathbb P(g^x\mod n=z|g^x\mod n\in Y')=1/M$$
สำหรับทุกอย่าง $z\ในY'$ ซึ่งอธิบายการกระจายแบบสม่ำเสมอ