Masalah MPC & Sirkuit Terenkripsi Yao

MPC memungkinkan n pihak, yang masing-masing memegang masukan privat x_i, menghitung f(x_1,...,x_n) bersama-sama tanpa mengungkapkan masukan mereka satu sama lain—seolah-olah pihak ketiga tepercaya yang menghitungnya.

Masalah Para Jutawan Yao pada tahun 1982: Alice dan Bob ingin mengetahui siapa yang lebih kaya tanpa mengungkapkan kekayaan mereka. Tidak ada pihak ketiga tepercaya. MPC menyelesaikan hal ini dengan jaminan kriptografi.

1. Privasi: pihak-pihak hanya mengetahui keluaran dan hal-hal yang dapat mereka simpulkan darinya. 2. Kebenaran: keluaran tetap benar meskipun beberapa pihak telah disusupi. 3. Tersedia varian untuk penyerang semi-jujur dan penyerang berbahaya.

Fungsi apa pun dapat dinyatakan sebagai sirkuit Boolean (gerbang AND, XOR, NOT). Protokol MPC sering bekerja pada tingkat sirkuit dengan mengevaluasi setiap gerbang secara aman.

Alice (pembuat sirkuit tersamar) menetapkan dua label acak untuk setiap jalur: satu untuk 0 dan satu untuk 1. Ia mengenkripsi tabel kebenaran setiap gerbang menggunakan label jalur masukan. Bob (pengevaluasi) hanya mengetahui label untuk masukannya melalui transfer tanpa pengetahuan.

Bob menerima tabel tersamar (4 enkripsi untuk setiap gerbang AND). Ia mendekripsi tepat satu baris menggunakan label masukannya dan memperoleh label keluaran—tanpa mengetahui apakah label tersebut mewakili 0 atau 1.

Tambahkan "bit pemilih" acak ke setiap label. Bob menggunakan bit pemilih untuk menemukan baris tersamar yang benar dalam O(1), alih-alih mencoba keempat dekripsi. Hal ini mengurangi komputasi sebesar 4×.

Kolesnikov & Schneider (2008): pilih pergeseran global Δ. Kemudian label_1 = label_0 ⊕ Δ untuk setiap jalur. Gerbang XOR menjadi gratis (tidak memerlukan enkripsi), sehingga menghemat sekitar 30% lebar pita.

Zahur dkk. (2015): setiap gerbang AND hanya memerlukan 2 teks tersandi (turun dari 4). Jika digabungkan dengan XOR Gratis, hal ini memangkas separuh lebar pita sirkuit tersamar standar.

Sirkuit tersamar klasik digunakan oleh 2 pihak. Ekstensi multipihak (misalnya, protokol BMR) memparalelkan proses penyamaran di semua pihak, tetapi memerlukan komunikasi O(n²). Pendekatan ini praktis untuk nilai n yang kecil.

Dalam protokol sirkuit tersamar Yao, bagaimana Bob memperoleh label jalur yang sesuai dengan bit masukan privatnya?

MPC memungkinkan pihak-pihak menghitung bersama tanpa mengungkapkan masukan. Sirkuit tersamar menyandikan fungsi Boolean sebagai tabel kebenaran terenkripsi. Pengoptimalan (XOR Gratis, Gerbang Setengah, Tunjuk-dan-Permutasi) membuatnya praktis. OT mengirimkan label masukan Bob secara privat.