ปัญหา MPC และวงจรบูลีนที่ทำให้สับสนของ Yao

MPC เปิดให้ผู้เข้าร่วม n ฝ่าย ซึ่งแต่ละฝ่ายถืออินพุตส่วนตัว x_i ร่วมกันคำนวณ f(x_1,...,x_n) โดยไม่เปิดเผยอินพุตของตนแก่กันและกัน เสมือนว่าบุคคลที่สามซึ่งเชื่อถือได้เป็นผู้คำนวณให้

ปัญหาเศรษฐีของเหยาในปี 1982: อลิซและบ็อบต้องการทราบว่าใครร่ำรวยกว่าโดยไม่เปิดเผยทรัพย์สินของตน และไม่มีบุคคลที่สามซึ่งเชื่อถือได้ MPC แก้ปัญหานี้ด้วยหลักประกันทางการเข้ารหัส

1. ความเป็นส่วนตัว: ผู้เข้าร่วมจะเรียนรู้เฉพาะเอาต์พุตและสิ่งที่อนุมานได้จากเอาต์พุตนั้น 2. ความถูกต้อง: เอาต์พุตยังถูกต้องแม้ผู้เข้าร่วมบางรายจะถูกควบคุม 3. มีรูปแบบต่างกันสำหรับผู้โจมตีที่ปฏิบัติตามโพรโทคอลแต่พยายามเรียนรู้ข้อมูลเพิ่มเติม และผู้โจมตีที่มุ่งร้าย

ฟังก์ชันใด ๆ สามารถเขียนแทนได้ด้วยวงจรบูลีน ซึ่งประกอบด้วยเกต AND, XOR และ NOT โพรโทคอล MPC มักทำงานในระดับวงจร โดยประเมินค่าแต่ละเกตอย่างปลอดภัย

อลิซในฐานะผู้สร้างวงจรพรางกำหนดป้ายกำกับแบบสุ่มสองค่าให้กับสายแต่ละเส้น ได้แก่ค่าหนึ่งสำหรับ 0 และอีกค่าสำหรับ 1 จากนั้นเธอเข้ารหัสตารางค่าความจริงของแต่ละเกตโดยใช้ป้ายกำกับของสายอินพุต บ็อบในฐานะผู้ประเมินจะเรียนรู้เฉพาะป้ายกำกับสำหรับอินพุตของตนผ่าน Oblivious Transfer

บ็อบได้รับตารางพราง ซึ่งมีการเข้ารหัส 4 รายการต่อเกต AND หนึ่งเกต เขาถอดรหัสเพียงแถวเดียวโดยใช้ป้ายกำกับอินพุตของตน และได้ป้ายกำกับเอาต์พุตโดยไม่ทราบว่าป้ายกำกับนั้นแทนค่า 0 หรือ 1

เพิ่ม “บิตเลือก” แบบสุ่มให้กับป้ายกำกับแต่ละค่า บ็อบใช้บิตเลือกเพื่อค้นหาแถวที่ถูกต้องในตารางพรางด้วยเวลา O(1) แทนการลองถอดรหัสทั้งสี่รายการ ทำให้การคำนวณลดลง 4 เท่า

โคเลสนิคอฟและชไนเดอร์ (2008) เสนอให้เลือกค่าเลื่อนส่วนกลาง Δ จากนั้นกำหนดให้ label_1 = label_0 ⊕ Δ สำหรับสายทุกเส้น เกต XOR จึงไม่เสียค่าใช้จ่าย เพราะไม่จำเป็นต้องเข้ารหัส ช่วยประหยัดแบนด์วิดท์ได้ประมาณ 30%

ซาฮูร์ และคณะ (2015): เกต AND แต่ละเกตต้องใช้ข้อความเข้ารหัสเพียง 2 รายการ ลดลงจาก 4 รายการ เมื่อใช้ร่วมกับการปรับแบบ XOR ฟรี วิธีนี้ลดแบนด์วิดท์ของวงจรพรางมาตรฐานลงครึ่งหนึ่ง

วงจรพรางแบบคลาสสิกใช้สำหรับสองฝ่าย ส่วนส่วนขยายสำหรับหลายฝ่าย เช่น โพรโทคอล BMR จะทำให้การสร้างวงจรพรางของทุกฝ่ายทำงานขนานกัน แต่ต้องใช้การสื่อสาร O(n²) จึงเหมาะกับค่า n ขนาดเล็ก

ในโพรโทคอลวงจรพรางของเหยา บ็อบได้รับป้ายกำกับสายที่ตรงกับบิตอินพุตส่วนตัวของตนอย่างไร

MPC ช่วยให้ผู้เข้าร่วมคำนวณร่วมกันได้โดยไม่เปิดเผยอินพุต วงจรพรางเข้ารหัสฟังก์ชันบูลีนเป็นตารางค่าความจริงที่เข้ารหัส การปรับให้เหมาะสม เช่น XOR ฟรี เกตครึ่งหนึ่ง และการชี้และสับเปลี่ยนลำดับ ทำให้ใช้งานได้จริง OT ส่งมอบป้ายกำกับอินพุตของบ็อบอย่างเป็นส่วนตัว