Özel Küme Kesişimi
Neden önemli Şirketler çoğu zaman, ortak bir teklif için ya da bir reklamın işe yarayıp yaramadığını ölçmek için, hangi müşterileri paylaştıklarını bilmek ister. Kolay yol müşteri listelerini takas etmektir, bu da e-postanın başka bir şirketin veritabanına düşmesi demektir. Özel Küme Kesişimi, iki tarafın da listesini vermeden örtüşmeyi bulmalarını sağlar. Nasıl çalıştığını bilmek gerçek gizliliği "yalnızca hash'lenmiş e-postaları paylaştık"tan ayırmanı sağlar.
Öğretme amaçlı kripto, güvenli değil: bu modülün laboratuvarlarındaki sayılar okunabilecek kadar küçük ve notlama tekrarlanabilir olsun diye rastgelelik tohumlanmış. Gerçek sistemler denetlenmiş kütüphaneler ve çok daha büyük sayılar kullanır. Öğretme kodunu asla bir ürüne kopyalama.
Sorun
Bir dükkânın ve bir uygulamanın her birinin bir müşteri e-postaları listesi var. İki listede de olan e-postaları istiyorlar, başka hiçbir şeyi değil: dükkân uygulamanın diğer kullanıcılarını öğrenmemeli, ve uygulama dükkânın diğer müşterilerini öğrenmemeli.
Küme kesişimi: iki listenin ortak öğeleri. Özel Küme Kesişimi (PSI): iki tarafın, listeleri hakkında başka hiçbir şey açığa çıkarmadan onu hesaplamasının bir yolu.
"Hash'le geç" neden başarısız olur
Hash: metni sabit uzunlukta bir karmaşaya çeviren bir fonksiyon (SHA-256 yaygın bir tanesidir). Aynı girdi her zaman aynı çıktıyı verir, ve onu doğrudan geriye çalıştıramazsın.
"Hash'lenmiş e-postaları takas ediyoruz, bu yüzden kimse gerçeklerini görmüyor" güvenli gibi duyulur. Ama e-postalar tahmin edilebilir. Olası e-postaların bir listesine sahip herkes her tahmini hash'leyip eşleşme arayabilir, büyük bir anahtarlıktaki her anahtarı denemek gibi. naive_reverse fonksiyonun alıştırma dünyasının 200 sentetik e-postasıyla tam olarak bunu yapacak. Hash'leme veriyi yalnızca girdiler tahmin edilemediğinde gizler, ve e-postalar, telefon numaraları ve adlar tahmin edilebilir.
İki kilit numarası
Matematik dersinden hatırla: önce gizli a'yı, sonra gizli b'yi koymak, önce b sonra a ile aynı sonucu verir. Her e-postayı bir kutu olarak düşün. Alice kutularının her birine kendi kilidini koyar ve onları Bob'a gönderir. Bob kendi kilidini ekler ve onları geri gönderir. Bob ayrıca kendi kutularını kilitler ve onları kendi kilidini ekleyen Alice'e gönderir. Artık her kutunun iki kilidi de var, ve içinde aynı e-posta olan iki kutu, hangi kilit önce takılmış olursa olsun aynı görünür.
Sayılarla, watched.leg7a_privacy'deki alıştırma grubuyla (P, hash_to_group, random_secret):
- Alice
blind(alice_items, a)'yı gönderir: her öğe gruba hash'lenir, sonraakuvvetine yükseltilir. - Bob onları
bkuvvetine yükseltir (reblind) ve aynı sırayla geri gönderir. - Bob
blind(bob_items, b)'yi gönderir. - Alice Bob'un değerlerini
akuvvetine yükseltir. Çift kilitli değerlerinden Bob'un çift kilitli kümesinde görünen her biri paylaşılan bir öğedir. Sırayı koruduğu için, her birinin kendi öğelerinden hangisi olduğunu bilir.
Hash'lemenin başarısız olduğu yerde bu neden güvenli? Bir tahmini test etmek için iki sırra da ihtiyacın var, ve her taraf kendisininkini tutar. Bob, Alice'in değerlerini yalnızca onun sırrı üzerindeyken görür, ve bunlar rastgele sayılar gibi görünür.
Diffie-Hellman PSI: bu protokolün adı, ödünç aldığı 1976 anahtar değişimi fikrinden (iki tarafın gizli üsleri birleştirmesi). Gerçek sürümler eliptik eğriler (aynı "sıra önemli değil" özelliğine ve çok daha kısa sayılara sahip farklı türde bir grup) ve dikkatli hash'leme kullanır.
Cevabın kendisi bir ifşadır
Kusursuz PSI bile Alice'e belirli bir kişinin Bob'un müşterisi olduğunu söyler. Bob bir klinik ya da bir borç danışmanıysa, bu hassastır. Bir şirketin çoğu zaman yalnızca kaç müşterinin paylaşıldığına ihtiyacı vardır. PSI kardinalitesinde Bob 2. adımda cevabını karıştırır, böylece Alice eşleşmeleri sayabilir ama kendi öğelerinden hangisine ait olduklarını söyleyemez. Soruyu cevaplayan en azını iste.
Diğer dillerde
BigInt ile JavaScript'te körleme adımı (matematik dersindeki gibi bir powMod yardımcısı kullanarak):
const blind = (items, secret) => items.map(x => powMod(hashToGroup(x), secret, P));
const reblind = (values, secret) => values.map(v => powMod(v, secret, P));Ve Go'da math/big ile:
func reblind(values []*big.Int, secret, p *big.Int) []*big.Int {
out := make([]*big.Int, len(values))
for i, v := range values {
out[i] = new(big.Int).Exp(v, secret, p)
}
return out
}Gerçek ürünler için kendininkini yazmak yerine denetlenmiş bir PSI kütüphanesi kullan.
Özet
- Hash'lenmiş e-postalar bir tahmin listesiyle kolayca tersine çevrilir, bu yüzden "yalnızca hash'leri paylaştık" gizlilik değildir.
- Diffie-Hellman PSI her öğeyi sırası önemli olmayan iki sırla çift kilitler, böylece eşleşmeler iki liste de açığa çıkmadan görünür.
- Sırayı korumak hangi öğelerin eşleştiğini açığa çıkarır; karıştırmak (PSI kardinalitesi) yalnızca kaç tane olduğunu açığa çıkarır.
- Kesişimin kendisi kişisel veridir, bu yüzden soruyu cevaplayan en azını iste.
Beş fonksiyon yaz. naive_reverse(hashes, candidates), SHA-256 hex özeti (hashlib.sha256(c.encode()).hexdigest()) hashes içinde olan adayların sıralı listesini döndürür. blind(items, secret), [pow(hash_to_group(x), secret, P) for x in items] döndürür. reblind(values, secret), sırayı koruyarak her değeri P modülo secret kuvvetine yükseltir. psi(alice_items, bob_items, a_secret, b_secret), blind ve reblind kullanarak dersin dört adımını takip eder ve Bob'un da sahip olduğu Alice'in öğelerinin sıralı listesini döndürür. psi_cardinality(alice_items, bob_items, a_secret, b_secret, rng) aynı şeyi yapar ama Bob'un cevabını rng.shuffle ile karıştırır ve sadece ortak öğelerin sayısını döndürür.
Bu derste bir sorun mu fark ettin? Bildir · Bu ders hakkında soru sor
Bu alıştırma yakında açılacak
Bu dersi bitirince bu ders açılacak. Kursun tamamı ücretsiz, hesap gerekmiyor ve bu dersi hemen şimdi okuyabilirsin.
Bu tarayıcı learn.floati.life için çerezleri engelliyor, bu yüzden burada bitirdiğin dersler sırasıyla açılamıyor. Bu site için çerezlere izin ver ve sayfayı yenile.