暗号勉強会

あまりコードが出てこない話

相互通信を排除したマルチパーティ計算モデル※随時更新

マルチパーティ計算 NIMPC マルチパーティ計算モデル

NIMPC

NIMPC(Non-Interactive-Multi-party-Computation)はマルチパーティ計算モデルの一つ。2014年、任意関数のＮＩＭＰＣが実現された。従来のマルチパーティ計算モデルでは計算時の通信回数がボトルネックになっていたのが、NIMPCでは相互通信が排除されている。この記事では、自分が分かりにくいと感じたところを実例を交えながら紹介する。 ※このマルチパーティ計算モデルのマルチパーティ計算モデルにおける性能と先行研究についてはまだ調査不足

簡単な流れ

※ここでは指示関数は定義域の唯一の値に対して1を出力し、それ以外は0を返すような関数。

NIMPCに登場する定義一覧

  • 添え字の集合 [n]

例えばパーティが1からnまであるとすれば、[n]=\{1,2\dots,n\}

  • 添え字の部分集合 T

例えば[5]=\{1,2,3,4,5\}に対して、T=\{2,4,5\}、\bar{T}=\{1,3\}

  • 関数hの入力空間 \mathcal{X}

\mathcal{X_i,\dots,X_n}の直積で表される空間。T={2,4,5}とすると、T\subseteq [n]であるようなTの持つ入力空間は\mathcal{X_2,X_4,X_5}

  • 乱数空間 \mathcal{R}

\mathcal{R_1,\dots,R_n}の直積で表される空間。

  • メッセージ空間 \mathcal{M}

局所符号化関数Enc_iの終域。局所符号化関数Enc_iの始域はX_iとR_iの直積となる。

  • 出力空間 \mathcal{\Omega}

復号関数Dec_iの終域。復号関数Dec_iの始域は\mathcal{M}である。

書き方は構成によってちょっとずつ違う。rは乱数、xは入力、mはメッセージであることは変わらない。

NIMPCの構成

関数族h\in Hに対して、以下のようにNIMPCは以下のようなモデルである。

  • ランダム生成アルゴリズムGen関数hを与えると、関係のあるn個のr_1,\dots,r_nを生成。
  • ローカル符号化関数Enc_iによって、秘密x_iとr_iを使って、メッセージ生成（各iでの処理）
  • 復号アルゴリズムDecはn個のメッセージからh(x_1,\dots,x_n)を再構成する。

NIMPCの何がうれしいのかと言えば非対話的であるところだ。モデルを見ると乱数を生成し、メッセージを生成して送るだけで任意関数の評価ができると言っているのである。以下は任意関数を評価しつつ、このモデルが安全であることを示そう。なお、マルチパーティ計算においての安全性は入力と出力から得られる情報以外は何も得られず、臨んだ出力が得られることが求められる。これをprivacyとcorrectnessというが詳しくは別に解説記事を出す。

具体例

例えば多入力関数h(x_1,\dots,x_n)をh(x_1,\dots,x_n)=x_1 \times \dots \times x_nのように総乗を計算する関数とする。この時、Genはhをもとにr _ 1,\dots,r _ {n-1}までの一様な乱数と、r _ n={\frac{1}{\Pi_{i=1}^{n-1} r _ i}}を生成する。この時、r _ nはr _ 1,\dots,r _ {n-1}の積の逆数となっているので、必ず\Pi _ {i=1}^n r _ i=1になる。局所符号化関数をEnc _ {i}(x _ i,r _ i)=x _ i \times r _ i=m _ iとする。この時、

Dec(Enc_{i}(x_i,r_i))=\Sigma_{i=1}^n m_i=\Pi_{i=1}^n x_i \times \Pi_{i=1}^n r_i=\Pi_{i=1}^n x_i

つまり、結果はh(x)である。ちなみに論文内ではこれを総和で計算する方法が紹介されている。r _ n={\frac{1}{\Pi_{i=1}^{n-1} r _ i}}なのでr _ 1,\dots,r _ {n}は関係のある乱数である。

T-robustの安全性

NMPCにおける安全性はSim_T関数というものを用いて、シミュレートできるかどうかで判定する。 1\leq t \leq nとすると、t-robustであるとはすべてのサイズt以下のTに対してT-robustならt-robustという。fully robustというのはn-robust（つまり全サイズにおいてrobustである）のことを言う。また、関数族ｈに対してt-robustならt-robust NIMPCプロトコルという。 大きさがtの結託したパーティをTとし、hのうち\bar{T}の入力を固定したものをh| _ {\bar{T},x _ \bar{T}} とする。このとき、Sim _ T(h| _ {\bar{T},x _ \bar{T}})\equiv (M _ \bar{T},R _ T)ができる、つまり、Tがh| _ {\bar{T},x _ \bar{T}} と知っている情報を使って(M_\bar{T},R_T)を入手できれば、T-robustである。 インフォーマルにはT-robustはパーティTに関数から漏れる情報以上のことは何も情報を漏らしていないということを意味している。

具体例

ここで、T=\{1,2\}かつ\bar{T} = \{3,4\},|T|=2であるとしよう。

h| _ {\bar{T},x _ \bar{T}}(1^{|T|})=h(1,1,x_3,x_4)=1 \times 1 \times x_3 \times x_4 \times \Pi_{i=1}^{n-1} r _ i = x_3 \times x_4

x_3 \times x_4を入手できた。 次に\rho _ 1,\rho _ 2,\rho _ 3をランダムに選ぶ。\rho _ 4のみ、\rho _ 4=\frac{x_3 \times x_4}{\rho _ 1 \times \rho _ 2 \times \rho _ 3} とする。 このとき\rho _ 1,\rho _ 2,\rho _ 3,\rho _ 4を使って、M _ \bar{T}=\{\rho _ 3,\rho _ 4 \}とR _ T=\{\rho _ 1,\rho _ 2 \}をシミュレーションできる。

実際、知っている情報x_1,x_2と\rho _ 1,\rho _ 2,\rho _ 3,\rho _ 4を用いることで、

\begin{eqnarray} Dec(Enc_{i}(x_i,r_i))&=&\Pi_{i=1}^n m_i=\Pi_{i=1}^n x_i \times \Pi_{i=1}^n r_i=x_1 \times r _ 1 \times \dots \times x _ i \times r _ i \\ &=& x _ 1 \times \rho _ 1 \times x _ 2 \times \rho _ 2 \times \rho _ 3 \times \rho _ 4 \\ &=& x _ 1 \times x _ 2 \times x _ 3 \times x _ 4 \end{eqnarray}

であるので、シュミレーションできている。2行目では\rho _ 4=\frac{x_3 \times x_4}{\rho _ 1 \times \rho _ 2 \times \rho _ 3} をつかって、\rho _ 1,\rho _ 2,\rho _ 3を消去している。

NIMPCプロトコル

NIMPCモデルをもとに、対話通信するプロトコルを定義する。P(\Pi)をn人のプレイヤーP_1,\dots,P_nと各プレイヤーが持つx_iがあるプロトコルとする。この時、P_0という入力がなく出力をするだけのサーバを作る。hは追加の入力とする。

  • 準備フェーズ

Gen関数hを、関係のあるn個のr_1,\dots,r_nを生成する。これを各P_iが受け取る。

  • 対話通信フェーズ

各プレイヤーはEnc_iによって、秘密x_iとr_iを使って、メッセージ\mathcal{M_i}を生成しP_0に送る。（各iでの処理）

  • 出力フェーズ　

P_0は受け取ったn個のメッセージからDecでh(x_1,\dots,x_n)を再構成する。

NIMPCプロトコルの指示関数による読み替え

指示関数を用いて構成する

１. 指示関数の族からNIMPCを構成する。

２. 指示関数h_aの和から指示関数のNIMPCを構成する。NIMPCをもとにNIMPCを構成する。

\mathcal{H_{ind}}はいくつかのh_aとh_0からなる族である。この族に含まれるhは以下のように分類される。

h(x)=\begin{cases} h_a(a)=1\ (h=h_a\ and\ x=a) \\ h_a(x)=0\ (h=h_a\ and\ x\neq a)\\ h_0(x)=0\ (h=h_0) \\ \end{cases}

この指示関数族によって構成する。 すべてのサイズtの連合Tが必要な情報だけ得られる。我々ものモデルでは\bar{T}のメッセージMから多くの出力を計算できる。 ｍとｒを明らかにすることが、T以外のパーティの入力を得るのと同じ。つまり、T以外のパーティの入力を固定したh以上の情報を得られない。

指示関数のNIMPC

P(\Pi_ind)をn人のプレイヤーP_1,\dots,P_nと各プレイヤーが持つx_iがあるプロトコルとする。この時、P_0という入力がなく出力をするだけのサーバを作る。hは追加の入力とする。また、b\in\mathcal{X_i}である。

準備フェーズ

  • h=h _ 0なら、s個のs次元ベクトルからなる集合\{m _ {i,b} \} _ {i\in[n],b\in\mathcal{X _ i}}を生成する。

  • h=h _ aなら、s個のs次元ベクトルからなる集合\{m _ {i,b} \} _ {i\in[n],b\in\mathcal{X _ i}}をa=(a_1,\dots,a_n)\in \mathcal{X}に対して\Sigma _ {i=1}^{n}m _ {i,a _ i}=0を満たすように選ぶ。（例えば、m _ {i,a _ 1},\dots,m _ {i,a _ {n-1}}はランダムに選び、m _ {i,a _ n}=-\Sigma _ {i=1}^n m_{i,a_i}とすることでそれは実現できる）

  • そして、d_i次元ベクトル\{m _ {i,b}\} _ {b\in \mathcal{X_i}}を各P _ iに送る。

対話通信フェーズ

各プレイヤーP_iは、 \{m _ {i,b} \} _ {b\in \mathcal{X _ i}}を持っている。x_iを関数に入力したいとすればb=x_iであるようなm _{i,b}をM_iとおいて、P_0に送る。（各iでの処理）

出力フェーズ　

P_0は受け取ったn個のメッセージM_iから\Sigma_{i=1}^{n} M_iを計算する。結果が0なら1、そうでなければ0をP_0は出力する。 M_iの和は、h_aかつx=aなら0になるように選ばれているので0、P_0は1を出力する。それ以外は0を出力する。つまり、P_1がa_1、P_2がa_2...というように各パーティP_iがa_iを入力し、全体としてaになっているときだけP_0は1を出力する。

具体例

準備フェーズ

\mathcal{X_1}=\{1,2,3\},\mathcal{X_2}=\{4,5,6\},\mathcal{X _ 3}=\{7,8,9\} とすると、h=h_aのときa=(1,4,7)に対し、\Sigma _ {i=1}^{n}m _ {i,a _ i}=0を満たすように

\{m _ {i,b} \} _ {i \in [n ],b\in\mathcal{X _ i}} = \{m _ {1,1},m _ {1,2},m _ {1,3},m _ {2,1},m _ {2,2},m _ {2,3},m _ {3,1},m _ {3,2},m _ {3,3} \}

をランダムに生成する。このとき、m _ {1,1},m _ {2,4}はランダムに選び、m _ {3,7}=-\Sigma _ {i=1}^{2} m_{i,a_i}とする。そして、 \{m _ {1,b} \} _ {b\in \mathcal{X _ 1}} = \{m _ {1,1},m _ {1,2},m _ {1,3}\}はP_1に送られる。

対話通信フェーズ

プレイヤーP_1で考える。m _ {1,b}=\{m _ {1,1},m _ {1,2} ,m _ {1,3}\}を持っている。プレイヤーP_1が1を関数に入力したいとすればm _ {1,1}を、2を関数に入力したいとすればm _ {1,2}をM_1とおいて(入力はb \in X_i)、P_0に送る。この時、P_1,P_2,P_3がそれぞれm _ {1,1},m _ {2,4},m _ {3,7}を入力していればaを入力したことになる。

計算フェーズ

プレイヤーP _ 0が受け取ったM _ iがM _ 1=m _ {1,1},M_2=m _ {2,4},M _ 3=m _ {3,7}だとすれば、

\Sigma _ {i=1}^{3} M_i=m _ {1,1}+m _ {2,4}+m _ {3,7}=m _ {1,1}+m _ {2,4} -\Sigma _ {i=1}^{2} m _ {i,a _ i}=0

でありP _0は1を出力する。これはつまりh(a)=1を計算したことになる。

指示関数の上位プロトコル

指示関数族のうち、ある入力aによって1になるh_aだけ集めて族を構成する。つまり、\Sigma_h(a)={1,a \in \mathcal{X}} h_a。この構築方法には二つの問題点がある。

  • 関数が1を返すような1の個数が分かってしまう。NIMPCにおいては関数を隠すことを考える。その時、\Sigma_h(a)={1,a \in \mathcal{X}} h_a で指示関数を和から関数を作ると、h_a(a)=1となる関数の個数から計算している関数が推測できてしまうので和にh_0を含める。具体的にはh_a(a)=1ならh_a'=h_aにし、h_a(a)=0ならh_a'=h_0とし、\Sigma _ {a \in \mathcal{X}} h' _ aと定義しなおす。
\begin{eqnarray} h(a)&=h _ a(a)+h _ a(a)=&1+0\\ & &\downarrow\\ h(a)&=h' _ a(a)+h' _ a(a)+h&' _ a(a)=h _ a(a)+h _ a(a)+h _ 0(a) \\ \end{eqnarray}
  • h(x)=1となったとき、x=aなので自分の入力と合わせて他のパーティの入力が分かってしまう。置換\piを使って入力を隠す。置換\piはX_iに含まれるa={a_1,a_2\dots,a_n}の順番を並び替える。

任意の真偽関数評価

P(\Pi)(h)をn人のプレイヤーP_1,\dots,P_nと各プレイヤーが持つx_iがあるプロトコルとする。この時、P_0という入力がなく出力をするだけのサーバを作る。hは追加の入力とする。

準備フェーズ

  • Iはh(x)=1となるようなxの集合とする。
\begin{cases} Gen(h _ a)=r^{a}=\{r^{a} _ 1,\dots,r^{a} _ n\}(For\ each\ a \in I)\\ Gen(h _ 0)=r^{a}=\{r^{a} _ 1,\dots,r^{a} _ n\}(For\ each\ a \in X-I)\\ \end{cases}

h_a(x)=1となるようなaは今回の構成では複数存在しているので、そのようなh_aとaごとに行う。

  • その後、行列Rを生成する。この行列は(R _ {i,b}) _ {b\in\mathcal{X}}:=r_i^{\pi(b)}を行に持つような行列でi\times |\mathcal{X_i}|行列である。例えば、
R = \left( \begin{array}{ccc} (R _ {1,b}) _ {b \in \mathcal{X}} & \\ \vdots & \\ (R _ {n,b}) _ {b \in \mathcal{X}} & \end{array} \right)

(R _ {i,b}) _ {b\in X} (Rのi列)を各P _ iに送る。

対話通信フェーズ

各プレイヤーP_iはx_iを入力するために、行列Mを作る。MはM _ {i,b}:=Enc _ i(x _ i,R _ {i,b})を各要素とする行列として定義される。

M = \left( \begin{array}{c} (M _ {1,b}) _ {b \in \mathcal{X}} & \\ \vdots & \\ (M _ {n,b}) _ {b \in \mathcal{X}} & \end{array} \right)= \left( \begin{array}{c} (Enc _ 1(x _ 1,R _ {1,b})) _ {b \in \mathcal{X}} & \\ \vdots & \\ (Enc _ n(x _ n,R _ {n,b})) _ {b \in \mathcal{X}} & \end{array} \right)

Mの行であるM_i:=(M _ {i,b}) _ {b\in \mathcal{X}}をP_0に送る。(各iでの処理）

出力フェーズ　

あるbに対し、Dec(M _ {1,b},M _ {2,b}, \dots ,M _ {n,b})=1を出力し、残りは0になる。ここで1を返すような\pi(b)=a=\hat{b}つまり、

出力フェーズであるbとなっているのは、前回と違って、一つのaに対して値を返すわけではないこと、またbが置換されていること、が影響している。

具体例

準備フェーズ

OR関数hのように和で表すことを考えよう。P=\{P _ 0,P _ 1,P _ 2\}として、X _ 1=\{ 0,1\} ,X _ 2=\{ 0,1 \}である。

入力x 入力y x or y
0 0 0
0 1 1
1 0 1
1 1 1

h(a)=1になるようなaは(0,1),(1,0),(1,1)である。よって、h(a)=h _ {(0,1)}+h _ {(1,0)}+h _ {(1,1)}となる。 このままだと１の個数が分かってしまうので、h _ {(0,0)}に0を返すことを保証する関数（後でわかるが、置換するため何も返さないようなh _ 0が欲しい）を含め、h=\Sigma _ {a \in \mathcal{X}} h' _ a =h _ {(0,1)} + h _ {(1,0)} + h _ {(1,1)}+ h _ 0とする。この関数h' _ aのひとつひとつに対して、NIMPCプロトコルP(\Pi _ {ind})を呼び出してる。つまりこのNIMPCプロトコルP(\Pi)は、関数h' _ aの含む関数の数、つまり４つだけ、並列にP(\Pi _ {ind})が動いている。

定義から、明らかに(0,1),(1,0),(1,1) \in Iであり、 (0,0) \in X-Iである。

a \in I、つまりa \in \{(0,1),(1,0),(1,1)\}について

r _ {(0,1)}=(r^{(0,1)} _ {1},\dots,r^{(0,1)} _ {n}) \leftarrow Gen(h _ {(0,1)})\\ r _ {(1,0)}=(r^{(1,0)} _ {1},\dots,r^{(1,0)} _ {n}) \leftarrow Gen(h _ {(1.0)})\\ r _ {(1,1)}=(r^{(1,1)} _ {1},\dots,r^{(1,1)} _ {n}) \leftarrow Gen(h _ {(1,1)})\\

a \in X-I、つまりa \in \{(0,0)\}について

r _ {(0,0)}=(r^{(0,0)} _ {1},\dots,r^{(0,0)} _ {n}) \leftarrow Gen(h _ 0)

この乱数生成はそれぞれ、\mathcal{P(H _ {ind})}の乱数生成に対応している。 さて、これをもとに行列Rを生成する。表を一つ進める置換\piによって、R _ {i,b}:=r _ i^{\pi(b)}とおくと、 例えば、R _ {1,(0,1)}=r _ 1^{\pi (0,1)}=r _1^{(1,0)}となる。この時、R _ {1,(0,1)}=r _ 1^{(1,0)}のように外から見える添え字bと実際の添え字aが異なっているのでGarbled Cirucuitのようにどれがどれに対応しているのかわからない。

R = \left( \begin{array}{ccc} R _ {1,(0,0)} & R _ {1,(0,1)} & R _ {1,(1,0)} & R _ {1,(1,1)} \\ R _ {2,(0,0)} & R _ {2,(0,1)} & R _ {2,(1,0)} & R _ {2,(1,1)} \end{array} \right)

(R _ {i,b}) _ {b\in X} (Rのi列)を各P _ iに送る。例えば、P_1には R _ {1,(0,0)},R _ {1,(0,1)},R _ {1,(1,0)},R _ {1,(1,1)} を送る。

対話通信フェーズ

P_1にフォーカスすると、P_1はx_1を入力にM _ {1,b}:=Enc _ 1(x _ 1,R _ {1,b})を各要素としてMを定義される。P_1は R _ {1,(0,0)},R _ {1,(0,1)},R _ {1,(1,0)},R _ {1,(1,1)} を持っている。

M\\ = \left( \begin{array}{c} Enc _ 1(x _ 1,R _ {1,(0,0)}), Enc _ 1(x _ 1,R _ {1,(0,1)}), Enc _ 1(x _ 1,R _ {1,(1,0)}), Enc _ 1(x _ 1,R _ {1,(1,1)}) \\ Enc _ 2(x _ 2,R _ {2,(0,0)}), Enc _ 2(x _ 2,R _ {2,(0,1)}), Enc _ 2(x _ 2,R _ {2,(1,0)}), Enc _ 2(x _ 2,R _ {2,(1,1)}) \\ \end{array} \right)\\ =\left( \begin{array}{cccc} M _ {1,(0,0)} , M _ {1,(0,1)}, M _ {1,(1,0)} , M _ {1,(1,1)} \\ M _ {2,(0,0)} , M _ {2,(0,1)} , M _ {2,(1,0)} , M _ {2,(1,1)} \\ \end{array} \right)

ここで、Mの各列はNIMPCプロトコルP(\Pi _ {ind})のm _ {i,b}を表している。つまり列の数だけP(\Pi _ {ind})が動いている。 Mの行であるM _ 1=\{M _ {1,(0,0)} , M _ {1,(0,1)}, M _ {1,(1,0)} , M _ {1,(1,1)}\}をP_1はP_0に送る。P_2で同じことを行う。

計算フェーズ

そして、M_1,M_2からP_0は

\begin{eqnarray} Dec&(M_{1,(0,0)},M_{2,(0,0)})\\ Dec&(M_{1,(0,1)},M_{2,(0,1)})\\ Dec&(M_{1,(1,0)},M_{2,(1,0)})\\ Dec&(M_{1,(1,1)},M_{2,(1,1)}) \end{eqnarray}

を計算する。これは一つのDecがそれぞれP(\Pi _ {ind})と対応している。

それぞれ置換されているので、それを考慮すると

\begin{eqnarray} Dec&(M _ {1,(0,0)},M _ {2,(0,0)}) =h _ {\pi(0,0)}(x_1,x_2)=h _ {(0,1)}(x_1,x_2)\\ Dec&(M _ {1,(0,1)},M _ {2,(0,1)})=h _ {\pi(0,1)}(x_1,x_2)=h _ {(1,0)}(x_1,x_2)\\ Dec&(M _ {1,(1,0)},M _ {2,(1,0)})=h _ {\pi(1,0)}(x_1,x_2)=h _ {(1,1)}(x_1,x_2)\\ Dec&(M _ {1,(1,1)},M _ {2,(1,1)})=h _ {\pi(1,1)}(x_1,x_2)=h _ 0 (x_1,x_2) \end{eqnarray}

となっている。つまり、このNIMPCプロトコルP(\Pi)が出力するのは、

h(x_1,x_2)=h _ {(0,1)}(x_1,x_2)+h _ {(1,0)}(x_1,x_2)+h _ {(1,1)}(x_1,x_2)+ h _ 0 (x_1,x_2)\\

の結果である。

例えば、x _ 1=0,x _ 2=1とすると、

h(0,1)=h _ {(0,1)}(0,1)+h _ {(1,0)}(0,1)+h _ {(1,1)}(0,1)+ h _ 0 (0,1)=0+1+0+0=1

or関数が計算できた。

まとめ

この記事ではNIMPCの数式の具体例を挙げて解説し、任意の真偽関数が評価できることを示した。 NIMPCの勉強をする人やマルチパーティ計算モデルに興味がある人の助けに少しでもなればと思う！ 不足箇所があるので、分かり次第更新していきます！

参考文献

Non-Interactive Secure Multiparty Computation A.Beimel, A.Gabizon, Y.Ishai, E.Kushilevitz, S.Meldgaard, A.Paskin-Cherniavsky (https://link.springer.com/content/pdf/10.1007/978-3-662-44381-1_22.pdf)