紛失通信

Oblivious Transfer

暗号化したままテーブル引きができる。

Aliceがmでテーブル引きしたいが、mをテーブルTを持っているBobに教えたくない。

BobがEnc(m) → Enc(T(m)) を計算できる手法があれば良い

もちろんBobは Enc(m)→m できない

mを送信したい場合に、mを「m番目だけが1で残りが0のワンホットベクトル」にし、ベクトルのそれぞれの要素をEncする

Enc(0)はもちろん異なる値になる

テーブル引きはこのワンホットベクトルとの内積である。

Encが準同型暗号であれば内積を計算することができる。

10年前は掛け算ができる準同型暗号がなかった

完全準同型暗号が生まれた

それは計算が重たいので「1回だけ掛け算ができる準同型暗号」が生まれた

2次元テーブルから値を取りたい場合にどうするか

加算だけの準同型暗号では2つのインデックスを256x+yみたいに組み合わせてインデックスをつくる

可能だけど、テーブルがX * Yのサイズならメッセージの長さもX * Yになるのでコストが高い

乗算が1回できる準同型暗号では端折ることができる

2つのインデックスの積を計算することができれば「両方が1である」ところだけに1が残るから。