Komputasi Multi-Pihak Aman

Komputasi multi-pihak aman (MPC) memungkinkan pihak-pihak yang saling tidak percaya untuk secara bersama-sama menghitung suatu fungsi dari masukan pribadi mereka tanpa mengungkapkan apa pun selain keluaran yang disepakati.

Definition

Komputasi multi-pihak aman adalah protokol yang memungkinkan sekumpulan pihak, masing-masing memegang masukan pribadi, untuk menghitung fungsi yang disepakati sehingga setiap pihak mempelajari keluaran yang benar dan tidak ada yang lain tentang masukan pihak lain.

Scope

Topik ini mencakup protokol untuk komputasi aman: definisi keamanan simulasi ideal/nyata, sirkuit acak Yao untuk dua pihak, protokol berbasis pembagian rahasia (GMW, BGW) untuk banyak pihak, perbedaan antara keamanan semi-jujur dan berbahaya, serta kriptografi ambang. Ini membahas aplikasi praktis seperti irisan himpunan pribadi dan agregasi aman. Ini tidak termasuk bukti tanpa pengetahuan yang sering digunakan sebagai sub-protokol dan enkripsi homomorfik penuh yang menawarkan jalur alternatif untuk komputasi pada data terenkripsi.

Core questions

• Bagaimana pihak-pihak dapat menghitung data gabungan tanpa ada pihak yang melihat masukan pihak lain?
• Apa yang dibutuhkan paradigma simulasi ideal/nyata dari protokol yang aman?
• Bagaimana sirkuit acak memungkinkan komputasi dua pihak yang aman?
• Bagaimana protokol berbasis pembagian rahasia dapat diskalakan ke banyak pihak dan mentolerir korupsi?
• Apa perbedaan antara jaminan keamanan semi-jujur dan berbahaya?

Key concepts

• masukan pribadi dan keluaran bersama
• simulasi ideal/nyata
• sirkuit acak
• transfer tanpa sadar
• pembagian rahasia
• adversary semi-jujur vs berbahaya
• kriptografi ambang
• irisan himpunan pribadi
• mayoritas jujur vs mayoritas tidak jujur

Key theories

Keamanan simulasi ideal/nyata

Protokol MPC aman jika apa pun yang dapat dicapai musuh dalam protokol nyata juga dapat dicapai di dunia ideal di mana pihak tepercaya menghitung fungsi — menjamin privasi dan kebenaran terhadap korupsi yang dimodelkan.

Sirkuit acak dan pembagian rahasia

Sirkuit acak Yao memungkinkan dua pihak mengevaluasi sirkuit Boolean apa pun dengan satu pihak mengenkripsi tabel kebenaran dan pihak lain mendekripsi secara tanpa sadar; skema pembagian rahasia membagi masukan di antara pihak-pihak sehingga subset secara bersama-sama menghitung gerbang tanpa merekonstruksi rahasia.

Mechanisms

Dalam protokol dua pihak Yao, satu pihak mengacak sirkuit Boolean dengan mengenkripsi tabel kebenaran setiap gerbang dan pihak lain mengevaluasinya menggunakan kunci yang diperoleh melalui transfer tanpa sadar, hanya mempelajari keluarannya. Dalam pendekatan pembagian rahasia (GMW, BGW, SPDZ), setiap masukan dibagi menjadi bagian-bagian yang didistribusikan di antara pihak-pihak; gerbang penjumlahan dihitung secara lokal pada bagian-bagian dan gerbang perkalian menggunakan interaksi, setelah itu bagian-bagian keluaran direkonstruksi. Keamanan berbahaya menambahkan bukti tanpa pengetahuan atau bagian terautentikasi untuk mendeteksi kecurangan.

Clinical relevance

MPC bergerak dari teori ke penerapan untuk kolaborasi yang menjaga privasi: institusi menghitung statistik agregat atas kumpulan data gabungan tanpa mengumpulkan data mentah (studi kesenjangan upah gender Boston), perusahaan menjalankan irisan himpunan pribadi untuk penemuan kontak dan pengukuran iklan, tanda tangan ambang melindungi penyimpanan mata uang kripto dan kunci otoritas sertifikat, dan agregasi aman mendukung pembelajaran mesin yang menjaga privasi.

Evidence & guidelines

MPC didukung oleh kerangka kerja terbuka yang matang (misalnya, MP-SPDZ) dan semakin banyak oleh upaya standar dalam kriptografi ambang (proyek Kriptografi Ambang Multi-Pihak NIST). Jaminan keamanan sangat bergantung pada model korupsi yang diasumsikan (semi-jujur vs berbahaya) dan ambang korupsi (mayoritas jujur vs mayoritas tidak jujur), yang harus sesuai dengan asumsi kepercayaan penerapan.

History

Andrew Yao memperkenalkan komputasi dua pihak aman dan ide sirkuit acak pada tahun 1982-1986 (masalah jutawan). Goldreich, Micali, dan Wigderson (1987) memperluas komputasi aman ke sejumlah pihak, dan protokol BGW dan CCD (1988) memberikan keamanan teoretis informasi dengan mayoritas jujur. Puluhan tahun peningkatan efisiensi (ekstensi transfer tanpa sadar, SPDZ) membuat MPC cukup praktis untuk penerapan nyata pada tahun 2010-an.

Key figures

• Andrew Yao
• Oded Goldreich
• Silvio Micali
• Avi Wigderson
• Adi Shamir

Seminal works

• yao1982
• goldreich2004
• katz2020

Frequently asked questions

Bagaimana MPC berbeda dari enkripsi homomorfik?

Keduanya menghitung data pribadi, tetapi enkripsi homomorfik memungkinkan satu pihak untuk menghitung ciphertext yang tidak dapat dibacanya, sedangkan MPC mendistribusikan komputasi di antara beberapa pihak yang berinteraksi, tanpa ada satu pihak pun yang dapat melihat masukan. Keduanya terkadang digabungkan.

Apa arti keamanan 'semi-jujur' versus 'berbahaya'?

Keamanan semi-jujur (jujur-tetapi-penasaran) mengasumsikan pihak-pihak mengikuti protokol tetapi mencoba mempelajari informasi tambahan dari apa yang mereka lihat. Keamanan berbahaya secara tambahan melindungi dari pihak-pihak yang menyimpang secara sewenang-wenang dari protokol, yang lebih kuat tetapi lebih mahal.