秘匿マルチパーティ計算

紛失通信

Takami Torao #OT
  • このエントリーをはてなブックマークに追加

概要

紛失通信 (oblivious transfer; OT) は送信者の送信する \(n\) 個のデータのうち受信者が \(k\) 個を受信できる二者間の通信プロトコル。ここで送信者は \(n\) 個のうちのどの \(k\) 個が受信されたかを知ることができず、受信者は \(k\) 個以外のデータを知ることができないという暗号論的な性質を持つ。最も単純なケースは \(n=2\), \(k=1\) の設定の 1-out-of-2 紛失通信である (1-out-of-2 紛失通信を使って任意の \(k\)-out-of-\(n\) 紛失通信を構築できることが証明されている)。また紛失通信は他の暗号技術の基盤として使われることが多く、応用は秘匿マルチパーティ計算、秘匿情報検索、秘匿共通集合、秘匿位置情報サービスなど多岐にわたる。

暗号理論での oblivious とは、一方が送ったデータを知ることなく、他方が暗号理論的な計算を行うプロトコルを表す。

Table of Contents

  1. 概要
  2. 単純な 1-out-of-2 紛失通信プロトコル
    1. 例 1: 2-way
    2. 例 2: 3-way
  3. 非インタラクティブ紛失転送
    1. \((n-1)\)-out-of-\(n\) 紛失転送への拡張
  4. 参考文献

単純な 1-out-of-2 紛失通信プロトコル

送信者の Alice は 2 つのデータ \(M_0\) と \(M_1\) を持っており、受信者の Bob は \(M_b\) をデータを必要としている。ただし Bob は Alice にどちらのデータを必要としているか (つまり \(b\)) を知られたくなく、また Alice は必要ではない方のデータ \(M_\bar{b}\) を Bob に知られたくないと思っている。ここで \(b\) でない方の 0/1 をビット反転 \(\bar{b}=1-b\) で表す。

例 1: 2-way

文献 [1] の例は Alice と Bob の双方が不正を行わないという前提で機能する。

  1. Bob: 公開鍵ペア \((S_b, P_b)\) と、公開鍵と同じサイズだが完全にランダムなビットで構成された偽の公開鍵 \(P_{\bar{b}}\) を生成し、\((P_b, P_\bar{b})\) を Alice に送信する。

  2. Alice: \(M_0\) と \(M_1\) をそれぞれ対応する \(P_b\), \(P_\bar{b}\) で暗号化した \(({\rm Enc}_0(M_0), {\rm Enc}_1(M_1))\) を Bob に送信する。

  3. Bob: \({\rm Enc}_b(M_b)\) を秘密鍵 \(S_b\) で復号化してデータ \(M_b\) を得る。このとき Alice は Bob がどちらのデータを入手したかを知るすべがないことに注意。

この例では Alice は \(M_0=M_1\) とすれば \(b\) の値によらず Bob が入手した情報を特定することができる点に注意。このため追加でゼロ知識証明などの技術を導入して \(M_0\ne M_1\) であることを証明するスキームが必要になるだろう。また Bob が 2 つの公開鍵ペアを用意して \(M_0\) と \(M_1\) の両方を入手することも容易である。

例 2: 3-way

文献 [2] の例は Bob が両方のデータを入手できないプロトコルになっている。

  1. Alice: 2 つの公開鍵ペア \((S_0,P_0)\), \((S_1,P_1)\) を生成し、公開鍵 \((P_0,P_1)\) を Bob に送信する。

  2. Bob: 対称鍵 \(E\) を生成して \(P_b\) で暗号化した \({\rm Enc}_b(E)\) を Alice に送信する。

  3. Alice: \(S_0\) と \(S_1\) それぞれで復号化した \(E_0\), \(E_1\) を使って対応するデータ \(M_0\), \(M_1\) を暗号化し、\(({\rm Enc}_0(M_0),{\rm Enc}_1(M_1))\) を Bob に送信する。ここで片方の対称鍵 \(E_\bar{b}\) は無意味なビット列になるが、Alice にはどちらが無意味な鍵であるか分からないことに注意。

  4. Bob: 対称鍵 \(E\) で \({\rm Enc}_b(M_b)\) を復号化して \(M_b\) を得る。ここで Bob は \({\rm Enc}_\bar{b}(M_\bar{b})\) を復号化するための鍵 \(E_\bar{b}\) を知らないので \(M_\bar{b}\) を入手できないことに注意。

この例では Bob が \(M_0\) と \(M_1\) の両方を入手するケースを排除できる。しかし Alice が \(M_0=M_1\) とする不正は残ったままである。ただし、もしすべての必要な手続きが完了した後に Bob が \(M_0\), \(M_1\) の両方を知っても良いのであれば、どこかのタイミングで Bob に \(S_0\), \(S_1\) を明かして \(M_0\ne M_1\) であったことを証明することができる。

非インタラクティブ紛失転送

文献 [3] は Bob が認証済みの設定で (つまり Alice が Bob の公開鍵を入手している前提で) 離散対数問題の困難性と Diffie-Hellman 仮定に基づいて非インタラクティブな 1-out-of-2 紛失転送を行う方法を提案している。

  1. 設定:

    1. Alice と Bob は素数 \(p\)、生成元 \(g\)、共通参照情報となる (素因数分解が明らかとなっていない) 定数 \(C\) を共有している。

    2. Alice はデータ \(s_0\) と \(s_1\) を持っている。

    3. Bob はランダムに \(i \in \{0,1\}\) と \(x_i \in \{0,\ldots,p-2\}\) を選択する。\(\beta_i=g^{x_i}\), \(\beta_\bar{i}=C\cdot (g^{x_i})^{-1}\) としたとき、公開鍵を \((\beta_0,\beta_1)\)、秘密鍵を \((i,x_i)\) とする。公開鍵は Alice に共有されているものとする。

  2. Alice: \(y_0,y_1 \in \{0,\ldots,p-2\}\) をランダムに選び、Bob に \((g^{y_0},g^{y_1})\) と \((s_0 \oplus \beta_0^{y_0}, s_1 \oplus \beta_1^{y_1})\) を送信する。

  3. Bob: 秘密鍵に基づいて \((g^{y_i})^{x_i}=\beta_i^{y_i}\) を計算し、\((s_i \oplus \beta_i^{y_i}) \oplus \beta_i^{y_i}=s_i\) を取得する。

Diffie-Hellman 仮定では \(g^x\) と \(g^y\) だけを知っていても \(g^{xy}\) を計算することは困難であることに注意。この方法は離散対数問題や DH 仮定を使っていくつかの問題を解決している。

  • Alice は Bob の公開鍵が正しいことを \(\beta_0 \cdot \beta_1 = g^{x_i}\cdot C \cdot (g^{x_i})^{-1} = C\) で検証できる。
  • Bob は \(\beta_\bar{i}=C\cdot (g^{x_i})^{-1}=g^{z_\bar{i}}\) となるような \(z_\bar{i}\) を計算することが困難であるため、\(s_\bar{i}\) を取得することは困難である。

ただし、Bob が \(s_\bar{i}\) を得る可能性を \(g^x\), \(g^y\) から \(g^{xy}\) を得るのと同程度に困難にするには、\(s_0\), \(s_1\) を 1 ビットとして \(k\) 回のプロトコルを繰り返す必要がある (ここで \(k\) は \(p\) を表現するのに必要なビット数)。任意長のデータを送るにはプロトコルをデータのビット数分だけ繰り返して送信することもできるが、文献 [3] では先に長さ \(k\) ビットのシークレットを送信し、以降はシークレットをシードとした疑似乱数による XOR で任意の長さのデータを送信する方法を提案している。

文献 [3] の方法は非インタラクティブである代わりに \(i\in\{0,1\}\) が公開鍵に固定され、データ送信ごとに \(i\) を選択できないことに注意。このため「2 つの送信データのうちどちらかの値しか受信できない」ではなく「2 つのチャネルのうちどちらかしか値を取り出せない」という意味にシフトしており、紛失通信チャネル (oblivious transfer channel) という呼び方をしている。

\((n-1)\)-out-of-\(n\) 紛失転送への拡張

文献 [3] の方法は少しの変更で \(k=n-1\) の紛失転送に拡張できる。

  1. Alice はデータ \(s_0,\ldots,s_{n-1}\) を持っている。

  2. Bob はランダムに \(i_0,\ldots,i_{k-1} \in \{0,1\}\) と \(x_1,\ldots,x_{k-1} \in \{0,\ldots,p-2\}\) を選択する。\(\beta_{i_0}=g^{x_{i_0}},\ldots,\beta_{i_{k-1}}=g^{x_{i_{k-1}}}\) とし、残った 1 つは \(\beta_\ell=C\cdot (g^{x_{i_0}})^{-1} \cdot \ldots \cdot (g^{x_{i_{k-1}}})^{-1}\) とする。公開鍵を \((\beta_0,\ldots,\beta_{n-1})\)、秘密鍵を \((i_0,\dots,i_{k-1},x_{i_0},\ldots,x_{i_{k-1}})\) とする。

後のプロトコルにも同様の拡張を加えれば良い。

参考文献

  1. Le Trieu Phong. 紛失通信プロトコルの考察. 情報通信研究機構季報 = Review of the National Institute of Information and Communications Technology / 情報通信研究機構広報部編 57 ((3・4)), 193-199, 2011.
  2. Bruce Schneier. Applied Cryptography: Protocols, Algorithms and Source Code in C, Vol 2 §5.5. Published by Wiley 2015
  3. BELLARE, Mihir; MICALI, Silvio. Non-interactive oblivious transfer and applications. In: Advances in Cryptology — CRYPTO’89 Proceedings. CRYPT0 ‘89, LNCS 435, pp. 547-557, 1990