โพรโทคอล GMW และการถ่ายโอนแบบไม่รู้ตัว

โพรโทคอล โกลด์ไรช์-มิชาลี-วิกเดอร์สัน (GMW) ประเมินวงจรบูลีนโดยใช้ส่วนแบ่งลับแบบ XOR ค่าบนสายแต่ละเส้นจะถูกแบ่งให้ผู้เข้าร่วมทุกฝ่าย และทุกฝ่ายจะโต้ตอบกันทีละเกต

ฝ่าย i ถือส่วนแบ่ง s_i ซึ่งเป็นไปตามเงื่อนไข s_1 ⊕ s_2 ⊕ ... ⊕ s_n = w โดย w คือค่าจริงบนสาย เกต XOR ไม่เสียค่าใช้จ่าย เพราะแต่ละฝ่ายทำ XOR ส่วนแบ่งของตนในเครื่องได้

สำหรับเกต AND บนสาย a,b การคำนวณ (a_1⊕a_2)(b_1⊕b_2) จะขยายเป็นพจน์ไขว้ การประเมินพจน์ไขว้ a_i·b_j ระหว่างฝ่าย i≠j ต้องใช้ Oblivious Transfer

ใน OT แบบ 1-จาก-2 ผู้ส่งมีข้อความ (m_0, m_1) ส่วนผู้รับมีบิตตัวเลือก c ผู้รับจะได้รับ m_c ผู้ส่งจะไม่เรียนรู้ค่า c และผู้รับจะไม่เรียนรู้ค่า m_{1-c}

โพรโทคอลนี้อาศัย Diffie-Hellman โดยผู้รับสร้างคีย์สาธารณะสองค่า ซึ่งเธอรู้ลอการิทึมไม่ต่อเนื่องของเพียงค่าเดียว ผู้ส่งเข้ารหัสแต่ละข้อความด้วยคีย์หนึ่งค่า และผู้รับถอดรหัสได้เฉพาะข้อความเข้ารหัสที่ตนเลือก

อิชาย และคณะ (2003): จาก OT พื้นฐาน k รายการ สามารถสร้าง OT จำนวน m >> k รายการโดยใช้เพียงการดำเนินการแบบคีย์สมมาตร ส่วนขยาย IKNP ลดต้นทุน OT เหลือประมาณการเรียกใช้เออีเอส 3 ครั้งต่อ OT หลังจากการตั้งค่าครั้งเดียว

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

GMW แบบกึ่งซื่อสัตย์สามารถทำให้ปลอดภัยต่อผู้มุ่งร้ายได้โดยใช้การพิสูจน์แบบไม่เปิดเผยความรู้หรือ OT แบบตัดและเลือก ต้นทุนจะเพิ่มขึ้น 3–8 เท่า แต่รับประกันความปลอดภัยต่อผู้เข้าร่วมที่โกง

MASCOT (เคลเลอร์ และคณะ) ขยาย OT เพื่อสร้างทริปเปิล AND ที่รับรองความถูกต้องในแบบจำลองผู้มุ่งร้าย ทำให้ใช้โพรโทคอล SPDZ ได้ ซึ่งจะกล่าวถึงในบทเรียนถัดไป

ชุดเครื่องมือ EMP และ MOTION ใช้ GMW พร้อมส่วนขยาย OT ทั้งสองสามารถประมวลผลเกต AND ได้หลายล้านเกตต่อวินาทีระหว่างสองฝ่ายผ่าน LAN ทำให้แอปพลิเคชันจริงสามารถใช้งานได้

เหตุใดเกต XOR ในโพรโทคอล GMW จึงไม่ต้องใช้การสื่อสารระหว่างผู้เข้าร่วม

GMW ใช้ส่วนแบ่งลับแบบ XOR บนวงจรบูลีน เกต XOR ไม่เสียค่าใช้จ่าย ส่วนเกต AND ต้องใช้ OT ส่วนขยาย OT ทำให้ OT มีต้นทุนต่ำ การรักษาความปลอดภัยต่อผู้มุ่งร้ายเพิ่มการพิสูจน์แบบไม่เปิดเผยความรู้หรือการตัดและเลือก ไลบรารีอย่าง EMP ให้ปริมาณงานที่ใช้งานได้จริงสำหรับแอปพลิเคชันจริง