はじめに
この記事では秘密計算の一種である積和変換プロトコルを紹介します。まず積和変換プロトコルの概要を述べ、次にそのプロトコル内部で使われる別のプロトコルである紛失通信プロトコルについて述べます。その後積和変換プロトコルを説明し、積和変換プロトコルで正しく情報がやり取りされることの証明を述べます。
概要
互いを信頼しないアリスとボブがそれぞれ自然数\alpha, \betaを持っています。それぞれ自分の持っている値は相手に明らかにしないままx + y = \alpha\betaとなるような自然数のペア(x,y)を作り、アリスだけがxを知り、ボブだけがyを知るようにすることはできるでしょうか？自分の手の内を明かさずにRSA暗号の鍵を二人で協力しながら生成するために、このような問題が[1]で考えられました。現在このような積和変換はRSAの鍵生成のみならず、線形性を利用したい場面で広く応用されています。
紛失通信(Oblivious Transfer)プロトコルという、一見役に立たなそうなプロトコルが活躍する面白いアルゴリズムです。
紛失通信プロトコル
紛失通信プロトコルでは、送信者と受信者が登場します。送信者は二つのメッセージM_0, M_1を持ち、受信者は選択ビットb\in \{0,1\}を持っています。受信者はbを決めてから送信者にM_bを要求しますが
1) 受信者が送信者にbを教えることはなく
2) 送信者が受信者にM_{1-b}を教えることもありません。
プロトコルが正常に完了すると、送信者は何も新しい情報を得られず、受信者はM_bのみを情報として得た状態になります。
様々な実現方法がありますが、今回は[2]の公開鍵暗号を利用するものを使います。
プロトコル
送信者が送信するメッセージはM_0, M_1のどちらかであるとする。
送信者:
秘密鍵と公開鍵のペア(sk,pk)を生成し、pkとランダムな数m_0,m_1を受信者に送る。
受信者:
b\in \{0,1\}を選び、ランダムな数kを生成する。その後送信者にq = Enc(pk,k)\oplus m_bを送る。
送信者:
k'_0 = Dec(sk, q \oplus m_0), k'_1 = Dec(sk, q \oplus m_1)を計算し、(M_0\oplus k'_0, M_1\oplus k'_1)を受信者に送る。
受信者:
(M_b\oplus k'_b) \oplus k = M_bを得る。
積和変換
以上のような紛失通信プロトコルを使って、積を和として表現し直すプロトコル(Multiplication to Addition, MtA)を考えてみます。ポイントは、紛失通信プロトコルにおける受信者の選択ビットを並列化することで、受信者の持つ数の二進数表現として見ることができるということです。
以下ではアリスを受信者、ボブを送信者として説明します。積和変換の入出力(入力: \alpha, \beta、出力: x,y)を見ると二者は対等ですが、内部で使われる紛失通信プロトコルでは非対称な関係です。つまり、大枠で見た時、積和変換ではx+y = y+xと\alpha\cdot\beta=\beta\cdot\alphaは対称性のある変数になっていますが、内部の紛失通信プロトコルでは送信者と受信者という、異なる役割になるということです。
実は、以下で説明する積和変換プロトコルは安全ではありません。例えばボブが生成した乱数が本当に乱数であるという保証はどこにもありません。これを保証するためには、相関ランダム化紛失通信プロトコル(Correlated Randomized Oblivious Transfer)を使う必要があります。つまり、ボブが用意する二つの乱数の組は、差分だけボブの自由にすることができて、値はランダムであることがランダムオラクル仮定の下で検証できなければなりません。今回は簡単のために、ボブが正直に乱数を生成する方式で説明します。
以下では自然数の積和変換を考えますが、任意の環に対して適用できます。また、合同算術を適用しても関係は保存されます。
プロトコル
アリスが\alpha\in\mathbb{Z}_pボブが\beta\in\mathbb{Z}_pを持つとする。r = log(p)として、アリスは\alphaを二進数表現\alpha = \alpha_{r-1}\alpha_{r-2}...\alpha_{0}で表現する。ここでi=0,...,r-1に対して\alpha_i\in\{0,1\}。アリスとボブは出力としてそれぞれx,yを得る。
アリスは\alpha_i\in\{0,1\}をr回の紛失通信プロトコルのうちi回目での入力とする。
ボブは乱数s_0,...,s_{r-1}をランダムに選び、(t^0_i,t^1_i) = (s_i, 2^i \beta + s_i)をr回の紛失通信プロトコルのうちi回目での入力とする。
紛失通信プロトコルをr回(並列に)行い、以下のような出力を得る。
アリスは乱数の列t^{\alpha_0}_0,...,t^{\alpha_{r-1}}_{r-1} を得る。
ボブが送信したことになるメッセージは乱数のペアの列(t^0_0,t^1_0),...,(t^0_{r-1},t^1_{r-1})になる。
アリスの出力はx = \sum^{r-1}_{i=0} t^{\alpha_i}_i になる。
ボブの出力はy = -\sum^{r-1}_{i=0} s_iになる。
x+y=αβの証明
x + y = \sum^{r-1}_{i=0} t^{\alpha_i}_i -\sum^{r-1}_{i=0} s_i = \sum^{r-1}_{i=0} \alpha_i \cdot 2^i \beta = \alpha\beta
まとめ
暗号プロトコルを設計する上で、線形性が成り立つと便利なことがあります。具体的にはシュノア署名[3]などが扱いやすいのは線形性が成り立つからです。しかし、ビットコインの署名で使われるECDSAなど線形性が成り立たない暗号プロトコルもあリます。積和変換を巧妙に使うことでこの線形性が成り立たないプロトコルに無理やり線形性を導入できることがあるので、暗号プロトコルを設計したければ覚えておいて損はないでしょう。
参考文献
[1] http://www.bgu.ac.il/~gilboan/publications/rsa280599.pdf
[2] https://sehermitage.web.fc2.com/cryptech/crypto_protocol.html
[3] https://blog.visvirial.com/articles/721
