ระบบพิสูจน์ความรู้เป็นศูนย์เชิงโต้ตอบสามารถนำมาใช้โดยใช้การคำนวณสองฝ่ายที่ปลอดภัยได้หรือไม่

ฉันกำลังกำหนดการคำนวณแบบหลายฝ่ายโดยใช้กระบวนทัศน์ในอุดมคติที่แท้จริง (ดู บทนำเชิงปฏิบัติเพื่อความปลอดภัยของคอมพิวเตอร์หลายฝ่าย). นั่นคือสำหรับการโจมตีโปรโตคอล MPC ที่ประสบความสำเร็จในโลกแห่งความจริง จะมีเครื่องจำลองที่ดำเนินการโจมตีนี้ได้สำเร็จในโลกแห่งอุดมคติ ตามมาว่าความปลอดภัยในโลกแห่งความเป็นจริงจะต้องเทียบเท่ากับความปลอดภัยในโลกอุดมคติ

ฉันกำลังกำหนดระบบการพิสูจน์ความรู้เป็นศูนย์เชิงโต้ตอบสำหรับภาษาหนึ่งๆ $L$ โดยใช้นิยามเดิมจาก ความซับซ้อนของความรู้ของระบบพิสูจน์แบบโต้ตอบ. นั่นคือคู่ $(ก, ข)$ ของเครื่องทัวริงแบบโต้ตอบจะต้องตอบสนอง

1. ความสมบูรณ์: ให้ $x \ใน L$, $B$ ยอมรับมีความเป็นไปได้สูงมาก
2. ความสมบูรณ์: ให้พิสูจน์ใด ๆ $A'$ และ $x \ไม่\ใน L$ ผ่านเข้าไป $(ก', ข)$, $B$ ยอมรับด้วยความน่าจะเป็นที่ต่ำมาก
3. Zero-Knowledge: มีตัวจำลองเวลาพหุนามที่น่าจะเป็นอยู่ซึ่งสามารถจำลองการแลกเปลี่ยนข้อความทั้งหมดระหว่าง $A$ และ $B$ สำหรับอินพุตใด ๆ $x \ใน L$.

ตอนนี้กระดาษ Zero-Knowledge จาก Secure Multiparty Computation กล่าวถึงสิ่งต่อไปนี้:

โปรโตคอลที่ไม่มีความรู้สามารถถูกมองว่าเป็นกรณีพิเศษของสองฝ่ายที่ปลอดภัย การคำนวณ โดยที่ฟังก์ชันตรวจสอบความถูกต้องของพยานที่ผู้พิสูจน์ถือไว้

นั่นคือได้รับ $L \in \mathcal{NP}$มีอัลกอริทึมอยู่ $A$ ดังนั้น $x \in L \iff \exists w\โคลอน A(x, w) = 1$ (ความหมายของ $\mathcal{NP}$). ฝ่ายหนึ่ง $P_1$ ทำหน้าที่เป็นผู้พิสูจน์อีกคนหนึ่ง $P_2$ เป็นผู้ตรวจสอบ $P_1$ รู้ $x$ และ $w$, $P_2$ รู้เท่านั้น $x$. พวกเขาดำเนินการ $ก(x,w)$ ร่วมกันพิจารณาว่า $x \ใน L$ หรือไม่.

เห็นได้ชัดว่า $w$ ไม่เปิดเผยต่อผู้ตรวจสอบ $P_2$ เนื่องจากโปรโตคอล MPC อย่างไรก็ตาม คำจำกัดความของความรู้เป็นศูนย์นั้นไม่กว้างไปกว่านั้นใช่หรือไม่ ถ้าผู้พิสูจน์ $P_1$ ส่ง ด้วยเหตุผลบางอย่าง วิธีแก้ปัญหาบางอินสแตนซ์ของ $\mathcal{NP}$ปัญหาที่สมบูรณ์¹ไม่มีเครื่องจำลองเวลาพหุนามใดที่สามารถจำลองสมมติฐานนี้ได้ $\mathcal{P} \neq \mathcal{NP}$. ระบบพิสูจน์ที่สร้างขึ้นจะไม่มีความรู้เป็นศูนย์

ดังนั้น เนื่องจากโปรโตคอล MPC สามารถแลกเปลี่ยนข้อความที่ไม่สามารถจำลองได้ จึงไม่สามารถใช้โปรโตคอล MPC เพื่อใช้ระบบพิสูจน์ความรู้เป็นศูนย์สำหรับบางภาษา $L \in \mathcal{NP}$ได้หรือไม่

¹ การแก้ปัญหาสามารถทำได้ขึ้นอยู่กับ $x$ ซึ่งไม่คงที่และจำลองได้ง่าย