เป็นเรื่องปกติ / ถูกต้องหรือไม่ที่จะฮาร์ดโค้ดองค์ประกอบของภาษาลงในโปรแกรมจำลอง

เวอร์ชั่นสั้น: เป็นแนวปฏิบัติทั่วไป (และแนวปฏิบัติที่ถูกต้อง) หรือไม่ในการฮาร์ดโค้ดองค์ประกอบ $d \in \mathcal{L}$ ของภาษาลงในเครื่องจำลอง? (ทำให้เครื่องจำลองไม่สม่ำเสมอและไม่สร้างสรรค์)

รุ่นยาว:

ฉันมีข้อพิสูจน์ $พี$ ที่ทำสิ่งต่อไปนี้: ใช้สตริงบิต $d \in \mathcal{L}$ สำหรับบางภาษาใน $\textsf{NP}$จากนั้นจะเข้ารหัส $d$ ใช้การเข้ารหัสที่ปลอดภัยของ CPA เพื่อรับการเข้ารหัส $k$และส่งหลักฐาน Zero-Knowledge (NIZK) แบบไม่โต้ตอบ $\pi$ พิสูจน์ได้ว่า $k$ เข้ารหัสข้อความ $d \in \mathcal{L}$. ฉันอยากจะบอกว่าตอนนี้โครงการนี้ไม่มีการรั่วไหลของข้อมูลมากนัก $d$ในแง่ที่ว่ามีเครื่องจำลองอยู่ $ซิม$ เช่นนั้นสำหรับตัวตรวจสอบที่ไม่สม่ำเสมอที่เป็นอันตราย $วี^*$: $$\{Sim(V_\lambda^*)\}_{\lambda,d} \stackrel{comp}{\equiv} \{\textsf{OUT}_{V^*}(P_\lambda(d) \leftrightarrow V^*_\lambda)\}_{\lambda,d}$$

(ที่ $\{X_{\lambda,d}\}_{\lambda,d}\stackrel{comp}{\equiv}\{Y_{\lambda,d}\}_{\lambda,d}$ สัญลักษณ์แสดงถึงความสามารถในการแยกแยะความแตกต่างของคอมพิวเตอร์: สำหรับตัวแยกความแตกต่างที่ไม่สม่ำเสมอ $D$มีอยู่เล็กน้อย $\mu$ เช่นนั้นสำหรับทุกคน $\lambda \in \mathbb{N},d \in \mathcal{L}$, $|\Pr[D_\lambda(X_d)]-\Pr[D_\lambda(Y_d)]| < \mu(\แลมบ์ดา)$)

หากไม่มีส่วน NIZK การพิสูจน์ก็ง่าย: เครื่องจำลองของฉันจะเลือกแบบสุ่ม $d'$ และเข้ารหัสเป็น $k'$: แยกแยะไม่ออก $k$ และ $k'$ โดยไม่ทำลายความปลอดภัยของ CPA โดยสังหรณ์ใจแล้ว การเพิ่มหลักฐาน NIZK ไม่ควรทำให้ข้อมูลเพิ่มเติมรั่วไหล...อย่างไรก็ตาม ฉันไม่แน่ใจว่าจะจัดการกับกรณีนี้อย่างไร: ฉันมีความคิด แต่มันดูค่อนข้างแปลกสำหรับฉัน (ฉันไม่เคยเห็นวิธีการแบบนั้นมาก่อน) และฉันก็ค่อนข้างสงสัยเกี่ยวกับมัน

ปัญหาหลักของฉันคือถ้าฉันป้อนแบบสุ่ม $d'$ ถึง NIZK แล้ว $d'$ อาจไม่ใช่ของ $\mathcal{L}$ดังนั้นฉันจึงไม่สามารถใช้เครื่องจำลอง NIZK ได้ตามคาด $k$ เพื่อเป็นการเข้ารหัสของ $d \in \mathcal{L}$. ดังนั้นความคิดของฉันคือจะบอกว่าถ้า $\mathcal{L}$ ไม่ว่างเปล่า แสดงว่ามีสตริงอยู่ $d' \in \mathcal{L}$ (ซึ่งอาจจะเท่ากับหรือไม่ก็ได้ $d$). ถ้าฉันเข้ารหัสสตริงนี้เป็น $k'$, $k'$ ตอนนี้เป็นองค์ประกอบที่ "ถูกต้อง" เพื่อป้อนเข้าสู่เครื่องจำลอง NIZK ดังนั้นฉันจึงสามารถเรียกใช้โปรแกรมจำลอง NIZK ได้เลย $k'$ เพื่อรับ $ซิม$ ฉันต้องการ: การพิสูจน์ขั้นสุดท้ายของการแยกแยะไม่ได้จะเพิ่มการแจกแจงระดับกลาง ซึ่งเราใช้ $k$ ด้วยเครื่องจำลอง NIZK: เกมสองเกมแรกไม่น่าจะแยกแยะได้เนื่องจากคุณสมบัติ NIZK เกมสองเกมที่สองไม่น่าจะแยกแยะได้เนื่องจากคุณสมบัติ CPA (ฉันยังคงต้องเขียนร่างหลักฐานนี้อย่างเป็นทางการเพื่อตรวจสอบว่าไม่มีข้อผิดพลาดโง่ๆ หรือไม่)

อย่างไรก็ตาม ฮาร์ดโค้ดองค์ประกอบของ $\mathcal{L}$ เข้าไปข้างใน $ซิม$ ดูแปลกไปหน่อยสำหรับฉัน (โดยเฉพาะอย่างยิ่งเนื่องจากโปรแกรมจำลองไม่สร้างสรรค์และไม่สม่ำเสมอเนื่องจากสำหรับทุกขนาด $d$ เราต้องการความแตกต่าง $d'$). เป็นสิ่งที่พบได้ทั่วไป/ถูกต้องในการพิสูจน์ Zero-Knowledge หรือฉันขาดอะไรไป

อันที่จริงฉันสับสนโดยไม่มีเหตุผล (ขอบคุณไมเคิล): เราสามารถกำหนดเกมไฮบริดได้สองเกม (เราเพียงแค่ร่างหลักฐานที่นี่):

1. ในเกมแรกเราแทนที่ $\textsf{Proof}(k, (d, r))$ ($r$ เป็นการสุ่มที่ใช้ในการเข้ารหัส) ด้วย $ซิม(k)$: ดังนั้นข้อความที่ส่งไปคือตอนนี้ $(k, ซิม(k))$. เป็นไปไม่ได้ที่จะแยกแยะจาก $(k,\textsf{Proof}(k,(d,r)))$ เนื่องจากโปรโตคอลคือ ZK และ $k$ เป็นภาษาที่เหมาะสม (เช่น เป็นการเข้ารหัสของ $d \in \mathcal{L}$).
2. จากนั้นในไฮบริดที่สองเราจะแทนที่ $k$ ทั้งในข้อความและ Simulator โดยก $k'$ มาจากการเข้ารหัสแบบสุ่ม $d$ (ซึ่งอาจไม่ใช่ของ $\mathcal{L}$): ข้อความใหม่คือ $(k', Sim(k'))$. เป็นไปไม่ได้ที่จะแยกความแตกต่างจาก $(k, ซิม(k))$ หรือเราสามารถใช้โปรแกรมจำลองนี้เพื่อทำลาย IND-CPA: แนวคิดง่ายๆ คือขอให้ฝ่ายตรงข้ามเรียกใช้ $ซิม$ ในการเข้ารหัสอินพุต $e$แล้วส่ง $(อี,ซิม(อี))$ ให้กับผู้แยกแยะ เจฟฟรอยยังตั้งข้อสังเกตว่าเราต้องการ IND-CPA ที่นี่เพื่อต่อต้านศัตรูนอกเครื่องแบบ (ซึ่งเป็นคำจำกัดความมาตรฐานอยู่ดี) เหตุผลก็คือว่า $\stackrel{comp}{\equiv}$ ถูกกำหนดขึ้นสำหรับตัวแยกความแตกต่างที่ไม่สม่ำเสมอ ดังนั้นหากตัวแยกความแตกต่างที่ไม่สม่ำเสมอสามารถทำลาย IND-CPA ได้ ขั้นตอนนี้จะใช้ไม่ได้กับตัวแยกความแตกต่างดังกล่าว

เกี่ยวกับเครื่องจำลองที่ไม่สม่ำเสมอ (ขอบคุณ Geoffroy สำหรับการชี้แจง) คำจำกัดความมาตรฐานต้องใช้เครื่องจำลองเครื่องแบบ อย่างไรก็ตาม การมีเครื่องจำลองแบบไม่เป็นชุดจะช่วยรับประกันได้ และส่วนใหญ่แล้วการมีเครื่องจำลองแบบไม่เป็นชุดก็เป็นเรื่องปกติ เหตุผลคือเราคาดหวังว่าการรักษาความปลอดภัยจะคงอยู่แม้กับผู้ตรวจสอบที่ไม่ซื่อสัตย์ซึ่งไม่มีเครื่องแบบ ดังนั้นจึงเหมาะสมที่จะอนุญาตให้เครื่องจำลองไม่เหมือนกัน เนื่องจากมีหน้าที่รับผิดชอบในการจำลองผลลัพธ์ของผู้ตรวจสอบ