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

Private Set Intersection

なぜ大切か 会社はしばしば、共同の特典のためや、広告が効いたかを測るために、どの顧客を共有しているかを知りたがります。簡単なのは顧客の一覧を交換することですが、それはあなたのメールがほかの会社のデータベースに入るということです。Private Set Intersection なら、どちらも自分の一覧を渡さずに重なりを見つけられます。その仕組みを知れば、本物のプライバシーと「ハッシュにしたメールしか共有していません」を見分けられます。

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

問題

店とアプリが、それぞれ顧客のメールの一覧を持っています。両方の 一覧にあるメールだけが欲しく、ほかには何も要りません。店はアプリのほかのユーザーを知ってはならず、アプリは店のほかの顧客を知ってはなりません。

集合の共通部分:2 つの一覧に共通するものです。Private Set Intersection(PSI):2 者が、それぞれの一覧についてほかに何も明かさずに、それを計算するやり方です。

なぜ「ハッシュにすればいい」は失敗するか

ハッシュ:文字を決まった長さのかき混ぜたものに変える関数です(SHA-256 がよくあるものです)。同じ入力はいつも同じ出力になり、直接逆に計算することはできません。

「ハッシュにしたメールを交換するので、誰も本物を見ない」は安全に聞こえます。でもメールは推測できます。ありそうなメールの一覧を持つ人なら誰でも、推測をすべてハッシュにして一致を探せます。大きな鍵束の鍵をすべて試すようなものです。あなたの naive_reverse 関数は、練習の世界の 200 個の合成のメールでまさにそれをします。ハッシュがデータを隠すのは入力が推測できないときだけで、メール、電話番号、名前は推測できます。

2 つの錠の手口

数学のレッスンを思い出してください。秘密の a をかけてから秘密の b をかけるのは、b から a と同じになります。それぞれのメールを箱だと思ってください。Alice は自分の箱それぞれに自分の錠をかけ、Bob に送ります。Bob は自分の錠を加えて送り返します。Bob も自分の箱に錠をかけて Alice に送り、Alice が自分の錠を加えます。これでどの箱にも両方の錠がかかり、中に同じメールが入った 2 つの箱は、どちらの錠が先でも同じに見えます。

数で言うと、watched.leg7a_privacy の練習用の群(P、hash_to_group、random_secret)を使って:

  1. Alice は blind(alice_items, a) を送ります。それぞれの項目を群へハッシュし、a で累乗したものです。
  2. Bob はそれを b で累乗し(reblind)、同じ順番で 送り返します。
  3. Bob は blind(bob_items, b) を送ります。
  4. Alice は Bob の値を a で累乗します。彼女の二重に錠をかけた値のうち、Bob の二重に錠をかけた集合に現れるものが共有の項目です。順番を保ったので、それぞれが自分のどの項目かがわかります。

ハッシュが失敗したところで、なぜこれは安全なのでしょう? 推測を試すには 両方の 秘密が要り、それぞれが自分の秘密を持っています。Bob が見るのは、Alice の秘密がかかった彼女の値だけで、それはランダムな数に見えます。

Diffie-Hellman PSI:このプロトコルの名前で、借りている 1976 年の鍵交換の考え(2 者が秘密の指数を組み合わせる)にちなみます。実際の版は楕円曲線(「順番は関係ない」という同じ性質を持ち、数がずっと短い、別の種類の群)と注意深いハッシュを使います。

答えそのものが開示である

完璧な PSI でさえ、ある特定の人が Bob の顧客だと Alice に伝えます。Bob が診療所や債務の相談者なら、それは慎重さが要る情報です。会社が必要なのは、しばしば共有している顧客が 何人 かだけです。PSI の件数版 では Bob が手順 2 で返事を混ぜるので、Alice は一致を数えられますが、それが自分のどの項目かはわかりません。問いに答える最小限を求めましょう。

ほかの言語では

BigInt を使った JavaScript での目隠しの手順(数学のレッスンにあるような powMod の補助関数を使います):

const blind = (items, secret) => items.map(x => powMod(hashToGroup(x), secret, P));
const reblind = (values, secret) => values.map(v => powMod(v, secret, P));

そして math/big を使った Go では:

func reblind(values []*big.Int, secret, p *big.Int) []*big.Int {
    out := make([]*big.Int, len(values))
    for i, v := range values {
        out[i] = new(big.Int).Exp(v, secret, p)
    }
    return out
}

実際の製品では、自分で書くのではなく、監査済みの PSI のライブラリを使ってください。

まとめ

  • ハッシュにしたメールは推測の一覧で簡単に元に戻せるので、「ハッシュしか共有していない」はプライバシーではありません。
  • Diffie-Hellman PSI は、順番が関係ない 2 つの秘密ですべての項目に二重に錠をかけるので、どちらの一覧も明かさずに一致が現れます。
  • 順番を保つとどの項目が一致するかが明かされ、混ぜる(PSI の件数版)と何個かだけが明かされます。
  • 共通部分はそれ自体が個人のデータなので、問いに答える最小限を求めましょう。
あなたの番

5 つの関数を書いてください。naive_reverse(hashes, candidates) は、SHA-256 の 16 進ダイジェスト(hashlib.sha256(c.encode()).hexdigest())が hashes にある候補を並べたリストを返します。blind(items, secret) は [pow(hash_to_group(x), secret, P) for x in items] を返します。reblind(values, secret) は順番を保ったまま、それぞれの値を P を法として secret で累乗します。psi(alice_items, bob_items, a_secret, b_secret) は blind と reblind を使ってレッスンの 4 つの手順に従い、Bob も持っている Alice の項目を並べたリストを返します。psi_cardinality(alice_items, bob_items, a_secret, b_secret, rng) は同じことをしますが、Bob の返事を rng.shuffle で混ぜ、共有の項目の数だけを返します。

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

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

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