Oblivious Transfer
Exchange Of Secret(EOS)問題
- EOSプロトコルの構成
- EOSプロトコルの5について
1/2で素因数分解できてしまうのはなぜか
- Rabin暗号
- 素因数分解できる理由
まとめ
参考

Oblivious Transfer

Oblivious Transfer(紛失通信)とは送信者が受信者の受け取った情報について何も得られないようなプロトコルのことを指す。ちなみにOblivious Transferには二種類の定義があって、もう一つは送信者が提示したn個のデータのうち受信者は1個の情報しか得られず、送信者は受信者がどのデータを選んだのかわからないプロトコルのことを指している。これを1-out-of-n Oblivious Transferという。なお、このプロトコルは相互変換できることが知られている。Claude Crépeauさんがそれを証明しているらしい。

Exchange Of Secret(EOS)問題

How to Exchange Secrets with Oblivious Transfer https://www.iacr.org/museum/rabin-obt/obtrans-eprint187.pdf

からの引用でOblivious Transferが必要な一例を紹介する。

ボブとアリスがある情報 $S _ A$ 、 $S _ B$ を同時に交換したいとする。

$S_A$ はボブの暗号化されたファイルを読むためのパスワードで、 $S_B$ はその逆である。
暗号化ファイルに間違ったパスワードを使うとファイルが破損するようになっている。

これはナイーブにやろうとすると難しい。アリスがボブに $S_A$ を渡した後にボブがアリスに送り返さずに逃げるかもしれないし、アリスがボブに誤った情報（例えば別データ $S$ を $S_A$ だと取り繕って）を送るかもしれない。 EOS問題のモチベーションとしては、ボブもアリスもどちらも通信において優位に立てないようにしたい。これは第三者の存在、または同時に情報をやりとりできるようなプロトコルなしには実現できなかった。

EOSプロトコルの構成

そこでOblivious Transferが活躍する。EOS問題を解決するようなEOSプロトコルが論文では登場する。まず、大前提として大きな素数p，qの積nは素因数分解の困難性を持つ。(素因数分解は出来ないという仮定)このプロトコルではパスワードを入手したことが確実なときだけアリスとボブはファイルを読もうとすることを前提にする。（理由は後述）

1　アリスは大きな素数 $p_A$ 、 $q_A$ を選んで以下を計算して、それをボブに送る。　

$n_A＝p_A q_A\$

　同様にボブは以下を計算しアリスに送る。　

$n_B＝p_B q_B\$

2　ボブは $n_A$ 以下の $x$ をランダムに選び、以下を計算して $c$ をアリスに送る。　

$c＝x^{2}\ mod n _ {A}\$

　アリスは以下を計算して $x_1$ を入手し、ボブに送る。　

$x^{2} _ {1} ＝c\ mod n_A\$

3　ボブはアリスから来た $n_A$ , $x1$ と自分で作った $x$ をもとに以下をを計算する。　

$gcd(x- x_1 ,n_A)＝d\$

　このとき、ボブは2分の1の確率で $d＝p_A$ または $d＝q_A$ を入手し、xを素因数分解できる。アリスはボブのxを知らないし、ボブが素因数分解できたのかも分からない。　ここで今度は、 $v_B$ を定義する。この値はボブがアリスの送ってきた $n_A$ を素因数分解できた時0になり、そうでない場合1になるような値である。 $v_A$ も同様に作る。ボブは以下を計算してこれをアリスに送る。　

$\epsilon_B=S_B \oplus v_B\$

　アリスからは $v_B$ が0か1か分からない（=素因数分解できたか分からない）ので、 $\epsilon_B$ から $S_B$ の情報は洩れない。

4　ここまでの処理を（Oblivious Transferと呼ぶ）をアリスとボブを逆にして行う。

5　アリスはボブに対し、[tex:E{n_A}(m_A)=C=d_A]を送る。この $d_A$ を復号するには、因数 $p_A,q_A$ を知らないといけない。これをボブも[tex:E{n_B}(m_B)=d_B]を計算しに繰り返す。

EOSプロトコルの5について

5では $d_A$ を $d_B$ 送り合っている。もしボブが $v_B=0$ 、つまり素因数分解できていたならボブは $d_A$ から $S_A$ と $m_A$ が読めたことになるが、同時にアリス側では $v_B=0$ であることになるので

$\epsilon_B=S_B \oplus 0 = S_B\\$

となり $S_B$ がアリスも $S_B$ を入手した状態になる。もし、ボブが素因数分解できていなかったなら

$\epsilon_B=S_B \oplus 1 \ne S_B\\$

となり、アリスも $S_B$ を持っていない。 つまり、ボブが読めたら、アリスも読める状態になる。どちらもファイルを同時に読めるようになり、有利不利がない。

なお、アリスに送られた $\epsilon_B$ は3/4の確率で $\epsilon_B=S_B$ である（ $ε _ B=S _ B$ じゃないのは $\epsilon _ B=0 \oplus 1 = 1$ のときだけ）。しかし、前提条件より確実に $ε_B=S_B$ ではないのでアリスはファイルを読もうとしない。万全を期したいのである。ボブがファイルを読んだという事実を知るか（ボブが通信中に逃げた場合）、 $d_B$ から $S_B$ を読むまで（ボブが通信中に逃げなかった場合）ファイルを読まない。

このプロトコルはどちらも素因数分解成功、どちらかが失敗、どちらも失敗のパターンがあるが、どちらも失敗すると秘密が交換できない。この確率は1/4である。

1/2で素因数分解できてしまうのはなぜか

そのためにはまず、この論文の参考文献にあるRabin暗号について知る必要がある。

Rabin暗号

鍵生成

大きな素数 $p,q$ （この $p$ と $q$ をブラム数という4で割って3余る素数にすると復号を簡略化できる）を計算し、 $n=pq$ を計算し、 $n$ を公開鍵、 $(p,q)$ を秘密鍵とする。

暗号化

公開鍵 $n$ を入手して、 $m\in \mathbb{Z_n^\times}$ であるような平文 $m$ を選択する。c=m² mod nを計算する。

復号

秘密鍵 $p.q$ を使って以下の方程式を計算する。

$\begin{eqnarray} \hat{m_p}=\sqrt{c}\ mod\ p\\ \hat{m_q}=\sqrt{c}\ mod\ q\\ \end{eqnarray} \\$

方程式の解は４つあり、 $(\hat{m_p},\hat{m_q})$ は $(m_p,m_q),(m_p,-m_q),(-m_p,m_q),(-m_p,-m_q)$ のどれかである。求まった解に中国人剰余定理を使うことで、4種類ある平文候補のうちどれかが求まる。これが一意復号できない（単射ではない）というRabin暗号の特徴である。

このRabin暗号を上記のプロトコルに読み替えると

手順1の $n_A＝p_A q_A$ の計算は公開鍵と秘密鍵を生成している。
手順2の $n_A$ より小さいような $x$ を選んでいるのは平文の選択で、 $c＝x^{2}\ mod n _ {A}$ はRabin暗号の暗号化である。 $c$ をアリスに送っているが、これは暗号文を通信しているのと同じである。アリスが $x^{2} _ {1} ＝c\ mod n_A$ であるような $x_1$ を選択し、ボブに送っているがこれは復号した平文を送信しているのに等しい。

素因数分解できる理由

例えば $p$ で割ると $x_p$ あまり、 $q$ で割ると $x_q$ あまる数 $x$ を $x=(x_p,x_q)$ としよう。プロトコルでは $c＝x^{2}\ mod n _ {A}$ から $c$ を計算した後、 $x^{2} _ {1} ＝c\ mod n_A$ を計算することで $x_1$ を計算しているが、 $x_1$ は $(x_p,x_q),(x_p,-x_q),(-x_p,x_q),(-x_p,-x_q)$ のどれかになる。このうち $(x_p,-x_q),(-x_p,x_q)$ のどちらかが求まるとする。この時、 $x-x_1$ を計算すると1番目を $x_1=(x_p,-x_q)$ 、２番目を $x_1=(-x_p,x_q)$ として

$\begin{eqnarray} x-x_1&=&(x_p-x_p\ \equiv\ 0\ mod\ n,x_q+x_q\ \equiv\ 2x_q\ mod\ q)\\ x-x_1&=&(x_p+x_p\ \equiv\ 2x_p\ mod\ n,x_q+x_q\ \equiv\ 0\ mod\ q)\\ \end{eqnarray} \\$

のどちらかが計算できることになる。この式から分かるように、 $x-x_1$ はpかqのどちらかで割ったときに0になる（つまり割り切れる）数であるので $gcd(x-x_1,n)$ からpかqのどちらかが求まることになる。よって $n_A$ を素因数分解できる。この確率は4つの解のうち2つで起こりうる事象なので、 $\frac{2}{4}=\frac{1}{2}$ である。