Private Set Intersection
यह क्यों मायने रखता है कंपनियाँ अक्सर जानना चाहती हैं कि वे कौन-से ग्राहक साझा करती हैं, एक साझा offer के लिए या यह मापने के लिए कि एक विज्ञापन ने काम किया या नहीं। आसान तरीका ग्राहक सूचियाँ बदलना है, जिसका मतलब है आपका email दूसरी कंपनी के database में पहुँचता है। Private Set Intersection उन्हें किसी भी पक्ष के अपनी सूची सौंपे बिना overlap ढूँढने देता है। यह कैसे काम करता है यह जानना आपको असली निजता को "हमने बस hashed emails साझा किए" से अलग पहचानने देता है।
सीखने का crypto, सुरक्षित नहीं: इस module के labs की संख्याएँ पढ़ने लायक छोटी हैं और बेतरतीबी seeded है ताकि grading दोहराने लायक हो। असली सिस्टम जाँची libraries और कहीं बड़ी संख्याएँ इस्तेमाल करते हैं। सीखने का code कभी एक product में copy न करें।
समस्या
एक दुकान और एक ऐप के पास हर एक के ग्राहक emails की एक सूची है। वे वे emails चाहते हैं जो दोनों सूचियों पर हों, और कुछ नहीं: दुकान को ऐप के दूसरे उपयोगकर्ता नहीं जानने चाहिए, और ऐप को दुकान के दूसरे ग्राहक नहीं जानने चाहिए।
Set intersection: वे चीज़ें जो दो सूचियों में साझा हैं। Private Set Intersection (PSI): दो पक्षों के लिए अपनी सूचियों के बारे में और कुछ बताए बिना उसे निकालने का एक तरीका।
"बस hash कर दो" क्यों विफल होता है
Hash: एक function जो टेक्स्ट को एक तय लंबाई की गड्डमड्ड में बदलता है (SHA-256 एक आम है)। एक ही input हमेशा एक ही output देता है, और आप उसे सीधे उल्टा नहीं चला सकते।
"हम hashed emails बदलते हैं, इसलिए कोई असली नहीं देखता" सुरक्षित लगता है। पर emails का अनुमान लगाया जा सकता है। संभावित emails की सूची रखने वाला कोई भी हर अनुमान का hash बनाकर मेल खोज सकता है, जैसे एक बड़े key ring की हर चाबी आज़माना। आपका naive_reverse function अभ्यास दुनिया के 200 synthetic emails के साथ ठीक यही करेगा। Hashing डेटा तभी छिपाता है जब inputs का अनुमान न लगाया जा सके, और emails, फ़ोन नंबर और नामों का लगाया जा सकता है।
दो-ताले की तरकीब
गणित पाठ से याद करें: गुप्त a लगाना, फिर गुप्त b, वही देता है जो b फिर a। हर email को एक डिब्बा सोचें। Alice अपने हर डिब्बे पर अपना ताला लगाकर उन्हें Bob को भेजती है। Bob अपना ताला जोड़कर उन्हें वापस भेजता है। Bob अपने डिब्बों पर भी ताला लगाकर उन्हें Alice को भेजता है, जो अपना ताला जोड़ती है। अब हर डिब्बे पर दोनों ताले हैं, और अंदर एक ही email वाले दो डिब्बे एक जैसे दिखते हैं, चाहे कोई भी ताला पहले लगा।
संख्याओं में, watched.leg7a_privacy के अभ्यास group (P, hash_to_group, random_secret) के साथ:
- Alice
blind(alice_items, a)भेजती है: हर item group में hash होकर फिरaतक उठाया। - Bob उन्हें
bतक उठाता है (reblind) और उन्हें उसी क्रम में वापस भेजता है। - Bob
blind(bob_items, b)भेजता है। - Alice Bob के मानों को
aतक उठाती है। उसके दो-ताले वाले मानों में से जो भी Bob के दो-ताले वाले set में दिखे वह एक साझा item है। क्योंकि उसने क्रम रखा, वह जानती है कि हर एक उसका कौन-सा item है।
यह सुरक्षित क्यों है जहाँ hashing विफल हुआ? एक अनुमान परखने के लिए, आपको दोनों रहस्य चाहिए, और हर पक्ष अपना रखता है। Bob कभी बस Alice के मान उसके रहस्य के साथ देखता है, जो बेतरतीब संख्याओं जैसे दिखते हैं।
Diffie-Hellman PSI: इस protocol का नाम, उस 1976 के key-exchange विचार के नाम पर जो यह उधार लेता है (दो पक्ष गुप्त घातांक मिलाते हुए)। असली वर्ज़न elliptic curves (एक अलग तरह का group, उसी "क्रम मायने नहीं रखता" गुण और बहुत छोटी संख्याओं के साथ) और सावधान hashing इस्तेमाल करते हैं।
जवाब ख़ुद एक खुलासा है
परफ़ेक्ट PSI भी Alice को बताता है कि एक ख़ास व्यक्ति Bob का ग्राहक है। अगर Bob एक clinic या एक क़र्ज़ सलाहकार है, तो यह संवेदनशील है। अक्सर एक कंपनी को बस यह चाहिए कि कितने ग्राहक साझा हैं। PSI cardinality में Bob क़दम 2 में अपना जवाब फेंटता है, ताकि Alice मेल गिन सके पर बता न सके कि वे उसके किन items के हैं। सवाल का जवाब देने वाला सबसे कम माँगें।
दूसरी भाषाओं में
BigInt के साथ JavaScript में blinding क़दम (गणित पाठ वाले जैसा एक powMod helper इस्तेमाल करते हुए):
const blind = (items, secret) => items.map(x => powMod(hashToGroup(x), secret, P));
const reblind = (values, secret) => values.map(v => powMod(v, secret, P));और math/big के साथ Go में:
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
}असली products के लिए, अपना लिखने के बजाय एक audited PSI library इस्तेमाल करें।
सार
- Hashed emails अनुमानों की एक सूची से आसानी से उलटे जा सकते हैं, इसलिए "हमने बस hashes साझा किए" निजता नहीं।
- Diffie-Hellman PSI हर item पर दो रहस्यों से दो ताले लगाता है जिनका क्रम मायने नहीं रखता, इसलिए किसी सूची के उजागर हुए बिना मेल दिखते हैं।
- क्रम रखना बताता है कि कौन-से items मेल खाते हैं; फेंटना (PSI cardinality) बस बताता है कि कितने।
- intersection ख़ुद निजी डेटा है, इसलिए सवाल का जवाब देने वाला सबसे कम माँगें।
पाँच functions लिखें। naive_reverse(hashes, candidates) उन candidates की sorted सूची लौटाता है जिनका SHA-256 hex digest (hashlib.sha256(c.encode()).hexdigest()) hashes में है। blind(items, secret) [pow(hash_to_group(x), secret, P) for x in items] लौटाता है। reblind(values, secret) हर मान को secret तक modulo P उठाता है, क्रम रखते हुए। psi(alice_items, bob_items, a_secret, b_secret) blind और reblind इस्तेमाल करते हुए पाठ के चार क़दमों का पालन करता है, और Alice के उन items की sorted सूची लौटाता है जो Bob के पास भी हैं। psi_cardinality(alice_items, bob_items, a_secret, b_secret, rng) वही करता है पर Bob के जवाब को rng.shuffle से फेंटता है और बस साझा items की संख्या लौटाता है।
इस पाठ में कोई समस्या दिखी? बताएँ · इस पाठ के बारे में पूछें
यह अभ्यास जल्द खुलेगा
इससे पहले वाला पाठ पूरा करें और यह खुल जाएगा। पूरा कोर्स मुफ़्त है, कोई खाता नहीं चाहिए, और आप यह पाठ अभी पढ़ सकते हैं।
यह ब्राउज़र learn.floati.life के लिए कुकी रोक रहा है, इसलिए यहाँ पूरे किए गए पाठ क्रम से नहीं खुल सकते। इस साइट के लिए कुकी की अनुमति दें और फिर से लोड करें।