Silabus Pelajaran 133 dari 156 · Teknologi privasi lebih dari sekadar pemblokiran
Teknologi privasi lebih dari sekadar pemblokiran

Matematika yang kamu butuhkan

Kenapa ini penting Alat privasi di modul ini, seperti mencari pelanggan yang sama tanpa bertukar daftar atau mempublikasikan statistik yang melindungi setiap orang, bergantung pada tiga bagian kecil matematika. Kamu tidak butuh gelar matematika. Kamu butuh aritmetika jam, perasaan tentang peluang, dan ide bahwa derau acak akan saling meniadakan dalam kelompok besar. Pelajaran ini memberikan hal itu tepat untukmu, dengan Python untuk dicoba.

1. Aritmatika jam

Sekarang jam 22:00. Jam berapa 5 jam kemudian? Bukan 27:00: jam berputar kembali, jadi jam 03:00. Kamu mengambil 22 + 5 = 27 dan menyimpan sisa setelah dibagi 24.

Aritmatika modular: aritmatika di mana angka berputar setelah mencapai ukuran tetap, yaitu modulus. "27 mod 24" adalah 3, sisa hasil bagi setelah membagi 27 dengan 24. Di Python operator sisa adalah %: 27 % 24 adalah 3.

Wrapping menjaga angka tetap pada ukuran tetap tidak peduli seberapa banyak kamu menambah atau mengalikan, itulah yang membuatnya berguna untuk kriptografi. Python juga punya fungsi bawaan cepat untuk "pangkatkan, lalu bungkus": 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. Gampang satu arah, susah arah lainnya

Mencampur cat kuning dan biru menjadi hijau itu mudah. Mengurai kembali hijau menjadi kuning dan biru yang tepat itu hampir mustahil. Beberapa matematika bekerja dengan cara yang sama.

Pilih modulus bilangan prima yang besar P dan sebuah angka h. Menghitung pow(h, a, P) untuk sebuah rahasia a terjadi seketika. Tapi jika hanya ada jawabannya, mencari a lagi sangat lambat untuk angka yang cukup besar sehingga tidak ada yang bisa melakukannya. Sifat satu arah ini disebut discrete logarithm problem.

Satu fakta lagi, dan ini akan berguna untuk lab berikutnya. Memangkatkan ke a lalu ke b memberikan hasil yang sama dengan memangkatkan ke b lalu ke a, karena keduanya sama dengan h pangkat a kali 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

Seperti dua kunci pada satu kotak, urutan kamu memasangnya tidak masalah. Dua orang bisa masing-masing menambahkan rahasia mereka dan berakhir di tempat yang sama tanpa pernah membocorkan rahasia mereka.

3. Probabilitas dalam satu paragraf

A probabilitas adalah angka dari 0 (tidak pernah) sampai 1 (selalu). Koin yang adil mendarat di sisi angka dengan probabilitas 0.5. Ketika dua hal bersifat independen, peluang keduanya adalah hasil kali: dua angka berturut-turut adalah 0.5 x 0.5 = 0.25. expected value adalah rata-rata jangka panjang: lempar dadu yang adil berkali-kali dan rata-ratanya mendekati 3.5.

4. Noise hilang di tengah keramaian

Noise: jumlah acak yang sengaja ditambahkan ke nilai asli, supaya nilai pastinya tersembunyi. Jika noise sama kemungkinannya untuk naik atau turun, rata-ratanya akan menjadi nol dalam banyak nilai.

Ini adalah trik survei klasik yang disebut randomised response. Kamu ingin tahu berapa banyak orang yang sudah melakukan sesuatu yang memalukan. Setiap orang secara rahasia melempar koin. Angka: jawab dengan jujur. Gambar: lempar lagi dan jawab "yes" untuk angka dan "no" untuk gambar. Setiap jawaban "yes" bisa saja hanya karena koin, jadi jawaban siapa pun tidak membuktikan apa pun tentang mereka.

Tapi total dari kerumunan masih berguna. Jika fraksi aslinya adalah p, fraksi jawaban "yes" yang kamu harapkan adalah 0.5 x p + 0.25. Jadi jika 35% bilang yes, p adalah sekitar (0.35 - 0.25) / 0.5 = 0.2, atau 20%. Semakin besar kerumunannya, semakin akurat estimasinya, karena noise acak mengecil relatif terhadap total saat kerumunan bertambah besar.

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

Noise yang digunakan dalam differential privacy, yang disebut Laplace noise, adalah versi halus dari ide yang sama: biasanya kecil, terkadang lebih besar, sama kemungkinannya untuk naik atau turun. scaleZ-nya menentukan seberapa besar ukurannya biasanya.

Di bahasa lain

%JavaScript bekerja dengan cara yang sama untuk angka positif, dan angka besar menggunakan BigInt (ditulis dengan n). Tidak ada fungsi modular power bawaan, jadi ini adalah loop standar:

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

Di Go, new(big.Int).Exp(base, exp, mod) dari math/big melakukan hal yang sama.

Kesalahpahaman umum

"Menambah noise membuat data tidak berguna." Untuk nilai satu orang, ya, dan itulah intinya. Untuk kelompok besar, noise sebagian besar saling meniadakan, jadi total dan rata-rata tetap berguna. Teknologi privasi hidup di celah itu: kabur untuk individu, tajam untuk kerumunan.

Ringkasan

  • Aritmatika modular membungkus angka ke dalam modulus; Python menggunakan % dan pow(b, e, m).
  • Menaikkan ke pangkat rahasia itu mudah dilakukan tapi hampir mustahil untuk dibalikkan, dan urutan dua pangkat rahasia tidak berpengaruh.
  • Peluang independen dikalikan; nilai harapan adalah rata-rata jangka panjang.
  • Noise acak menyembunyikan individu tapi saling menghapus dalam kelompok besar, begitulah cara kerja randomised response.

Ada masalah di pelajaran ini? Laporkan · Tanya tentang pelajaran ini

Latihan ini akan segera dibuka

Selesaikan pelajaran sebelumnya agar pelajaran ini terbuka. Seluruh kursus ini gratis, tidak butuh akun, dan kamu bisa baca pelajaran ini sekarang.