ここでは紛失通信(oblibious transfer:OT)と言われるプライバシーを実現する通信方法について簡単に説明する。RSA暗号を使った上記の英語版ウィキにあります。(自分の符号バージョンもできたら公開したいです)
ここでは楕円曲線、或いは素体上の離散対数問題を考えてプロトコルを構成してみます。
まず、紛失通信というのは以下の性質を満たすプロトコルのことです。
1.送信者は送った情報のうち、どれが届いたのか分からない
2.受信者は送られてきた情報のうち、一つの情報以外は得られない
これは一見すると何に使えるのかわかりませんが、次のような例でプライバシーを守ることができます。
TH | TH |
---|---|
TD | TD |
TD | TD |
なんか書きます |
アリスはコロナワクチンのファイザー社とモデルナ社ワクチンを用意して、$m_0$をファイザー製接種券、$m_1$をモデルナ製の接種券として、それを秘密に保護します。
アリスはボブがワクチンを選べるように、$m_0$か$m_1$の接種券との引換券である$x_0,x_1$をボブに送信します。
ボブはモデルナ社製のワクチンを打ちたいとき$x_1$を選びます。
しかしアリスにはどちらのワクチンを打ちたいのか知られたくないという状況を考えます。
以下ではエルガマル暗号を使ってOTを実現します。
アリスはエルガマル暗号の公開鍵$(g,g^k,P)$を公開しています。
ボブはモデルナがいいと思い$x_1$を選びアリスのの公開鍵$g^k$とボブの秘密鍵$a$を使い、
$c_1=x_1 \oplus g^{ak} \mod P$
として暗号化しアリスに送り返します。
ここでボブが送った暗号化された引換券を$c_b=(x_b \oplus g^{ak}) \mod P, b=(0,1)$とかくと、アリスはボブが$x_b$か$x_{1-b}$のどちらの引換券が届いたのか、$g^{ak}$によって暗号化されているので解りません。(アリスは$g^{ak}$を知らない。)
なので、アリスにとっては2つの可能性$c_b,c_{1-b}$があります。
アリスは、この2つの可能性に対して、それぞれ
$k_0=(c_b \oplus x_0)^{1/k}=({x_1} \oplus {x_0} \oplus g^{ak})^{1/k} \mod P$
$k_1=(c_b \oplus x_1)^{1/k}=({x_1} \oplus {x_1} \oplus g^{ak})^{1/k}=g^a \mod P$
を生成します。
ここでアリスはボブの暗号化された乱数$g^a$を見ているはずですが、$({x_1} \oplus {x_0} \oplus g^{ak})^{1/k}$を見ているのかも知れず、どちらが$g^a$なのか識別できません。
この時アリスを送信者とすると、
1.送信者は送った情報のうち、どれが届いたのか分からない
を満たしています。
更に、アリスは接種券$m_0,m_1$を、次のように暗号化して2つの暗号化した接種券を送信します。
$m_0'=m_0 \oplus k_0$
$m_1'=m_1 \oplus k_1$
ボブはアリスから送られてきた$m_0',m_1'$から自分の選んだ$m_1'$を$g^a$を使って、
$m_1=m_1' \oplus g^a$
と計算し、$b=1$であるモデルナの接種券$m_1$を得ます。(ボブが$b=0$を選んだときでも同じ事が言えます)
ここでなぜボブがうまく接種券を得ることができるのか考えましょう。
まずbはボブだけが知っている値です。
そしてアリスが公開しているデータ$x_b$をそれぞれアリスの公開鍵$(g,g^k)$で$x_b(g^k)^a$として暗号化しています。
そこで、$b_A$をアリスが選んだ番号、$b_B$をボブが選んだ接種券の番号とすると、
$k_b=({c_{b_B}} \oplus {x_{b_A}})^{1/k}=({x_{b_B}} \oplus {x_{b_A}} \oplus g^{a})^{1/k} \mod P$
となっています。
この時、$b_A=b_B$であるときだけデータ$x_b$がうまく打ち消し合い、$a$を知っているボブだけが$g^a$を用いて正しい接種券のデータ$m_b$が取り出せる仕組みです。
更に、ボブは残りの接種券を得ることができません。
なぜならボブはアリスの持っているもう一つの接種券$m_0$を復号しようとすると$k_0$の値を計算しなければなりません。
ここで$x_0,x_1$は公開されていますが、アリスの秘密鍵$k$を知らないため
$k_0=({c_1} \oplus {x_0})^{1/k} \mod P$
が計算できません。
なので、ボブを受信者とすると、
2.受信者は送られてきた情報のうち、一つの情報以外は得られない
ことが解ります。
修正が大変w
今日はここまで。
暗号って難しい。
参考文献