シラバス レッスン 156 中 136 · ブロックを超えるプライバシーの技術
ブロックを超えるプライバシーの技術

安全な集計

なぜ大切か フィットネスのアプリは町で歩かれた歩数の合計を知りたがり、キーボードの作り手はある言葉がすべての電話でどれだけ入力されるかを知りたがります。どちらでも、会社は多くの端末からひとつの数を必要とします。安全な集計なら、誰かひとりの値を一度も見ずにその合計を知ることができ、しかも驚くほど単純です。

教材の暗号で、安全ではありません:このモジュールのラボの数は読めるほど小さく、採点を再現できるようランダムさにシードが固定されています。実際のシステムは検証済みのライブラリと、ずっと大きな数を使います。教材のコードを製品に写さないでください。

給料の手口

3 人の友だちが、誰も自分の給料を明かさずに平均の給料を知りたいとします。1 人目は自分の給料に大きなランダムな数を足し、結果を 2 人目にささやきます。2 人目は自分の給料を足して、次にささやきます。3 人目も自分のものを足して戻します。1 人目が自分のランダムな数を引くと、合計が出てきます。どのささやきも、聞いた人にはランダムな数に見えました。

安全な集計:多くの人の値の合計(や平均)を、集めるサーバーも含めて誰にもひとつの値も明かさずに計算することです。

加法的秘密分散:秘密の数をいくつかの シェア に切り分けることです。シェアは単独ではランダムに見えますが、足すと秘密になります。どのひとつのシェアも、少なくともひとつのシェアが欠けたどの組も、秘密について何も明かしません。

シェアの仕組み

7,350 という数を 3 つのシェアに分けるには、ランダムな数を 2 つ選び、3 つの合計が 7,350 になるよう 3 つ目を選びます。一周する算数(法 M、ここでは 2 の 32 乗で、40 億を少し超える)を使うと、どのシェアも単独では一様にランダムな数です:

M = 2 ** 32
s1, s2 = 3919211450, 120775123           # random
s3 = (7350 - s1 - s2) % M                # whatever makes it add up
print((s1 + s2 + s3) % M)                # 7350

なぜ一周させるのでしょう? そうしないと、シェアがときどき負になったり、怪しいほど秘密に近くなったりします。一周させれば、秘密が何であってもどのシェアの値も同じくらいありそうなので、ひとつのシェアは何の情報も運びません。

多くの端末、いくつかのサーバー

今度はそれぞれの電話が、歩数をサーバーごとにひとつのシェアへ分け、シェア 1 をサーバー 1 に、シェア 2 をサーバー 2 に、というように送ります。それぞれのサーバーは受け取ったシェアを足し合わせます。それぞれのサーバーの合計もまだランダムに見えます。サーバーの合計を足し合わせたときに初めて、本当の町の合計が現れます。サーバーがひとつの電話の生のシェアを持ち寄らない限り、どの電話の値も決して見られません。

実世界の版

多くの電話にまたがってモデルを訓練するのに使われるシステム(連合学習 と呼ばれます)は、サーバーがひとつの、より巧みな変種を使います。端末のペアが、すべてを足すと打ち消し合うランダムなマスクに合意し、さらに途中でオフラインになる電話に対応する追加の手順があります。中心の考えは、あなたが作るものと同じです。合わせて初めて意味をなす、ランダムに見えるかけら。

安全な集計がしないこと

合計は正確に明かされます。2 人しか加わらず、ひとりが自分の値を知っていれば、それを引いてもうひとりのものを知れます。合計そのものに慎重さが要るなら、それに差分プライバシーのノイズも加えてください。2 つの道具はうまく組み合わさります。集計は入力を隠し、DP は出力へのひとりひとりの影響を隠します。

ほかの言語では

JavaScript での分け方。>>> 0 による 32 ビットの一周と、ブラウザの安全な乱数源を使います:

function split(value, n) {
  const shares = Array.from(crypto.getRandomValues(new Uint32Array(n - 1)));
  const sum = shares.reduce((a, b) => (a + b) >>> 0, 0);
  shares.push((value - sum) >>> 0);
  return shares;
}

そして Rust では、u32 の wrapping_sub が一周をしてくれます:

let last = value.wrapping_sub(shares.iter().fold(0u32, |a, &b| a.wrapping_add(b)));

まとめ

  • 安全な集計は合計を明かしますが、ひとつの寄与も明かしません。
  • 加法的秘密分散は、一周する算数を使って、値を足すとそれになるランダムに見えるシェアに分けます。
  • それぞれのサーバーはランダムに見えるシェアしか見ず、すべてのサーバーの合計を合わせて初めて答えになります。
  • 合計そのものは正確に明かされるので、合計が誰かをさらしうるときは DP のノイズと組み合わせましょう。
あなたの番

練習の世界の M(2 の 32 乗)を使って、3 つの関数を書いてください。split(value, n, rng) は n 個のシェアのリストを返します。最初の n - 1 個は rng.randrange(M) から、最後は (value - sum(shares)) % M に等しくします。combine(shares) は sum(shares) % M を返します。aggregate(values, n_servers, rng) は、それぞれの値を split で分け、シェア j を server_totals[j] に(M を法として)足し、total = combine(server_totals) である組 (total, server_totals) を返します。

このレッスンに問題を見つけましたか?報告する · このレッスンについて質問する

この演習はまもなく開きます

その前のレッスンを終えると、このレッスンが解放されます。コース全体が無料でアカウントも不要、このレッスンは今すぐ読めます。