Güvenli Çok Taraflı Hesaplama
Güvenli çok taraflı hesaplama (MPC), karşılıklı olarak güvensiz tarafların, üzerinde anlaşılan çıktı dışında hiçbir şeyi ifşa etmeden, özel girdilerinin bir fonksiyonunu ortaklaşa hesaplamasına olanak tanımaktadır.
Tanım
Güvenli çok taraflı hesaplama, her biri özel bir girdiye sahip olan bir dizi tarafın, üzerinde anlaşılan bir fonksiyonu hesaplamasına olanak tanıyan bir protokoldür; bu sayede her taraf doğru çıktıyı öğrenir ve diğerlerinin girdileri hakkında başka hiçbir bilgi edinmez.
Kapsam
Bu konu, güvenli hesaplama protokollerini kapsamaktadır: ideal/gerçek simülasyon güvenlik tanımı, iki taraf için Yao'nun karıştırılmış devreleri (garbled circuits), çok sayıda taraf için sır paylaşımına dayalı protokoller (GMW, BGW), yarı-dürüst (semi-honest) ve kötü niyetli (malicious) güvenlik arasındaki ayrım ve eşik kriptografisi (threshold cryptography). Özel küme kesişimi (private set intersection) ve güvenli toplama (secure aggregation) gibi pratik uygulamalara değinmektedir. Genellikle bir alt protokol olarak kullanılan sıfır bilgi ispatlarını (zero-knowledge proofs) ve şifreli veriler üzerinde hesaplama için alternatif bir yol sunan tam homomorfik şifrelemeyi (fully homomorphic encryption) içermemektedir.
Temel sorular
- Taraflar, diğerlerinin girdilerini görmeden birleştirilmiş veriler üzerinde nasıl hesaplama yapabilir?
- İdeal/gerçek simülasyon paradigması, güvenli bir protokolden ne gerektirmektedir?
- Karıştırılmış devreler, güvenli iki taraflı hesaplamayı nasıl mümkün kılmaktadır?
- Sır paylaşımına dayalı protokoller, çok sayıda tarafa nasıl ölçeklenebilir ve bozulmalara nasıl tolerans gösterebilir?
- Yarı-dürüst ve kötü niyetli güvenlik garantileri arasındaki fark nedir?
Anahtar kavramlar
- özel girdiler ve ortak çıktı
- ideal/gerçek simülasyon
- karıştırılmış devreler (garbled circuits)
- kör transfer (oblivious transfer)
- sır paylaşımı
- yarı-dürüst ve kötü niyetli düşman
- eşik kriptografisi
- özel küme kesişimi
- dürüst çoğunluk ve dürüst olmayan çoğunluk
Temel kuramlar
- İdeal/gerçek simülasyon güvenliği
- Bir MPC protokolü, bir düşmanın gerçek protokolde başarabileceği her şeyi, güvenilir bir tarafın fonksiyonu hesapladığı ideal bir dünyada da başarabilmesi durumunda güvenlidir — bu, modellenen bozulmalara karşı gizliliği ve doğruluğu garanti etmektedir.
- Karıştırılmış devreler (garbled circuits) ve sır paylaşımı
- Yao'nun karıştırılmış devreleri, bir tarafın doğruluk tablolarını şifrelemesi ve diğer tarafın körü körüne şifre çözmesiyle iki tarafın herhangi bir Boole devresini değerlendirmesine olanak tanır; sır paylaşım şemaları, girdileri taraflar arasında bölerek alt kümelerin sırları yeniden oluşturmadan kapıları ortaklaşa hesaplamasını sağlar.
Mekanizmalar
Yao'nun iki taraflı protokolünde, bir taraf her bir kapının doğruluk tablosunu şifreleyerek bir Boole devresini karıştırmakta (garbles), diğer taraf ise kör transfer (oblivious transfer) yoluyla elde edilen anahtarları kullanarak bunu değerlendirmekte ve yalnızca çıktıyı öğrenmektedir. Sır paylaşımı yaklaşımlarında (GMW, BGW, SPDZ), her girdi taraflar arasında dağıtılan paylara bölünmektedir; toplama kapıları paylar üzerinde yerel olarak hesaplanmakta ve çarpma kapıları etkileşim kullanmaktadır, ardından çıktı payları yeniden oluşturulmaktadır. Kötü niyetli güvenlik, hilekarlığı tespit etmek için sıfır bilgi ispatları veya doğrulanmış paylar eklemektedir.
Klinik önem
MPC, gizliliği koruyan işbirliği için teoriden uygulamaya geçmektedir: kurumlar, ham verileri bir araya getirmeden birleştirilmiş veri kümeleri üzerinde toplu istatistikler hesaplamaktadır (Boston cinsiyet ücret farkı çalışması), şirketler kişi tespiti ve reklam ölçümü için özel küme kesişimi yürütmektedir, eşik imzaları kripto para birimi saklama ve sertifika yetkilisi anahtarlarını korumaktadır ve güvenli toplama, gizliliği koruyan makine öğrenimini desteklemektedir.
Kanıt ve kılavuzlar
MPC, olgun açık çerçeveler (örn. MP-SPDZ) ve eşik kriptografisindeki standartlaşma çabaları (NIST'in Multi-Party Threshold Cryptography projesi) tarafından giderek daha fazla desteklenmektedir. Güvenlik garantileri, varsayılan bozulma modeline (yarı-dürüst ve kötü niyetli) ve bozulma eşiğine (dürüst çoğunluk ve dürüst olmayan çoğunluk) kritik ölçüde bağlıdır ve bunlar dağıtımın güven varsayımlarıyla eşleşmelidir.
Tarihçe
Andrew Yao, 1982-1986 yıllarında güvenli iki taraflı hesaplamayı ve karıştırılmış devre (garbled-circuit) fikrini (milyonerler problemi) tanıtmıştır. Goldreich, Micali ve Wigderson (1987), güvenli hesaplamayı herhangi bir sayıda tarafa genişletmiş ve BGW ile CCD protokolleri (1988), dürüst bir çoğunlukla bilgi-teorik güvenlik sağlamıştır. Onlarca yıllık verimlilik iyileştirmeleri (kör transfer uzantısı, SPDZ), 2010'larda MPC'yi gerçek dağıtımlar için yeterince pratik hale getirmiştir.
Öne çıkan isimler
- Andrew Yao
- Oded Goldreich
- Silvio Micali
- Avi Wigderson
- Adi Shamir
İlgili konular
Temel eserler
- yao1982
- goldreich2004
- katz2020
Sıkça sorulan sorular
- MPC, homomorfik şifrelemeden nasıl farklıdır?
- Her ikisi de özel veriler üzerinde hesaplama yapar, ancak homomorfik şifreleme tek bir tarafın okuyamadığı şifreli metinler üzerinde hesaplama yapmasına izin verirken, MPC hesaplamayı etkileşimde bulunan birkaç taraf arasında dağıtır ve hiçbir taraf girdileri tek başına göremez. Bazen birleştirilmektedirler.
- 'Yarı-dürüst' ve 'kötü niyetli' güvenlik ne anlama gelmektedir?
- Yarı-dürüst (dürüst ama meraklı) güvenlik, tarafların protokole uyduğunu ancak gördüklerinden ek bilgi öğrenmeye çalıştığını varsayar. Kötü niyetli güvenlik ise protokolden keyfi olarak sapan taraflara karşı ek koruma sağlar, bu daha güçlü ancak daha maliyetlidir.