Protokol GMW & Transfer Oblivious

Protokol Goldreich-Micali-Wigderson (GMW) mengevaluasi sirkuit Boolean menggunakan pembagian rahasia XOR. Nilai setiap jalur dibagi di antara semua pihak; mereka berinteraksi untuk setiap gerbang.

Pihak i memegang bagian s_i sedemikian rupa sehingga s_1 ⊕ s_2 ⊕ ... ⊕ s_n = w (nilai jalur yang sebenarnya). Gerbang XOR gratis: setiap pihak melakukan XOR secara lokal pada bagian mereka.

Untuk gerbang AND pada jalur a,b: menghitung (a_1⊕a_2)(b_1⊕b_2) menghasilkan suku-suku silang. Mengevaluasi suku silang a_i·b_j antara pihak i≠j memerlukan Oblivious Transfer.

Dalam OT 1-dari-2, pengirim memiliki pesan (m_0, m_1), sedangkan penerima memiliki bit pilihan c. Penerima memperoleh m_c; pengirim tidak mengetahui c; penerima tidak mengetahui m_{1-c}.

Protokol ini didasarkan pada Diffie-Hellman: penerima menghasilkan dua kunci publik sedemikian rupa sehingga ia hanya mengetahui logaritma diskret salah satunya. Pengirim mengenkripsi setiap pesan menggunakan salah satu kunci. Penerima hanya mendekripsi teks tersandi yang dipilihnya.

Ishai dkk. (2003): dari k OT dasar, hasilkan m >> k OT hanya dengan menggunakan operasi kunci simetris. Ekstensi IKNP mengurangi biaya OT menjadi sekitar 3 pemanggilan AES per OT setelah penyiapan satu kali.

Setiap gerbang AND memerlukan satu OT untuk setiap pasangan pihak. Dengan ekstensi OT, menghitung terlebih dahulu semua OT dalam fase luring memungkinkan fase daring hanya berupa satu pertukaran XOR per gerbang.

GMW semi-jujur dapat dibuat aman terhadap serangan berbahaya menggunakan bukti tanpa pengetahuan atau OT potong-dan-pilih. Biayanya meningkat 3–8×, tetapi memberikan jaminan keamanan terhadap pihak yang berbuat curang.

MASCOT (Keller dkk.) memperluas OT untuk menghasilkan tripel AND terautentikasi dalam model berbahaya, sehingga memungkinkan protokol SPDZ—yang dibahas dalam pelajaran berikutnya.

EMP-toolkit dan MOTION mengimplementasikan GMW dengan ekstensi OT. Keduanya mencapai jutaan gerbang AND per detik antara dua pihak melalui LAN, sehingga aplikasi nyata menjadi layak diterapkan.

Mengapa gerbang XOR dalam protokol GMW tidak memerlukan komunikasi antarpihak?

GMW menggunakan pembagian rahasia XOR pada sirkuit Boolean. Gerbang XOR gratis; gerbang AND memerlukan OT. Ekstensi OT membuat OT murah. Keamanan terhadap serangan berbahaya menambahkan bukti tanpa pengetahuan atau potong-dan-pilih. Pustaka seperti EMP menghasilkan laju pemrosesan praktis untuk aplikasi nyata.