必要な数学
なぜ大切か このモジュールのプライバシーの道具、例えば一覧を交換せずに共通の顧客を見つけることや、一人ひとりを守る統計を公開することは、3 つの小さな数学に支えられています。数学の学位は要りません。必要なのは時計の算数、確率の感覚、そして大きな集団ではランダムなノイズが打ち消し合うという考えです。このレッスンは、まさにそれを、試せる Python と一緒に渡します。
1. 時計の算数
今は 22:00 です。5 時間後は何時ですか? 27:00 ではありません。時計は一周するので 03:00 です。22 + 5 = 27 を計算し、24 で割った余りを残したのです。
剰余算:決まった大きさ、つまり 法 に達すると数が一周する算数です。「27 mod 24」は 27 を 24 で割った余りの 3 です。Python の余りの演算子は % です:27 % 24 は 3。
一周させると、どれだけ足したり掛けたりしても数が決まった大きさに保たれ、それが暗号に役立つところです。Python には「累乗してから一周させる」ための速い組み込みもあります: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. 一方は簡単、逆は難しい
黄色と青の絵の具を混ぜて緑にするのは簡単です。緑を元のちょうどの黄色と青に分けるのは、実際には不可能です。数学にも同じように働くものがあります。
大きな素数の法 P と数 h を選びます。秘密の a について pow(h, a, P) を計算するのは一瞬です。でも答えだけから a を見つけ直すのは、数が十分大きいと遅すぎて誰にもできません。この一方向の性質を 離散対数問題 と呼びます。
もうひとつの事実が、次のラボの原動力です。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
ひとつの箱にかける 2 つの錠のように、かける順番は関係ありません。2 人がそれぞれ自分の秘密を加え、秘密を明かすことなく同じ場所に行き着けるのです。
3. 1 段落の確率
確率は 0(決してない)から 1(いつも)の数です。公平な硬貨は確率 0.5 で表が出ます。2 つのことが独立なら、両方が起こる見込みは積です。2 回続けて表は 0.5 × 0.5 = 0.25 です。期待値 は長い目で見た平均です。公平なさいころを何度も振ると、平均は 3.5 に近づきます。
4. 大勢の中ではノイズが打ち消し合う
ノイズ:正確な値を隠すため、わざと真の値に加えるランダムな量です。ノイズが上にも下にも同じくらい出るなら、多くの値の上では平均がゼロになります。
ここに、ランダム化回答 という昔ながらの調査の手法があります。恥ずかしいことをした人が何人いるか知りたいとします。それぞれの人はこっそり硬貨を投げます。表なら正直に答えます。裏なら、もう一度投げて、表なら「はい」、裏なら「いいえ」と答えます。どの「はい」も硬貨のせいかもしれないので、誰の答えもその人について何も証明しません。
それでも、大勢の合計は役に立ちます。真の割合が 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
差分プライバシーで使うノイズは ラプラスノイズ と呼ばれ、同じ考えのなめらかな版です。たいてい小さく、ときどき大きく、上にも下にも同じくらい出ます。その スケール が、ふつうどれくらいの大きさかを決めます。
ほかの言語では
JavaScript の % は正の数では同じように働き、大きな数には BigInt(n を付けて書く)を使います。組み込みの剰余の累乗はないので、これが標準のループです:
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)); // 4nGo では、math/big の new(big.Int).Exp(base, exp, mod) が同じ仕事をします。
よくある誤解
「ノイズを加えるとデータは役に立たなくなる」。ひとりの値についてはその通りで、それが目的です。大きな集団では、ノイズはほとんど打ち消し合うので、合計や平均は役に立ち続けます。プライバシーの技術はその隙間にあります。個人にはぼやけ、大勢にははっきり。
まとめ
- 剰余算は数を法のまわりで一周させます。Python では
%とpow(b, e, m)を使います。 - 秘密の累乗は一方は簡単で、元に戻すのは実際には不可能です。2 つの秘密の累乗の順番は関係ありません。
- 独立な見込みは掛け合わされます。期待値は長い目で見た平均です。
- ランダムなノイズは個人を隠しますが、大きな集団では打ち消し合います。それがランダム化回答の仕組みです。
この演習はまもなく開きます
その前のレッスンを終えると、このレッスンが解放されます。コース全体が無料でアカウントも不要、このレッスンは今すぐ読めます。
このブラウザは learn.floati.life の Cookie をブロックしているため、ここで修了したレッスンを順番どおりに開けません。このサイトの Cookie を許可して再読み込みしてください。