Müfredat 156 dersinden 133. · Engellemenin ötesinde gizlilik teknolojisi
Engellemenin ötesinde gizlilik teknolojisi

İhtiyacın olan matematik

Neden önemli Bu modüldeki gizlilik araçları, listeleri değiştirmeden ortak müşterileri bulmak veya her kişiyi koruyan istatistikler yayınlamak gibi işlemler, üç küçük matematik parçasına dayanır. Matematik diplomasına ihtiyacın yok. Saat aritmetiğine, şans hissine ve büyük gruplarda rastgele gürültünün birbirini yok ettiği fikrine ihtiyacın var. Bu ders sana tam olarak bunları, denemek için Python ile birlikte veriyor.

1. Saat aritmetiği

Saat 22:00. 5 saat sonra saat kaç olur? 27:00 değil: saat başa döner, yani 03:00 olur. 22 + 5 = 27 aldın ve 24'e böldükten sonra kalanı tuttun.

Modüler aritmetik: sayıların sabit bir boyuta ulaştıktan sonra başa döndüğü aritmetik, modulus. "27 mod 24" 3'tür, 27'yi 24'e böldükten sonra kalan sayıdır. Python'da kalan operatörü %: 27 % 24 3.

Wrapping, ne kadar eklersen veya çarparsan da sayıları sabit bir boyutta tutar, bu da onu kriptografi için kullanışlı kılar. Python ayrıca "üssünü al, sonra sarmala" işlemi için hızlı bir yerleşik fonksiyona sahiptir: 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. Bir yönde kolay, diğerinde zor

Sarı ve mavi boyayı karıştırıp yeşil yapmak kolaydır. Yeşili tekrar tam olarak sarı ve maviye ayırmak ise neredeyse imkansızdır. Bazı matematiksel işlemler de aynı şekilde çalışır.

Büyük bir asal modül P ve bir sayı h seç. Gizli bir a için pow(h, a, P) hesaplamak anlıktır. Ancak sadece cevabı verildiğinde, yeterince büyük sayılar için a tekrar bulmak o kadar yavaştır ki kimse bunu yapamaz. Bu tek yönlü özellik discrete logarithm problem olarak adlandırılır.

Bir gerçek daha var ve bu sonraki laboratuvarlara güç veriyor. a sonra b kuvvetine yükseltmek, b sonra a kuvvetine yükseltmekle aynı sonucu verir, çünkü her ikisi de h'nin a kuvveti çarpı b:

değerine eşittir.
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

Bir kutudaki iki kilit gibi, onları ekleme sıran önemli değil. İki kişi kendi sırlarını ekleyebilir ve sırlarını hiç açığa çıkarmadan aynı noktada buluşabilirler.

3. Bir paragrafta olasılık

A olasılığı 0 (hiçbir zaman) ile 1 (her zaman) arasında bir sayıdır. Adil bir madeni para 0.5 olasılıkla yazı gelir. İki şey bağımsız olduğunda, her ikisinin şansı çarpımdır: üst üste iki yazı 0.5 x 0.5 = 0.25 olur. beklenen değer uzun vadeli ortalamadır: adil bir zar çok kez at ve ortalama 3.5 değerine yaklaşır.

4. Gürültü kalabalıkta kaybolur

Noise: gerçek bir değere bilerek eklenen rastgele bir miktar, böylece kesin değer gizlenir. Eğer gürültü yukarı veya aşağı olma olasılığı eşitse, birçok değer üzerinde sıfıra eşitlenir.

Burada randomised response denilen klasik bir anket hilesi var. Kaç kişinin utanç verici bir şey yaptığını bilmek istiyorsun. Her kişi gizlice bir madeni para atar. Yazı: dürüstçe cevap ver. Tura: tekrar at ve yazı için "evet", tura için "hayır" cevabını ver. Herhangi bir "evet" cevabı sadece paradan kaynaklı olabilir, bu yüzden hiç kimsenin cevabı onlar hakkında bir şey kanıtlamaz.

Yine de kalabalığın toplamı hala yararlı. Eğer gerçek oran p ise, beklediğin "evet" cevaplarının oranı 0.5 x p + 0.25. Yani eğer %35'i evet derse, p yaklaşık (0.35 - 0.25) / 0.5 = 0.2 yani %20 olur. Kalabalık ne kadar büyükse tahmin o kadar yakın olur, çünkü kalabalık büyüdükçe rastgele gürültü toplama oranında küçülür.

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

Diferansiyel gizlilikte kullanılan, Laplace noise olarak adlandırılan gürültü, aynı fikrin pürüzsüz bir versiyonudur: genellikle küçük, bazen daha büyük, yukarı veya aşağı gitme olasılığı eşit. scale genellikle ne kadar büyük olacağını belirler.

Diğer dillerde

JavaScript'in % pozitif sayılar için aynı şekilde çalışır ve büyük sayılar BigInt (n ile yazılır) kullanır. Yerleşik bir modüler üs alma fonksiyonu yok, bu yüzden standart döngü şöyledir:

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'da, new(big.Int).Exp(base, exp, mod) math/big ile aynı işi yapar.

Yaygın bir yanılgı

"Gürültü eklemek veriyi işe yaramaz hale getirir." Bir kişi için evet, amaç da bu. Büyük bir grup için gürültü büyük ölçüde birbirini dengeler, bu yüzden toplamlar ve ortalamalar kullanışlı kalır. Gizlilik teknolojisi bu boşlukta yaşar: bireyler için bulanık, kalabalıklar için net.

Özet

  • Modüler aritmetik sayıları bir modül etrafında döndürür; Python % ve pow(b, e, m) kullanır.
  • Gizli bir kuvvetle yükseltmek bir yönde kolaydır ve geri döndürmek neredeyse imkansızdır, iki gizli kuvvetin sırası ise önemli değildir.
  • Bağımsız olasılıklar çarpılır; beklenen değer uzun vadeli ortalamadır.
  • Rastgele gürültü bireyleri gizler ama büyük gruplarda birbirini yok eder, rastgele yanıt yöntemi de bu şekilde çalışı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.