忘却通信（Oblivious Transfer）

解きたい問題：「選んだことを隠して選ぶ」

二者間のやり取りには、素朴な暗号だけでは解けない矛盾があります。データベースから 1 レコードだけ取り出したいが、どのレコードを引いたかをサーバーに知られたくない。一方サーバーは、要求された 1 件以外を渡したくない。あるいは秘密計算で、受信者が自分の入力ビットに対応する値だけを受け取りたいが、入力ビットそのものは相手に見せられない。この「選択の事実を秘匿したまま、選んだものだけを得る」という一見矛盾した要求を満たすのが 忘却通信（Oblivious Transfer, OT） です。

OT の起源は 1981 年に Rabin が提案した「確率 1/2 でメッセージを丸ごと受け取れるか、何も受け取れないか」という all-or-nothing 型の忘却通信です。以下で扱う 1-out-of-2 OT はその後 1985 年に Even・Goldreich・Lempel が定式化した形で、現在はこちらが標準的な OT の定義として使われます（両者は Crépeau により計算量的に等価であることが示されています）。重要なのは、OT が**完全性が高い（complete）**プリミティブである点です。OT さえあれば、追加の暗号学的仮定なしに任意の二者間安全計算が構成できることが知られています。つまり OT は秘密計算の「最小部品」であり、準同型暗号と秘密計算（MPC） の Garbled Circuit や GMW プロトコルは、いずれも OT を土台に成立しています。

1-out-of-2 OT の定義

最も基本的な形が 1-out-of-2 OT（記号で 1-2 OT）です。登場人物は二者だけです。

送信者 (Sender):   2 つのメッセージ m0, m1 を持つ
受信者 (Receiver): 選択ビット b ∈ {0, 1} を持つ

プロトコル実行後:
  受信者は m_b を得る
  受信者は m_(1-b) について何も学ばない  … 送信者プライバシー
  送信者は b が 0 だったか 1 だったか知らない … 受信者プライバシー

満たすべき安全性は二方向に対称です。受信者プライバシーは、送信者が受信者の選択 b を推測できないこと。送信者プライバシーは、受信者が受け取った m_b 以外のメッセージ（選ばなかった側 m_(1-b)）を一切学べないこと。この両方が同時に成り立つ点が OT の核心で、通常の暗号通信では実現できません。

これを一般化した 1-out-of-n OT では n 個のメッセージから 1 つを、k-out-of-n OT では n 個から k 個を、同様の秘匿性のもとで選びます。1-2 OT があれば 1-n OT も構成できるため、理論では 1-2 OT を基本単位として扱います。

公開鍵からの構成：一方だけ復号できる鍵を送る

OT は公開鍵暗号の一方向性から構成できます。発想は「受信者が、選んだ側のメッセージだけを復号できる状況を作る」ことです。Bellare–Micali や Naor–Pinkas による DH ベースの構成を、Diffie-Hellman の記法で示します。素数位数 q の群、生成元 g、そして送信者が固定する公開値 C（対応する離散対数を誰も知らない要素）を共有しておきます。

受信者 (選択 b):
  秘密鍵 k をランダムに選ぶ
  PK_b = g^k     を自分の選ぶ側の公開鍵とする
  PK_(1-b) = C / g^k  をもう一方の公開鍵とする
  → 送信者へ (PK_0, PK_1) を送る

  ここで PK_0 * PK_1 = C が常に成り立つ。
  受信者は PK_b の秘密鍵 k を知るが、
  PK_(1-b) の離散対数を知るには C の離散対数が要る → 知り得ない

送信者は受け取った 2 つの公開鍵が「PK_0 * PK_1 = C」を満たすことだけ検証できます。どちらが本物の鍵か（＝b がどちらか）は判別できません。送信者は各メッセージを対応する公開鍵で暗号化して両方返します。

送信者:
  受け取った PK_0, PK_1 が PK_0 * PK_1 = C を満たすか検証
  E_0 = Enc(PK_0, m0)   を計算
  E_1 = Enc(PK_1, m1)   を計算
  → (E_0, E_1) を受信者へ返す

受信者:
  自分が秘密鍵 k を知るのは PK_b 側だけ
  → E_b だけ復号でき m_b を得る
  → E_(1-b) は復号鍵がなく m_(1-b) は学べない

これで両方の安全性が成立します。受信者は片側の秘密鍵しか持たないので選ばなかったメッセージは読めず（送信者プライバシー）、送信者は 2 つの公開鍵の見分けがつかないので選択を知れません（受信者プライバシー）。同様の構成は RSA の落とし戸一方向性を使っても実現でき、いずれも「一方向性を持つ公開鍵仮定」が土台です。

OT 拡張：少数のベース OT を対称鍵で増幅する

OT の理論的な力は絶大ですが、素朴に使うとメッセージ 1 組ごとに公開鍵演算（べき乗剰余など）が要るのが実務上の壁でした。Garbled Circuit や GMW では回路の入力ビット数だけ OT が必要で、大規模計算では数百万回に達します。公開鍵演算を毎回行えば到底実用になりません。

これを解決するのが OT 拡張（OT extension） で、決定版が 2003 年の IKNP プロトコルです。核心は次の分業です。

IKNP の巧妙な点は、ベース OT の役割を送信者と受信者で入れ替えることにあります。まず 128 本程度のベース OT を、後の本番とは逆向き（受信者が送信者役）に実行して、両者の間に相関した乱数のブロックを作ります。以降はそのブロックとハッシュ関数だけを使い、対称鍵演算のコストで任意個数の OT を量産します。1 回の重い立ち上げさえ済ませれば、追加の OT は事実上ハッシュ 1 回分の値段になります。

直感（本番で m0, m1 を大量に渡したい場合）:
  1. ベース OT を 128 回だけ実行（役割を反転）
     → 送信者と受信者が「相関した秘密の行列」を共有する
  2. 受信者は自分の選択ビット列に応じて行列の一部を確定
  3. 送信者は行列の各行をハッシュして 2 つのマスクを作り、
     m0, m1 をそれぞれのマスクで隠して送る
  4. 受信者は自分の選んだ側のマスクだけ再現でき m_b を復元
     → 選ばなかった側のマスクは復元不能（送信者プライバシー）

この「少数のベース OT を対称鍵演算で増幅する」構造のおかげで、MPC は実用速度に到達しました。以降、Correlated OT / Random OT など目的特化の変種や、通信量を圧縮する Silent OT（PCG ベース） といった改良が続いており、現代の秘密計算エンジンはほぼ例外なく OT 拡張を内蔵しています。

OT が支える秘密計算

OT がなぜ「秘密計算の基本部品」と呼ばれるかは、二者間計算の各方式で入力受け渡しを担う点に表れます。

• Garbled Circuit（Yao）：評価者（Evaluator）は自分の入力ビットに対応するワイヤラベルを回路作成者（Garbler）から受け取る必要があります。ここで Garbler に入力ビットを知られてはならず、評価者は要求した側のラベルだけを得なければならない。まさに 1-2 OT の出番で、選択ビット＝入力ビット、m0/m1＝そのワイヤの 0/1 ラベルに対応します。
• GMW プロトコル：ブール回路を秘密分散のシェア上で評価する方式で、AND ゲートの計算に OT（特に Correlated OT）を用います。回路の乗算（AND）段数に比例して OT が必要になるため、OT 拡張の高速化が全体性能を左右します。
• Private Set Intersection（PSI）や秘匿検索：二者が持つ集合の共通要素だけを求める PSI の多くの構成は OT を基盤にします。関連する暗号化データ上の検索技術は 検索可能暗号 も参照してください。

まとめ

忘却通信（Oblivious Transfer, OT）は、「選んだことを相手に隠したまま、選んだものだけを受け取る」という二者間の根本的な要求を満たすプリミティブです。基本形の 1-out-of-2 OT は、送信者の 2 メッセージ m0/m1 から受信者が選択ビット b で m_b だけを得るもので、受信者プライバシー（選択の秘匿）と送信者プライバシー（非選択メッセージの秘匿）を対称に満たします。

構成は公開鍵の一方向性から可能で、受信者が「一方だけ復号鍵を知る公開鍵ペア」を送り、送信者が各メッセージを対応鍵で暗号化して両方返す、という DH・RSA ベースの方式が典型です。素朴な形は semi-honest モデル向けで、malicious 耐性には検証の追加が要ります。公開鍵演算の重さは **OT 拡張（IKNP）**が解決し、セキュリティパラメータ分の少数のベース OT を種に、以降は対称鍵演算だけで任意個の OT を量産できます。OT は二者間安全計算に対して complete であり、準同型暗号と秘密計算（MPC） の Garbled Circuit・GMW・PSI といった技術すべての土台として働きます。証明の正しさだけを示す関連技術は ゼロ知識証明 と併せて押さえると、プライバシー保護計算の全体像がつかめます。