ข้อมูลรั่วไหลสำหรับการให้เอาต์พุตที่อ่านไม่ออกของวงจรที่อ่านไม่ออกของเหยา

ฉันกำลังอ่านกระดาษ: การแลกเปลี่ยนประสิทธิภาพสำหรับสองฝ่ายที่เป็นอันตราย การคำนวณ. กระดาษอธิบายก $k$-leak model และให้ตัวอย่างว่าการรั่วไหล 1 บิตสามารถเปลี่ยนวงจรที่อ่านไม่ออกของ Yao จากการต่อต้านกึ่งซื่อสัตย์เป็นการต่อต้านที่เป็นอันตราย

ที่หน้า 14 ระบุว่าอลิซให้ผลลัพธ์ที่อ่านไม่ออกแก่บ็อบ ผู้สร้างวงจรที่อ่านไม่ออกแต่บ็อบจะไม่สร้างอินพุตของอลิซทั้งหมดใหม่โดยเอาต์พุตที่อ่านไม่ออกของอลิซและตารางการเปลี่ยนแปลง (เนื่องจากบ็อบเป็นผู้สร้างวงจร)

สิ่งนี้ทำให้อินพุตเพียง 1 บิตรั่วไหลได้อย่างไร

คำอธิบายในหน้า 14 ก็ทำให้ฉันสับสนเช่นกัน ฉันเชื่อว่าสิ่งสำคัญที่ควรทราบคือเอกสารนี้เสนอให้ใช้โปรโตคอล "การเปิดเผยความลับแบบมีเงื่อนไข" โดยอ้างถึง [แอร์01]. ดังนั้นเมื่อโครงร่างพูดว่า:

อลิซเปิดเผย $W_a$ ถึงบ๊อบถ้า $O_1 = O_2$และค่าสุ่ม $r_a \in \{0, 1\}^{|W_a|}$ มิฉะนั้น.

..คำว่า "เปิดเผย" อาจหมายถึงโปรโตคอลการเปิดเผยแบบมีเงื่อนไข ไม่ใช่แค่การส่งเท่านั้น $W_a$. ถ้าอลิซส่ง $W_a$ ถึง Bob คุณพูดถูก Bob สามารถเรียนรู้เอาต์พุตวงจรของ Alice ซึ่งมีการรั่วไหลมากกว่าหนึ่งบิต

มีเอกสารจำนวนมากที่สร้างเกี่ยวกับกระบวนทัศน์การดำเนินการสองทางแบบคลาสสิกนี้ จากเอกสารเหล่านั้น ฉันขอแนะนำวิธีง่ายๆ ต่อไปนี้ในการดำเนินการขั้นตอนสุดท้ายของการดำเนินการสองทาง ตราบใดที่คุณตกลงกับ oracle แบบสุ่ม เกี่ยวกับสัญกรณ์ ปล่อยให้ $[x]_A$ หมายถึงการเข้ารหัสเอาต์พุตที่อ่านไม่ออกของ $x$ในการเข้ารหัสที่อลิซเลือก

1. อลิซประเมินวงจรของบ็อบเพื่อให้ได้ผลลัพธ์ $O_1$ และผลลัพธ์ที่อ่านไม่ออก $[O_1]_B$. อลิซรู้การเข้ารหัสที่เธอใช้สำหรับเอาท์พุทวงจรของเธอ เธอจึงสามารถคำนวณได้เช่นกัน $[O_1]_A$
2. บ็อบประเมินวงจรของอลิซเพื่อให้ได้ผลลัพธ์ $O_2$ และการเข้ารหัสที่อ่านไม่ออก $[O_2]_A$. Bob รู้การเข้ารหัสที่เขาใช้สำหรับเอาต์พุตของวงจร ดังนั้นเขาจึงสามารถคำนวณได้เช่นกัน $[O_2]_B$
3. อลิซคำนวณ $h_A = H( [O_1]_A, [O_1]_B )$ แล้วส่งไปให้บ๊อบ
4. บ๊อบคำนวณ $h_B = H( [O_2]_A, [O_2]_B )$. ถ้า $h_A = h_B$ เขายอมรับผลลัพธ์ $O_2$มิฉะนั้นเขาจะทำแท้ง

ถ้าอลิซเป็นคนซื่อสัตย์และบ็อบเป็นคนทุจริต บ็อบสามารถเรียนรู้ผลลัพธ์ที่อ่านไม่ออกเพียงตัวเดียว $[\cdot]_A$ ภายใต้การเข้ารหัสของอลิซ โดยคุณสมบัติความถูกต้องของวงจรที่อ่านไม่ออกของอลิซ ดังนั้น Bob จึงไม่สามารถสอบถาม $H$ ในการเข้ารหัสที่ถูกต้อง $[x]_A$ ยกเว้น $[O_2]_A$. ถ้า $O_1 \n O_2$ ดังนั้นบ๊อบจึงไม่สามารถถามได้ $H$ ในจุดเดียวกับที่อลิซทำ ดังนั้น คุณค่าของเธอ $h_A$ ดูสุ่มอย่างสม่ำเสมอเพื่อบ๊อบ นั่นคือไม่มีการรั่วไหลของข้อมูลใด ๆ เกี่ยวกับ $O_1$ นอกเหนือจากข้อเท็จจริงที่ว่า $O_1 \n O_2$.

ฉันได้มุ่งเน้นไปที่วิธีโน้มน้าว Bob ว่าผลลัพธ์นั้นถูกต้อง ในการโน้มน้าวใจอลิซ คุณต้องทำการเปรียบเทียบแฮชเดียวกันในทั้งสองทิศทาง แต่คุณไม่สามารถใช้การเรียกฟังก์ชันแฮชเหมือนกันทุกประการในทั้งสองทิศทาง -- ใช้ nonce ที่แตกต่างกันสำหรับ "แฮชโทรเพื่อโน้มน้าวอลิซ" กับ "แฮชโทรเพื่อโน้มน้าวบ็อบ"