はじめに
この記事では、Multi-party Computation(MPC) の内部で使用されることがあるOblivious Transfer(OT) について紹介していきます。
ただし、MPCについての詳細な説明はこちらでは致しませんので、以下の記事を参照していただければと思います。
Oblivious Transfer とは、紛失通信・忘却通信とも呼ばれる通信方法であり、
「送信者が送信した2つの情報のうち、どちらを受信者が受け取ったのかを送信者が知ることができず、受信者はどちらか片方の情報しか知ることができない」という性質を持ちます。
また、2つの情報をOTによって通信する方法は1-out-of-2 OT と呼ばれ、最も基本的な型となります。そこで、この記事では1-out-of-2 OT について紹介していきます。
1-out-of-2 OT は2者間でのMPCプロトコルに使用されます。
特に、こちらの記事で紹介したYao’s Garbled Circuit のようなGarbled Circuit ベースのMPCに使用されることが多いです。
それでは、OT の具体的な仕組みを見ていきましょう。
1-out-of-2 OT の仕組み
こちらでは、最も単純な仕組みである公開鍵暗号に基づいた方法を紹介します。ただし、通信の参加者がプロトコルから逸脱しないことを前提とします。この場合、以下の仕組みで1-out-of-2 OT は実現されます。
- 送信者
- $S$
- 送信者が持つ2つの情報（$n$ ビット）
- $x_0, x_1 \in \{0, 1 \}^n$
- 受信者
- $R$
- 受信者が持つ選択ビット
- $b \in \{0,1 \}$
- 公開鍵暗号の暗号化関数
- $Enc_{公開鍵}(平文)$
- 公開鍵暗号の復号化関数
- $Dec_{秘密鍵}(暗号文)$
- $R$ が秘密鍵と公開鍵のペア$(sk, pk)$ を作成する
- $R$ はランダムな公開鍵$pk’$ を生成する
- $R$ は選択ビット$b$ に0 または1 を選ぶ
- $R$ は2つの公開鍵を$S$ に送信する
- $b=0$ のとき
- $(pk,pk’)$
- $b = 1$ のとき
- $(pk’,pk)$
- $b=0$ のとき
- $S$ は公開鍵のペア$(pk_0, pk_1)$ を受け取る
- $S$ は2つの暗号文$e_0, e_1$ を$R$ に送り返す
- $e_0 = Enc_{pk_0}(x_0)$
- $e_1 = Enc_{pk_1}(x_1)$
- $R$ は$e_0,e_1$ の片方$e_b$ を復号して情報$x_b$ を得る
- $x_b = Dec_{sk}(e_b)$
ここで、$R$ は$e_0,e_1$ のどちらか片方しか復号できません。
つまり、$S$ が送信した2つの情報のうち片方しか受け取ることができないため、受け取ることができなかった方の情報を知ることはありません。
さらに、$S$ にとってもどちらの情報を$R$ が受け取ったのかを知ることもできません。
以上のことから、1-out-of-2 OT が実現できていることが確認できました。
ただし、先にも述べたとおり、通信の参加者がプロトコルから逸脱しないという条件が必要です。
例えば、$R$ が悪意を持っており、秘密鍵と公開鍵のペアを2つ用意してしまえば、$S$ から送られてきた2つの暗号文をどちらも復号することができてしまいます。
したがって、プロトコルから逸脱する参加者がいる場合には使えないことに注意が必要です。
まとめ
この記事のまとめは以下になります。
- Oblivious Transfer は「送信者が送信した2つの情報のうち、どちらを受信者が受け取ったのかを送信者が知ることができず、受信者はどちらか片方の情報しか知ることができない」性質を持つ通信方法
- Oblivious Transfer はGarbled Circuit ベースのMPC に使用される
- 単純な1-out-of-2 OT は公開鍵暗号を用いて実現される
- 参加者はプロトコルから逸脱しないという条件が必要
