Oblivious Transferを理解する

Oblivious Transferってなんだ

秘密計算について調べているとOblivious Transfer（OT）がよく出てきます。

日本語だと「紛失通信」あるいは「忘却送信」と呼ばれるらしいですが、日本語版のWikipediaだと詳しい内容が書かれていないので調べた内容を記しておこうと思います。

ちなみに、現在よく実用されているOTはk-out of-n OTと呼ばれるものですが、今回はその中で最もプリミティブな1-out of-2 OTについて書こうと思います。

というのも、1-out of-2 OTを拡張するとk-out of-n OTが構築できるらしい1ので、まずは1-out of-2 OTを理解しないと何も始まらないからです。

さて、1-out of-2 OTは以下のようなプロトコルです。

1. 送信者が2つのメッセージを送信する
2. 受信者はそのうち片方のみを受信することができる
3. 送信者は、受信者がどちらを受け取ったかを知ることができない

実現内容はシンプルですが、直感的に難しそうに見えます。

どうやって実現するか

Alice：送信する値の用意

まず、送信者のAliceは2つの値$m_0$と$m_1$を用意します。

これをそのままBobに送ってしまうと片方だけ読めるという要件を満たさなくなってしまうので、代わりの手段を用意する必要があります。

Alice：選択肢の提示

そこで、Aliceはメッセージの代わりに公開鍵$pk$と2つの乱数$r_0$と$r_1$を用意し、Bobに送信します。

これは特になんの意味もない乱数なので2つとも受け取ってしまっても問題ありません。
また、$pk$も公開鍵なので送ってしまって問題ありません。

$$\text{Alice} \xrightarrow{pk, r_0, r_1} \text{Bob}$$

Bob：選択の通知

さて、Bobはメッセージを選ぶ代わりに$r_0$と$r_1$のうちどちらを受け取るかを選びます。

しかし、この選択結果をそのままAliceに送ってしまうと、Aliceがどちらを受け取ったかを知ることができてしまいます。

そこで、Bobはどちらを選んだかわからないように、新たな乱数$x$を用意して、$Enc_pk(x)+r_b$をAliceに送信します^[1]。

$$\text{Bob} \xrightarrow{Enc_pk(x)+r_b} \text{Alice}$$

Alice：復号

AliceはBobから受け取った$\underline{Enc_{pk}(x)+r_b}$を復号します。

このとき、Aliceにとって未知の値となる$x$でマスクされているため、AliceはBobが$r_0$と$r_1$のうちどちらを使用したか分かりません。

そこで、Aliceは両方のケースを計算します。

$$y_0 = Dec_{sk}(\underline{Enc_{pk}(x)+r_b}-r_0) = \begin{cases} x & \text{if } r_b = r_0 \\ \perp & \text{if } r_b \neq r_0 \end{cases}$$

$$y_1 = Dec_{sk}(\underline{Enc_{pk}(x)+r_b}-r_1) = \begin{cases} x & \text{if } r_b = r_1 \\ \perp & \text{if } r_b \neq r_1 \end{cases}$$

ここで、$\perp$は復号不能を表す記号です。

このとき、Aliceは$x$の値を知らないため、$y_0$と$y_1$のどちらが$x$であるのかは判別できず、単に2つの乱数が得られただけの状態になります。

Alice：メッセージのマスクと送信

Aliceは、得られた$y_0$と$y_1$を用いて、本来送信したかった値$m_0$と$m_1$をマスクしてBobに送信します。

• $c_0 = m_0 + y_0$
• $c_1 = m_1 + y_1$

このとき$y_b = x$であるため、$c_b = m_b + x$です。

$$\text{Alice} \xrightarrow{c_0, c_1} \text{Bob}$$

Bob：復号

Bobは、Aliceから受け取った$c_0$と$c_1$から、$m_b$を復号します。

$$m_b = c_b - x$$

このとき、もう一方の値$m_{1-b}$については、

$$m_b \ne c_{1-b} - x = m_{1-b} + \perp - x$$

となり、復号不能です。

したがって、Bobが知ることができるのは片方の値のみである要件を満たします。

また、一連のやり取りの中で、AliceもBobがどちらの値を受け取ったかを知ることができず、OTの要件を満たしていることがわかります。

なぜ途中でEncryptを使ったのか

Bobは途中で新たな乱数$x$を用意して、$x+r_b$をそのまま送るのではなく、$Enc_pk(x)+r_b$をAliceに送信しました。

選んだ値をマスクするだけならば、$x+r_b$をそのまま送っても良いように思えます。実際に、この記事を書くのにOTを調べている過程で、この疑問が湧きました。

なぜ、わざわざ$Enc_pk(x)+r_b$を送る必要があるのでしょうか。

調べてみると、これはAliceに悪意があった場合、$r_0$と$r_1$の値を偏らせるなどして複数回のOTを通じてBobがどちらを選んだかを統計的に割り出すなどの攻撃を防ぐためらしいです。

であれば、$x$に選ぶ値を十分に大きくしたり、OTの回数が限られている場合であったり、偏りのある$r_0$と$r_1$を受け取った時点で拒否したりすることで回避も可能なように思いますが、たとえばGarbled circuitで$n$ビットの数を単純に比較するだけでも$n$回のOTが必要になるため、これらの回避策はあまり現実的ではないようです。

そのため、$Enc_pk(x)+r_b$を送ることで、Aliceに悪意があった場合でもBobがどちらを選んだかを知ることができないようにしているということでした。

まとめ

以上のようにして、1-out of-2 OTを実現することができました。

ちなみにこのプロトコルは、Garbled circuitの理解において非常に重要な役割を果たします。

Garbled circuitについては以下の記事で触れていますので、ぜひご覧ください。

https://zenn.dev/synschismo_inc/articles/c3988e338348d2

脚注

1. カジュアルに $Enc_{pk}(x) + r_b$ のような形で「暗号化の結果に数値を足す」操作をしていますが、これはどんな暗号方式でも可能というわけではありません。
   ここでは、加法準同型な性質を持つ公開鍵暗号を前提にしています。RSAや一般的な楕円曲線暗号（ECDSAやECDHなど）ではこのような操作は定義されておらず、本記事で紹介したプロトコルとは異なる方法でOTを実現する必要があります。