MPC Problemi ve Yao'nun Karıştırılmış Devreleri

MPC, her biri özel x_i girdisini elinde bulunduran n tarafın, girdilerini birbirlerine açıklamadan birlikte f(x_1,...,x_n) hesaplamasına olanak tanır; bu, hesaplamayı güvenilir bir üçüncü taraf yapıyormuş gibidir.

Yao'nun 1982 tarihli Milyonerler Problemi: Alice ve Bob, servetlerini açıklamadan hangisinin daha zengin olduğunu öğrenmek ister. Güvenilir bir üçüncü taraf yoktur. MPC bu problemi kriptografik güvencelerle çözer.

1. Gizlilik: taraflar yalnızca çıktıyı ve bundan çıkarabilecekleri bilgileri öğrenir. 2. Doğruluk: bazı taraflar kötü niyetli olsa bile çıktı doğrudur. 3. Yarı dürüst ve kötü niyetli saldırganlara yönelik farklı türler vardır.

Her işlev bir Boole devresiyle (AND, XOR, NOT kapıları) ifade edilebilir. MPC protokolleri genellikle devre düzeyinde çalışır ve her kapıyı güvenli biçimde değerlendirir.

Alice (devre oluşturucu), her tel için biri 0, diğeri 1 olmak üzere iki rastgele etiket atar. Her kapının doğruluk tablosunu giriş teli etiketleriyle şifreler. Bob (değerlendirici), girdileri için gereken etiketleri yalnızca Oblivious Transfer aracılığıyla öğrenir.

Bob, karıştırılmış tabloları alır (her AND kapısı için 4 şifreleme). Giriş etiketlerini kullanarak tam olarak bir satırın şifresini çözer ve 0'ı mı yoksa 1'i mi temsil ettiğini öğrenmeden çıktı etiketini elde eder.

Her etikete rastgele bir "seçim biti" ekleyin. Bob, dört şifrelemenin tümünü denemek yerine doğru karıştırılmış satırı O(1) sürede bulmak için seçim bitlerini kullanır. Hesaplama maliyetini 4 kat azaltır.

Kolesnikov ve Schneider (2008): küresel bir Δ ofseti seçin. Ardından her tel için label_1 = label_0 ⊕ Δ olur. XOR kapıları ücretsiz hâle gelir (şifreleme gerekmez) ve bant genişliğinden yaklaşık %30 tasarruf sağlanır.

Zahur ve diğerleri (2015): her AND kapısı yalnızca 2 şifreli metin gerektirir (önceden 4'tü). Free-XOR ile birlikte kullanıldığında standart karıştırılmış devrelerin bant genişliğini yarıya indirir.

Klasik karıştırılmış devreler 2 taraflıdır. Çok taraflı uzantılar (ör. BMR protokolü), karıştırma işlemini tüm taraflar arasında paralelleştirir ancak O(n²) iletişim gerektirir. Küçük n için pratiktir.

Yao'nun karıştırılmış devre protokolünde Bob, özel giriş bitlerine karşılık gelen tel etiketlerini nasıl elde eder?

MPC, tarafların girdilerini açıklamadan birlikte hesaplama yapmasını sağlar. Karıştırılmış devreler, Boole işlevlerini şifrelenmiş doğruluk tabloları olarak kodlar. Optimizasyonlar (Free-XOR, Yarım Kapılar, Nokta ve Permütasyon) bu devreleri kullanılabilir hâle getirir. OT, Bob'un giriş etiketlerini gizli biçimde sağlar.