หลักฐานการรักษาความปลอดภัยเกี่ยวกับตัวอย่างเคาน์เตอร์ที่ไม่มีความรู้ซึ่งมีความปลอดภัยในแบบจำลองสแตนด์อโลน แต่ไม่ปลอดภัยในแบบจำลอง UC

พื้นหลัง

ตัวอย่างการตอบโต้ด้วยความรู้เป็นศูนย์ (ZK) ต่อไปนี้อธิบายไว้ในงานของ Canetti [ความปลอดภัยและองค์ประกอบของ Cryptographic Protocols: บทช่วยสอน, หน้า 26] เพื่อแสดงว่ามีบางโปรโตคอลที่ปลอดภัยในโมเดลสแตนด์อะโลน แต่ไม่ปลอดภัยในโมเดล UC:

สมมติว่ามี "ระบบปริศนา" ที่ทั้งผู้พิสูจน์และผู้ตรวจสอบสามารถสร้างปริศนาได้อย่างมีประสิทธิภาพ และ

• ผู้พิสูจน์สามารถไขปริศนาใด ๆ ได้อย่างมีประสิทธิภาพและ
• ผู้ตรวจสอบไม่สามารถ (i) ไขปริศนาได้อย่างมีประสิทธิภาพ หรือ (ii) แยกความแตกต่างระหว่างวิธีแก้ปัญหาที่ถูกต้องหรือสุ่มไม่ถูกต้องสำหรับปริศนาหนึ่งๆ แม้ว่าปริศนานั้นจะถูกสร้างขึ้นเองก็ตาม

ตอนนี้ได้รับโปรโตคอล ZK $\pi$ สำหรับความสัมพันธ์ NP บางอย่าง $R$เราสามารถสร้างโปรโตคอลอื่นได้ $\pi'$ ที่ไหน

1. ผู้พิสูจน์และผู้ตรวจสอบทำงาน $\pi$,
2. ผู้พิสูจน์ส่งปริศนาแบบสุ่ม $p$ ถึงผู้ตรวจสอบ
3. ผู้ตรวจสอบตอบกลับด้วยโซลูชัน "ที่ถูกกล่าวหา" $s$ สำหรับ $p$บวกกับปริศนา $p'$,
4. ถ้า $s$ เป็นทางออกที่ถูกต้องสำหรับ $p$ผู้พิสูจน์เผยพยานลับ $w$ (ในโปรโตคอล ZK $\pi$) ไปยังผู้ตรวจสอบ มิฉะนั้นผู้พิสูจน์จะส่งวิธีแก้ไข $s'$ สำหรับ $p'$ ให้กับผู้ตรวจสอบ

คำถามของฉันเกี่ยวกับการรักษาความปลอดภัยในรูปแบบสแตนด์อโลน

ตามที่อ้างในงานของ Canetti ถ้า $\pi$ ZK อยู่ใน แบบสแตนด์อโลน การตั้งค่าก็เป็นเช่นนั้น $\pi'$. ที่เห็นนี้ผมถือว่า $\pi$ ใช้งานฟังก์ชัน ZK ได้อย่างปลอดภัย $\mathcal{F}_{\textsf{zk}}^R: ((x, w), x) \rightarrow (\lambda, R(x, w))$ ในการตั้งค่าแบบสแตนด์อโลนและพยายามแสดงให้เห็นว่า $\pi'$ ยังตระหนักอย่างปลอดภัย $\mathcal{F}_{\textsf{zk}}^R: ((x, w), x) \rightarrow (\lambda, R(x, w))$. โดยเฉพาะอย่างยิ่งหากผู้ตรวจสอบเป็นอันตรายใน $\pi'$ฉันสามารถสร้างโปรแกรมจำลองต่อไปนี้ได้ $\mathcal{S}_V$ นั่น ภายใน เรียกใช้ศัตรูในโลกแห่งความเป็นจริง $\mathcal{A}$:

• $\mathcal{S}_V$ เรียกใช้โปรแกรมจำลองสำหรับ $\pi$ เพื่อสร้าง $\pi$- ส่วนการถอดความระหว่างผู้พิสูจน์ที่ซื่อสัตย์และผู้ตรวจสอบที่เป็นอันตราย (หรือเทียบเท่า เราสามารถใช้ถ้อยคำนี้ใหม่ใน $\mathcal{F}_{\textsf{zk}}^R$-รุ่นไฮบริด)
• $\mathcal{S}_V$ ส่งปริศนาแบบสุ่ม $p$ ถึง $\mathcal{A}$,
• $\mathcal{S}_V$ รับคู่ $(s, p')$ จาก $\mathcal{A}$,
• ถ้า $s$ เป็นทางออกที่ถูกต้องสำหรับ $p$, $\mathcal{S}_V$ ยกเลิก มิฉะนั้น, $\mathcal{S}_V$ ส่งวิธีแก้ปัญหา $s'$ สำหรับ $p'$ ถึง $\mathcal{A}$.

เป็นที่ชัดเจนว่าเว้นแต่ $\mathcal{S}_V$ ยกเลิกการดำเนินการในอุดมคติต่อหน้า $\mathcal{S}_V$ แยกไม่ออกจากการปฏิบัติจริงต่อหน้า $\mathcal{A}$. ด้วยสมมติฐาน (i) เราจะเห็นว่าการยกเลิกนี้เกิดขึ้นด้วยความน่าจะเป็นเล็กน้อย ดังนั้น, $\pi'$ ปลอดภัยจากตัวตรวจสอบที่เป็นอันตราย ดังนั้น ZK

คำถามที่ 1:

สิ่งที่ทำให้ฉันสับสนก็คือการพิสูจน์ข้างต้นไม่จำเป็นต้องมีสมมติฐาน (ii) อันที่จริง Canetti แย้งว่า

นอกจากนี้ความจริงที่ว่า $พี$ (กล่าวคือผู้พิสูจน์) ให้ $วี$ (เช่น ผู้ตรวจสอบ) ด้วยวิธีแก้ปัญหา $s'$ ต่อปริศนา $p'$ ไม่ใช่ปัญหาในการตั้งค่าแบบสแตนด์อโลนเนื่องจาก $วี$ ไม่สามารถแยกแยะได้ $s'$ จากการสุ่มค่า (ซึ่ง $วี$ อาจเกิดขึ้นเอง)

สมมติฐานนี้ช่วยสร้างคุณสมบัติ ZK ของ $\pi'$ ในการตั้งค่าแบบสแตนด์อะโลน?

ความเข้าใจของฉัน:

สำหรับฉัน การดำเนินการตามลำดับของ $\pi'$ (แม้สำหรับอินพุตเดียวกัน) ยังคงเป็น ZK เนื่องจากผู้พิสูจน์ที่ซื่อสัตย์สุ่มตัวอย่างปริศนาแบบสุ่ม $p$ แต่ละครั้ง.ปริศนาเหล่านี้แตกต่างจากปริศนาที่ผู้ตรวจสอบผู้ประสงค์ร้ายรู้จักคำตอบซึ่งมีความเป็นไปได้สูง (ขึ้นอยู่กับพื้นที่ของปริศนา) ดังนั้น ผู้ตรวจสอบจึงไม่สามารถใช้ปริศนาที่ทราบเหล่านี้เพื่อบังคับให้ผู้พิสูจน์ให้ผลลัพธ์ของพยานที่มีความน่าจะเป็นที่ไม่สำคัญในการดำเนินการตามลำดับของ $\pi'$.

แน่นอน ในการรวมสมมติฐาน (ii) เข้าในการพิสูจน์ ดูเหมือนว่าเราสามารถแก้ไขได้ $\mathcal{S}_V$ ดังนั้นในขั้นตอนสุดท้าย $\mathcal{S}_V$ ส่งวิธีแก้ปัญหาแบบสุ่ม $s'$ ถึง $\mathcal{A}$ (แทนที่จะเป็นวิธีแก้ปัญหาที่ถูกต้องสำหรับ $p'$). เราพิจารณาสิ่งนั้นโดยไม่สูญเสียภาพรวม $\mathcal{A}$ แสดงมุมมองในกรณีนี้ แล้วเราจะเห็นว่าการแก้ปัญหา $s'$ รวมอยู่ใน $\mathcal{A}$มุมมองของ เพื่อให้ได้ความปลอดภัยที่เป็นอันตรายในรูปแบบสแตนด์อโลน โซลูชันแบบสุ่ม $s'$ ในการจำลองควรแยกไม่ออกจากการดำเนินการจริง อย่างไรก็ตาม ข้อสันนิษฐานของการที่ผู้ตรวจสอบไม่สามารถแยกความแตกต่างของโซลูชันไม่สามารถแปลได้ว่าตัวแยกความแตกต่าง (ซึ่งแยกความแตกต่างระหว่างการดำเนินการในอุดมคติและการดำเนินการจริง) ไม่สามารถแยกความแตกต่างระหว่างโซลูชันจริงและแบบสุ่ม ดังนั้น สมมติฐาน (ii) จึงดูไร้ประโยชน์เนื่องจากตัวแยกความแตกต่างยังคงสามารถแยกแยะโลกทั้งสองได้อย่างมีประสิทธิภาพโดยการสังเกตวิธีแก้ปัญหา $s'$ ใน $\mathcal{A}$มุมมองของ

ในความเห็นของฉัน ปัญหานี้อาจมาจากการลดลงระหว่างสมมติฐาน (i) และ (ii) เป็นการลดลงระหว่างสมมติฐาน CDH และ DDH การลดลงนี้ทำให้หนึ่งในสองสมมติฐานซ้ำซ้อน นี่เป็นความเข้าใจที่ถูกต้องหรือไม่?

คำถามของฉันเกี่ยวกับความปลอดภัยในโมเดล UC

ตามที่อ้างไว้ในงานของ Canetti $\pi'$ ไม่ปลอดภัยในโมเดล UC เนื่องจากมีการดำเนินการพร้อมกันสองครั้งของ $\pi'$ ด้วยอินพุตเดียวกัน $(x, w)$ อาจทำให้พยานรั่วไหลได้ $w$ ไปยังตัวตรวจสอบที่เป็นอันตราย โดยเฉพาะอย่างยิ่ง การโจมตีทำงานดังนี้:

$วี$ รอรับปริศนาก่อน $p_1$ และ $p_2$ จาก $พี$ ในสองช่วง จากนั้นจะส่ง $(s, p_2)$ ถึง $พี$ ในเซสชั่นแรกสำหรับบางคนโดยพลการ $s$. ในการตอบสนอง $วี$ ได้รับจาก $พี$ วิธีแก้ปัญหา $s_2$ ถึง $p_2$ซึ่งมันกลับไปที่ $พี$ ในเซสชั่นที่สอง เนื่องจาก $s_2$ เป็นการแก้ปัญหาที่ถูกต้อง $พี$ เดี๋ยวจะเปิดเผย $w$.

ให้เราสันนิษฐานว่า $\pi$ ตระหนักอย่างปลอดภัย $\mathcal{F}_{\textsf{zk}}^R$ ในแบบจำลอง UC และทบทวนความไม่ปลอดภัยนี้จากมุมมองของการพิสูจน์ความปลอดภัย ตอนนี้ เราอาจพิจารณาเครื่องจำลอง $\mathcal{S}_V'$ ในรุ่น UC โดยเฉพาะอย่างยิ่ง, $\mathcal{S}_V'$ เหมือนกันกับ $\mathcal{S}_V$ ยกเว้นว่ามัน ภายนอก โต้ตอบกับเครื่องสภาพแวดล้อม $\คณิตศาสตร์แคล{Z}$ ซึ่งทำหน้าที่เป็นตัวตรวจสอบที่เป็นอันตราย (แทนที่จะเป็น ภายใน มีปฏิสัมพันธ์กับ $\mathcal{A}$). เนื่องจาก $\pi'$ ไม่ปลอดภัย UC $\mathcal{S}_V'$ ควรยกเลิกในขั้นตอนสุดท้ายด้วยความน่าจะเป็นที่ไม่สำคัญ กล่าวอีกนัยหนึ่ง $\คณิตศาสตร์แคล{Z}$ จะสามารถไขปริศนาได้อย่างมีประสิทธิภาพ $p$ สุ่มตัวอย่างโดยผู้พิสูจน์ที่ซื่อสัตย์ $\คณิตศาสตร์แคล{Z}$ มีข้อมูลมากกว่า $\mathcal{A}$ ในรูปแบบสแตนด์อะโลนตั้งแต่การแก้ปัญหา $s$ เลือกโดย $\คณิตศาสตร์แคล{Z}$ ขึ้นอยู่กับมุมมองในเซสชันปัจจุบันเท่านั้น แต่ยังขึ้นอยู่กับมุมมองอื่นที่เกิดขึ้นพร้อมกันด้วย ดังนั้น ดูเหมือนจะมีสองทางที่เป็นไปได้สำหรับ $\คณิตศาสตร์แคล{Z}$ เพื่อแก้ปัญหา $p$: (ก) $\คณิตศาสตร์แคล{Z}$ แก้ปัญหา $p$ ด้วยตัวเอง หรือ (b) $\คณิตศาสตร์แคล{Z}$ ไม่สามารถแก้ไขได้อย่างมีประสิทธิภาพ $p$ แต่ใช้เซสชันอื่นเพื่อแก้ปัญหา การโจมตีเป็นของกรณี (b)

คำถามที่ 2:

แม้ว่าเราจะคิดอย่างนั้นก็ตาม $\คณิตศาสตร์แคล{Z}$ ไม่สามารถเปิด case (b) โจมตีได้ใช่ไหม $\pi'$ ยังไม่ปลอดภัยในรุ่น UC? สำหรับผม ถ้า $\คณิตศาสตร์แคล{Z}$ สามารถปฏิบัติตามรหัสของผู้พิสูจน์ที่ซื่อสัตย์เพื่อแก้ไข $p$ และข้อสันนิษฐาน (i) เกี่ยวกับผู้ตรวจสอบไม่มีผลกับ $\คณิตศาสตร์แคล{Z}$. ในกรณีนี้, $\คณิตศาสตร์แคล{Z}$ สามารถใช้ case (a) โจมตีเพื่อแยกแยะสองโลก

โดยทั่วไป หากเราตั้งสมมติฐานเกี่ยวกับฝ่ายที่เสียหายในโมเดล UC ให้นำสมมติฐานเหล่านี้ไปใช้กับเครื่องสภาพแวดล้อม $\คณิตศาสตร์แคล{Z}$ ที่ควบคุมฝ่ายเหล่านี้? โปรดทราบว่าในรูปแบบสแตนด์อโลน ผู้แยกแยะและฝ่ายตรงข้ามเป็นหน่วยงานที่แตกต่างกัน ในทางตรงกันข้าม ความแตกต่างและฝ่ายตรงข้ามเป็นทั้งเครื่องจักรสภาพแวดล้อม $\คณิตศาสตร์แคล{Z}$ ในรุ่น UC

คำถามที่ 3:

เพื่อยืนยันอย่างเป็นทางการว่าโปรโตคอลมีความปลอดภัยในโมเดล UC เราควรระบุวิธีที่เป็นไปได้ทั้งหมดอย่างชัดเจนสำหรับ $\คณิตศาสตร์แคล{Z}$ เพื่อสร้างข้อความขาออกตามมุมมองของการดำเนินการแบบอะซิงโครนัสตามอำเภอใจของเซสชัน (ไม่จำกัดจำนวนครั้ง)

ฉันได้อ่านบทพิสูจน์ของ UC แล้ว แต่ส่วนใหญ่ไม่ได้กล่าวถึงการดำเนินการเซสชันแบบอะซิงโครนัสอย่างชัดเจน เนื่องจากโปรโตคอลเหนือเซสชันอื่นสามารถกำหนดได้ตามอำเภอใจ ฉันคิดว่าเป็นไปไม่ได้ที่จะแจกแจง $\คณิตศาสตร์แคล{Z}$ข้อความของอิงจาก $\คณิตศาสตร์แคล{Z}$มุมมองของเซสชันทั้งหมด แล้วเราจะแน่ใจได้อย่างไรว่า $\คณิตศาสตร์แคล{Z}$ข้อความที่ส่งต่อไปยังโปรแกรมจำลองจะไม่ล้มเหลวในการจำลองเมื่อเราเขียนหลักฐานความปลอดภัยในแบบจำลอง UC?