पाठ्यक्रम 156 में से पाठ 133 · रोकने से आगे की निजता तकनीक
रोकने से आगे की निजता तकनीक

आपको चाहिए गणित

यह क्यों मायने रखता है इस module के निजता औज़ार, जैसे सूचियाँ बदले बिना साझा ग्राहक ढूँढना या ऐसे आँकड़े प्रकाशित करना जो हर व्यक्ति की रक्षा करें, गणित के तीन छोटे टुकड़ों पर टिके हैं। आपको गणित की डिग्री नहीं चाहिए। आपको घड़ी का गणित, संयोग की समझ, और यह विचार चाहिए कि बेतरतीब शोर बड़े समूहों में कट जाता है। यह पाठ आपको ठीक वही देता है, आज़माने के लिए Python के साथ।

1. घड़ी का गणित

22:00 बजे हैं। 5 घंटे बाद क्या समय होगा? 27:00 नहीं: घड़ी घूम जाती है, इसलिए 03:00 है। आपने 22 + 5 = 27 लिया और 24 से भाग देने के बाद शेष रखा।

Modular arithmetic: गणित जहाँ संख्याएँ एक तय आकार, modulus, तक पहुँचकर घूम जाती हैं। "27 mod 24" 3 है, 27 को 24 से भाग देने के बाद का शेष। Python में शेष operator % है: 27 % 24 3 है।

घूमना संख्याओं को एक तय आकार में रखता है चाहे आप कितना भी जोड़ें या गुणा करें, जो इसे cryptography के लिए काम का बनाता है। Python में "एक घात तक उठाएँ, फिर घुमाएँ" के लिए एक तेज़ built-in भी है: pow(base, exponent, modulus)।

print((22 + 5) % 24)       # 3
print(pow(3, 4, 7))        # 3*3*3*3 = 81, and 81 % 7 = 4
print(pow(5, 200, 23))     # instant, even though 5 to the 200 is huge

2. एक तरफ़ आसान, दूसरी तरफ़ कठिन

पीले और नीले paint को मिलाकर हरा बनाना आसान है। हरे को वापस ठीक उसी पीले और नीले में अलग करना व्यावहारिक रूप से असंभव है। कुछ गणित ऐसे ही काम करता है।

एक बड़ा अभाज्य modulus P और एक संख्या h चुनें। एक गुप्त a के लिए pow(h, a, P) निकालना तुरंत होता है। पर सिर्फ़ जवाब दिए जाने पर, a फिर से ढूँढना काफ़ी बड़ी संख्याओं के लिए इतना धीमा है कि कोई नहीं कर सकता। इस एक-तरफ़ा गुण को discrete logarithm problem कहते हैं।

एक और तथ्य, और यह अगले labs को चलाता है। a तक फिर b तक उठाना वही नतीजा देता है जो b तक फिर a तक उठाना, क्योंकि दोनों h की घात a गुणा b के बराबर हैं:

P = 1019                     # a small prime: fine for learning, useless for security
h, a, b = 42, 123, 456
print(pow(pow(h, a, P), b, P) == pow(pow(h, b, P), a, P))    # True

एक डिब्बे पर दो तालों की तरह, उन्हें लगाने का क्रम मायने नहीं रखता। दो लोग हर एक अपना रहस्य जोड़कर अपने रहस्य कभी बताए बिना एक ही जगह पहुँच सकते हैं।

3. एक paragraph में प्रायिकता

एक प्रायिकता 0 (कभी नहीं) से 1 (हमेशा) तक की एक संख्या है। एक निष्पक्ष सिक्का 0.5 की प्रायिकता से heads आता है। जब दो चीज़ें स्वतंत्र हों, तो दोनों का संयोग गुणनफल है: लगातार दो heads 0.5 x 0.5 = 0.25 है। Expected value लंबे समय का औसत है: एक निष्पक्ष पासा कई बार फेंकें और औसत 3.5 के क़रीब पहुँचता है।

4. भीड़ में शोर कट जाता है

शोर: एक सच्चे मान में जानबूझकर जोड़ी एक बेतरतीब मात्रा, ताकि ठीक मान छिपा रहे। अगर शोर के ऊपर और नीचे होने की बराबर संभावना हो, तो कई मानों पर उसका औसत शून्य हो जाता है।

यह एक क्लासिक survey तरकीब है जिसे randomised response कहते हैं। आप जानना चाहते हैं कि कितने लोगों ने कुछ शर्मनाक किया है। हर व्यक्ति चुपचाप एक सिक्का उछालता है। Heads: सच जवाब दें। Tails: फिर उछालें और heads पर "हाँ" और tails पर "नहीं" जवाब दें। कोई भी अकेली "हाँ" बस सिक्का हो सकती है, इसलिए किसी का जवाब उनके बारे में कुछ साबित नहीं करता।

फिर भी भीड़ का कुल काम का है। अगर सच्चा अंश p है, तो "हाँ" जवाबों का अपेक्षित अंश 0.5 x p + 0.25 है। इसलिए अगर 35% हाँ कहें, तो p लगभग (0.35 - 0.25) / 0.5 = 0.2, यानी 20% है। भीड़ जितनी बड़ी, अनुमान उतना क़रीब, क्योंकि भीड़ बढ़ने पर बेतरतीब शोर कुल के मुक़ाबले सिकुड़ता है।

import random
rng = random.Random(1)               # seeded: the same "random" numbers every run
truth = [rng.random() < 0.2 for _ in range(10000)]   # 20% really did it
answers = []
for did_it in truth:
    if rng.random() < 0.5:
        answers.append(did_it)             # heads: tell the truth
    else:
        answers.append(rng.random() < 0.5) # tails: random yes or no
yes = sum(answers) / len(answers)
print(round((yes - 0.25) / 0.5, 3))       # close to 0.2

differential privacy में इस्तेमाल शोर, जिसे Laplace noise कहते हैं, उसी विचार का एक चिकना वर्ज़न है: आमतौर पर छोटा, कभी-कभी बड़ा, ऊपर या नीचे बराबर संभावना से। उसका scale तय करता है कि वह आमतौर पर कितना बड़ा है।

दूसरी भाषाओं में

JavaScript का % धनात्मक संख्याओं के लिए ऐसे ही काम करता है, और बड़ी संख्याएँ BigInt इस्तेमाल करती हैं (एक n के साथ लिखी)। कोई built-in modular power नहीं है, इसलिए यह मानक loop है:

function powMod(base, exp, mod) {
  let result = 1n;
  base %= mod;
  while (exp > 0n) {
    if (exp & 1n) result = (result * base) % mod;
    base = (base * base) % mod;
    exp >>= 1n;
  }
  return result;
}
console.log(powMod(3n, 4n, 7n));   // 4n

Go में, math/big से new(big.Int).Exp(base, exp, mod) वही काम करता है।

एक आम ग़लतफ़हमी

"शोर जोड़ना डेटा को बेकार बनाता है।" एक व्यक्ति के मान के लिए, हाँ, और यही मक़सद है। एक बड़े समूह के लिए, शोर ज़्यादातर कट जाता है, इसलिए कुल और औसत काम के रहते हैं। निजता तकनीक उसी अंतर में रहती है: व्यक्तियों के लिए धुंधली, भीड़ के लिए तीखी।

सार

  • Modular arithmetic संख्याओं को एक modulus के चारों ओर घुमाता है; Python % और pow(b, e, m) इस्तेमाल करता है।
  • एक गुप्त घात तक उठाना एक तरफ़ आसान है और उलटना व्यावहारिक रूप से असंभव, और दो गुप्त घातों का क्रम मायने नहीं रखता।
  • स्वतंत्र संयोग गुणा होते हैं; expected value लंबे समय का औसत है।
  • बेतरतीब शोर व्यक्तियों को छिपाता है पर बड़े समूहों में कट जाता है, जो randomised response का काम करने का तरीका है।

इस पाठ में कोई समस्या दिखी? बताएँ · इस पाठ के बारे में पूछें

यह अभ्यास जल्द खुलेगा

इससे पहले वाला पाठ पूरा करें और यह खुल जाएगा। पूरा कोर्स मुफ़्त है, कोई खाता नहीं चाहिए, और आप यह पाठ अभी पढ़ सकते हैं।