Vitalik: Garbled devrelere hızlı bir giriş
Not: Orijinal yazar, Ethereum'un kurucu ortağı Vitalik Buterin'dir.
Bu makaleyi incelediği için Dankrad Feist'e özel teşekkürler.
Bozuk devreler çok eski ve çok basit bir kriptografik ilkeldir. Muhtemelen genel amaçlı "çok partili hesaplamanın" (MPC) en basit şeklidirler.
Aşağıdakiler programın genel ayarlarıdır:
Alice ve Bob'un yanlış bilgi göndermesini ve birbirlerine yanlış cevaplar vermesini önlemek için düzeni korumak için ek kriptografik kapsülleme kullanılabilir. Basitlik uğruna, bu konuları tartışmayacağız, ancak "ZK-SNARK'ı her şeyi kapsamak" ın etkili çözümlerden biri olduğu söylenebilir (oldukça zahmetli ve yetersiz!).
Temel plan nasıl çalışır? Devre ile başlayalım:
Bu en basit devre örneğidir Aslında bir şey yapar: iki bitlik bir toplayıcıdır. İkili biçimde iki basamak girer, her bir basamak iki basamaklıdır ve üç basamaklı bir ikili basamak (yani toplam) çıkarır.
Şimdi devreyi şifreleyelim. İlk olarak, her girdi için rastgele iki "etiket" (256 bitlik sayılar) oluştururuz: biri girdinin 0 olduğunu, diğeri girdinin 1 olduğunu gösterir. Ardından, çıktı satırı hariç her ara satır için aynısını yapıyoruz. Bu verilerin, Alice'in Bob'a gönderdiği "şaşırtma" nın bir parçası olmadığını unutmayın; şimdiye kadar, bu sadece kurulumdur.
Şimdi devredeki her bir kapı için aşağıdaki işlemleri gerçekleştiriyoruz. Her girdi kombinasyonu için, Alice (Alice) tarafından Bob'a sağlanan "gizleme" ye çıktı etiketini dahil ederiz (veya çıktı etiketi "son" çıktıysa, o zaman doğrudan çıktı), etiket Bu çıktıya neden olan giriş etiketleri birlikte karma hale getirilir ve üretilen anahtar şifrelenir. Basitlik açısından, şifreleme algoritmamız enc (out, in1, in2) = out + hash (k, in1, in2) olabilir, burada k kapının indeksidir (bu devredeki ilk kapıdır, ikincisi ,Üçüncü?). Bu iki girişin etiketlerini biliyorsanız ve karışıklık duyuyorsanız, karşılık gelen çıktıların etiketlerini öğrenebilirsiniz, çünkü yalnızca karşılık gelen karmayı hesaplamanız ve çıkarmanız gerekir.
Bu, ilk XOR geçidinin çarpışmasıdır:
Lütfen doğrudan 0 ve 1'i (şifrelenmiş biçim) dahil ettiğimize dikkat edin, çünkü bu XOR geçidinin çıktısı doğrudan programın son çıktısıdır. Şimdi en soldaki AND kapısına bir göz atalım:
Burada, kapının çıktısı yalnızca diğer geçitlerin girişi olarak kullanılır, bu nedenle değerlendiricideki bu orta bitleri gizlemek için bitler yerine etiketleri kullanırız.
Alice'in Bob'a sağlayacağı karışıklık, her kapının üçüncü sütunundaki her şeydir ve her kapının sıraları yeniden sıralanır (belirli bir satırın herhangi bir satıra karşılık gelip gelmediğini göstermekten kaçınmak için) Arka arkaya 0 veya 1). Bob'un her bir geçidin hangi değerin şifresini çözeceğini anlamasına yardımcı olmak için, belirli bir sıra kullanacağız: her kapı için, ilk satır iki çift sayılı giriş etiketi olan bir satır olur ve ikinci satır ikinci satırdır Etiketler tuhaf, üçüncü satırdaki ilk etiket tuhaf ve dördüncü satırdaki iki etiket de tuhaf (kasıtlı olarak önceki etiketi seçiyoruz, böylece her bir kapının bir çıktıda bir çift etiketi ve diğer çıktı Garip etiketlerle). Devredeki diğer tüm geçitleri aynı şekilde gizleriz.
Kısacası, Alice, devredeki her kapı için Bob'a yaklaşık 256 bitlik dört sayı gönderir. 4'ün optimal değerden uzak olduğu ortaya çıktı; AND geçitlerinin sayısının 3'e veya hatta 2'ye nasıl düşürüleceği ve XOR geçitlerinin sayısının sıfıra nasıl indirileceği için, burada bazı optimizasyonlara bakın. Lütfen bu optimizasyonların toplama ve çıkarma yerine XOR kullanarak belirli değişikliklere dayandığını, ancak bunun güvenlik nedenleriyle yapılması gerektiğini unutmayın.
Bob devreyi aldığında, Alice'den girişine karşılık gelen bir etiket ister ve Alice'i göndermek için "1/2 sersemlemiş iletim" adlı bir protokol kullanır. Alice'e girdisinin ne olduğunu açıklamadan, girdisine karşılık gelen etiketi sorar. Daha sonra devredeki kapılardan birer birer geçerek her bir ara kapının çıkış hatlarını ortaya çıkarır.
Alice'in girişinin iki sol kablo olduğunu ve (0, 1) verdiğini ve Bob'un girişinin iki sağ kablo olduğunu ve (1, 1) verdiğini varsayalım. Bu yine etiketli devredir:
O zaman Bob çıktıyı biliyor: 101. İkili durumda, 10 + 11 aslında 101'e eşittir (devrede, giriş ve çıkış bitleri en küçüğünden en büyüğüne sırayla verilmiştir, bu nedenle Alicein girişi 10 devrede (0, 1 ) Nedeni), bu yüzden işe yaradı!
Gizleme devresinde toplama işleminin anlamsız olduğunu lütfen unutmayın, çünkü 101'i bilen Bob kendi girdisini çıkarabilir ve 101-11 = 10 (Alice'in girdisi) elde edebilir, böylece gizliliği bozabilir. . Bununla birlikte, genel olarak, gizleme devreleri geri döndürülemez hesaplamalar için kullanılabilir, bu nedenle gizliliği bu şekilde bozmayın (örneğin, insanlar Alicein girdisinin ve Bobun girdisinin kendi kişisel testleri olduğu bir hesaplama düşünebilir. Cevap ve çıktı, algoritmanın uyumlu olup olmadıklarını belirleyen bir bittir; ve bu bitin bilgisi, Alice ve Bob'un birbirlerinin kişisel test cevaplarını bilmesine izin vermeyecektir.
1-of-2 habersiz transfer
Şimdi Bob'un Alice'ten kendi girdisine karşılık gelen etiketi elde etmek için kullandığı teknik olan 1/2 ihmal edilen transfer hakkında daha fazla konuşalım. Sorun şudur: Bob'un ilk giriş bitine odaklanıldığında (ikinci giriş biti için algoritma aynıdır), Alice'in 0'a (6529) karşılık gelen ve 1'e karşılık gelen bir etiketi vardır. (4872) etiketi. Bob istediği giriş bitine sahiptir: 1. Bob, Alice'in giriş bitinin 1 olduğunu bilmesine izin vermeden doğru etiketi (4872) öğrenmek ister. Önemsiz çözüm (Alice, Bob'a yalnızca 6529 ve 4872'yi gönderir) çalışmaz, çünkü Alice yalnızca iki giriş etiketinden birini bırakmak ister. Bob aynı anda iki giriş etiketini alırsa, Alice'in vazgeçmek istemediği verileri sızdırabilir.
İşte eliptik eğrileri kullanan basit bir protokol:
Bu sorunu çözer Bob, girdi bitlerine dayalı olarak iki satır etiketinden (6529 veya 4872) birini öğrenir, ancak Alice, Bob'un hangi etiketi öğrendiğini bilmez.
Uygulama alanı
Bozuk devrelerin, yalnızca 2'ye 2 hesaplama değil, birçok uygulama için potansiyel kullanımları vardır. Örneğin, bunları, herhangi bir sayıda katılımcının girdi sağladığı, sabit sayıda etkileşimde çalıştırılabilen herhangi bir karmaşıklığın çok taraflı hesaplamalarını gerçekleştirmek için kullanabilirsiniz. Bir gizleme devresinin üretimi tamamen paraleldir ve aynı anda birden fazla gizleme geçidi gerçekleştirebilirsiniz.
Bu nedenle, birçok katılımcının devredeki tüm kapıların çarpışmasını hesapladığı ve girişlerine karşılık gelen etiketleri yayınladığı büyük ölçekli çok partili hesaplamaları kolayca gerçekleştirebilirsiniz. Etiketin kendisi rastgeledir, bu nedenle girdi hakkında herhangi bir bilgi açığa çıkarmaz, ancak herkes yayınlanan gizleme devresini çalıştırabilir ve "temizlemede" çıktıyı öğrenebilir. Bir bileşen olarak bozulmayı kullanan MPC protokolünün en son örnekleri için lütfen buraya bakın.
Çok partili hesaplama tek uygulama ortamı değildir.Bu durumda, hesaplamayı paralel işlem parçalarına ayırma teknolojisi gizli veriler üzerinde çalışabilir ve ardından açıkça çalıştırılabilen sıralı parçalar gerçekleştirebilir. Bu yararlıdır. Bunu başarmak için tek yöntem kafa karıştırıcı devreler değildir. Genel olarak konuşursak, rastgele kodlama ile ilgili literatür çok daha karmaşık teknikleri içerir.Bu matematiğin dalı, şifreleme ve gizleme gibi işlevlerde de yararlıdır.
