オイラがなんかのリスト、たとえば顧客のリストを持っていて、Aさんも別の顧客のリストを持っていて、お互いにリストの全貌を知られることなしに、共通する顧客のリストを作るにはどうすればいいか？単純にお互いのリストの顧客氏名をハッシュして渡すとかだと、辞書攻撃に対しては無力なので、それよりマシな方法は？というお話。
時間のある時にちゃんと読もう。
先週、友達から中古でワインセラーを譲ってもらった。フォルスターのST-98Nとかって、ディスコンになってる24本入りの奴。出張とかでドタバタしてたので、今日ようやくセットアップ。
正直24本もワインがあったら片っ端から飲んじゃうと思うので、たぶん半分ぐらいはチーズ用になるな。ワインにチーズの匂いが移らないように、デカめのタッパー買ってきて突っ込んどくか。
ヴォネガットが『タイタンの妖女』で "There is no reason why good cannot triumph as often as evil. The triumph of anything is a matter of organization. If there are such things as angels, I hope that they are organized along the lines of the Mafia." とかって書いてたっけ。浅倉訳がどんな風だったか忘れてしまったけど、「善意がしばしば悪意には勝つことができないということに理由なんてない。なんであれ勝利というのは、どのくらい組織化された努力をするかで決まるものだ。もしも天使なんてものが存在するなら、マフィアと同じくらいに組織化されているといいのだが」ってな感じかね。
Freeman, Nissim, Pinkasのアルゴリズムの基本。
1) 世の中にはhomomorphic cryptosystemとゆー便利なものがある。xを暗号化したものをEnc(x)とした時に、Enc(x),Enc(y)が分かっていればEnc(x+y)が計算できたり、任意の定数cに対してEnc(cx)やEnc(cy)が計算できる。具体的には(modified)El Gamal, Paillierなど。
2) x1,x2,...,xnというリストがあった時、P(y)=(y-x1)(y-x2)...(y-xn)=an y^n + ... + a1 y + a0 という多項式を考える。
3) Enc(a0),...,Enc(an) を相手に渡す。
4) 相手は自分の持っているリストに含まれる全ての値 y について、Enc(r P(y) + y) を計算する。rは適当な乱数。
5) もしyがx1,x2,...,xnのどれかと等しければP(y) = 0 であるから、Enc(r P(y)+y) = Enc(y) になる。
6) なので、この計算の結果を返してもらえば、どれがマッチしたかは確認できる。
……なるほど。ていうか、そゆもんがあったらいいなあと空想したことはあるのだが、実際にhomomorphic cryptosystemなんつークソ便利なものがあるのね。