コンテンツにスキップ
tah5.com
ブログ

マルチパーティ計算（MPC）について

マルチパーティ計算（MPC, Multi-Party Computation）は、「秘密情報」の計算を、「秘密情報のシェア」を使って行う技術です。秘密情報を明かさずに計算を行うことができます。

BGW 型 MPC

BGW 型 MPC は、Shamir の秘密分散法を基盤として加算や乗算といった計算を実現する方式です。BGW は、提案者の Ben-Or 氏, Goldwasser 氏, Wigderson 氏 の頭文字を取っています。

加算 - BGW 型 MPC

BGW 型 MPC における加算は、各パーティが保持するシェアを単純に加算することで実現されます。

  • 秘密情報a=31a=31
  • 秘密情報b=18b=18
  1. 秘密情報a,ba,bからシェアsi,tis_i,t_iを作成し、各パーティPiP_iに配布する
  2. 各パーティは自身の持つ 2 つのシェアを加算する
  3. 各パーティが持つ加算結果のシェアを使って秘密情報の復元を行うと、a+ba+bの結果が得られる
  • P1P_1のシェア: (s1,t1)=(39,17)(s_1,t_1)=(39,17)
  • P2P_2のシェア: (s2,t2)=(37,20)(s_2,t_2)=(37,20)
  • P3P_3のシェア: (s3,t3)=(25,27)(s_3,t_3)=(25,27)
  • P4P_4のシェア: (s4,t4)=(3,38)(s_4,t_4)=(3,38)
sis_itit_isi+tis_i+t_i
P1P_1が知りうる情報 →391756
P2P_2が知りうる情報 →372057
P3P_3が知りうる情報 →252752
P4P_4が知りうる情報 →33841

各パーティは秘密情報a,ba,bおよびその加算結果a+ba+bの「シェア」を保持していますが、秘密情報a,ba,bおよびその加算結果a+ba+bそのものを知ることはできません。

乗算 - BGW 型 MPC

加算と同様にシェア同士を乗算すると、秘密情報の復元に必要なシェアの数が増加してしまいます。これは、Shamir の秘密分散法が、k−1k-1次多項式を使用していることに起因します。シェア同士を乗算すると、k−1k-1次多項式から(k−1)+(k−1)=2k−2(k-1)+(k-1)=2k-2次多項式へと次数が増加します。本来(k,n)(k,n)しきい値法として扱っていたものが、((2k−2)+1,n)=(2k−1,n)((2k-2)+1,n)=(2k-1, n)しきい値法となります。

そのため、BGW 型 MPC における乗算では、各パーティがシェア同士を乗算した後に、パーティ間でやりとり（通信）を行い、しきい値を調整します。

  1. 各パーティは自身の持つ乗算結果から、(k,n)(k,n)Shamir の秘密分散法でシェアを作成する（パーティがディーラーになる）
  2. ステップ 1 で作成したnn個のシェアを各パーティに配布する（nn個のうちの一つは自身が保持する）
  3. 各パーティは、受け取ったシェアのうち2k−12k-1個を使って秘密情報の復元を行う

ステップ 3 の秘密情報の復元により得られるのは、次数が下がった(k,n)(k,n)しきい値法のシェアです。このシェアがkk個集まることで、乗算結果が得られます。

複製型秘密分散法に基づく MPC

加算 - 複製型秘密分散法に基づく MPC

BGW 型 MPC同様、各パーティが保持するシェアを要素ごとに加算するだけで実現できます。

(2,3)(2,3)複製型秘密分散法に基づく MPC での加算 では、秘密情報a,ba,bから(3,3)(3,3)加法型秘密分散法シェアs1,s2,s3s_1,s_2,s_3とt1,t2,t3t_1,t_2,t_3を作成し、以下のように配布します。

  • P1P_1のシェア: (s1,s2),(t1,t2)(s_1,s_2),(t_1,t_2)
  • P2P_2のシェア: (s2,s3),(t2,t3)(s_2,s_3),(t_2,t_3)
  • P3P_3のシェア: (s3,s1),(t3,t1)(s_3,s_1),(t_3,t_1)

各パーティが要素ごとに加算すると、以下のような結果が得られます。

  • P1P_1のシェア: (s1+t1,s2+t2)(s_1+t_1,s_2+t_2)
  • P2P_2のシェア: (s2+t2,s3+t3)(s_2+t_2,s_3+t_3)
  • P3P_3のシェア: (s3+t3,s1+t1)(s_3+t_3,s_1+t_1)

この加算の結果のシェアを任意の 2 パーティから集めることで、加算結果a+ba+bを得られます。

乗算 - 複製型秘密分散法に基づく MPC

乗算では、各パーティが以下に示す計算(1)(1)を行った後に、パーティ間でやりとり（通信）を行います。

(2,3)(2,3)複製型秘密分散法に基づく MPC での乗算では、秘密情報a,ba,bから(3,3)(3,3)加法型秘密分散法シェアs1,s2,s3s_1,s_2,s_3とt1,t2,t3t_1,t_2,t_3を作成し、以下のように配布します。

  • P1P_1のシェア: (s1,s2),(t1,t2)(s_1,s_2),(t_1,t_2)
  • P2P_2のシェア: (s2,s3),(t2,t3)(s_2,s_3),(t_2,t_3)
  • P3P_3のシェア: (s3,s1),(t3,t1)(s_3,s_1),(t_3,t_1)
ui=siti+(si+si+1)+(ti+ti+1)(1)u_i=s_{i}t_{i}+(s_i+s_{i+1})+(t_i+t_{i+1}) \tag{1}

この計算結果uiu_iは、ababの(3,3)(3,3)加法型秘密分散法のシェアとなります。このことは、全てのパーティのシェアを集めて復元するとababとなることから確かめられます。

 s1t1+(s1+s2)+(t1+t2)+s2t2+(s2+s3)+(t2+t3)+s3t3+(s3+s1)+(t3+t1)= s1t1+s1t1+s1t2+s2t1+s2t2+s2t2+s2t2+s2t3+s3t2+s3t3+s3t3+s3t3+s3t1+s1t3+s1t1= s1t1+s1t2+s1t3+s2t1+s2t2+s2t3+s3t1+s3t2+s3t3= s1(t1+t2+t3)+s2(t1+t2+t3)+s3(t1+t2+t3)= (s1+s2+s3)(t1+t2+t3)= ab\begin{align*} \space &s_{1}t_{1}+(s_{1}+s_{2})+(t_{1}+t_{2})+s_{2}t_{2}+(s_{2}+s_{3})+(t_{2}+t_{3})+s_{3}t_{3}+(s_{3}+s_{1})+(t_{3}+t_{1})\\ =& \space s_{1}t_{1}+s_{1}t_{1}+s_{1}t_{2}+s_{2}t_{1}+s_{2}t_{2}+s_{2}t_{2}+s_{2}t_{2}+s_{2}t_{3}+s_{3}t_{2}+s_{3}t_{3}+s_{3}t_{3}+s_{3}t_{3}+s_{3}t_{1}+s_{1}t_{3}+s_{1}t_{1}\\ =& \space s_{1}t_{1}+s_{1}t_{2}+s_{1}t_{3}+s_{2}t_{1}+s_{2}t_{2}+s_{2}t_{3}+s_{3}t_{1}+s_{3}t_{2}+s_{3}t_{3}\\ =& \space s_{1}(t_{1}+t_{2}+t_{3})+s_{2}(t_{1}+t_{2}+t_{3})+s_{3}(t_{1}+t_{2}+t_{3})\\ =& \space (s_{1}+s_{2}+s_{3})(t_{1}+t_{2}+t_{3})\\ =& \space ab \end{align*}

加法型秘密分散法シェアから複製型秘密分散法シェアに変換

uiu_iがababの(3,3)(3,3)加法型秘密分散法のシェアであることはわかりましたが、複製型秘密分散法が加法型秘密分散法になってしまっているので、複製型秘密分散法に戻す作業が必要です。

各パーティPiP_iは現在、以下のシェアuiu_iを保持しています。

P1:u1P2:u2P3:u3\begin{align*} P_1&: u_1\\ P_2&: u_2\\ P_3&: u_3\\ \end{align*}

各パーティPiP_iがuiu_iをPi−1P_{i-1}に送信すれば、

P1:(u1,u2)P2:(u2,u3)P3:(u3,u1)\begin{align*} P_1&: (u_1,u_2)\\ P_2&: (u_2,u_3)\\ P_3&: (u_3,u_1) \end{align*}

となり、(2,3)(2,3)複製型秘密分散法に変換することができます。

PRSS

通信を安全かつ効率的に実現する有力な手順として、疑似乱数秘密分散（Pseudorandom secret sharing, PRSS）が用いられます。PRSS は、事前に共有された鍵やシードを用いて各パーティが擬似的に乱数シェアを作成します。この乱数シェアを復元した結果が 0 となる性質を持つため、0 の秘密分散とも言えます。これにより、MPC で計算する本来の値に影響を与えずに、乱数シェアの加算によってシェアをランダム化し、情報の漏れを防ぐことが可能となります。

PRSS を用いて乱数シェアを生成する方法を 2 つ紹介します。

モジュロ演算を用いた PRSS
  1. 各パーティPiP_iは乱数rir_iを生成し、その乱数をパーティPi+1P_{i+1}へ送信する（以下、適宜(i+j) mod n(i+j) \space mod \space n）
  2. 各パーティPiP_iは、自身が生成した乱数rir_iとPi−1P_{i-1}から受け取った乱数ri−1r_{i-1}の差分（ri−ri−1 mod qr_i - r_{i-1} \space mod \space q）を計算する

各パーティは以下の PRSS シェアを保持します。

P1:prss1=(r1−r3) mod qP2:prss2=(r2−r1) mod qP3:prss3=(r3−r2) mod q\begin{align*} P_1: prss_1 = (r_1 - r_3) \space mod \space q\\ P_2: prss_2 = (r_2 - r_1) \space mod \space q\\ P_3: prss_3 = (r_3 - r_2) \space mod \space q\\ \end{align*}

各パーティが計算したシェアの合計は、モジュロqqにおいて 0 になります。

(r1−r3)+(r2−r1)+(r3−r2)=0 mod q(r_1 - r_3) + (r_2 - r_1) + (r_3 - r_2) = 0 \space mod \space q

HMAC/ハッシュ関数を用いた PRSS

HMAC/ハッシュ関数を用いた PRSS は、特に XOR ベースの秘密分散法（例: 二元体GF(2n)GF(2^n)上の計算）で用いられます。

  1. 各パーティPiP_iは乱数（キー）kik_iを生成し、その乱数をパーティPi+1P_{i+1}へ送信する
  2. 各パーティPiP_iは、自身の持つキーkik_iと自身のパーティ ID iiを入力として HMAC 値hi=HMAC(ki,i)h_i = HMAC(k_i, i)を計算する
  3. 同様に、Pi−1P_{i-1}から受け取ったキーki−1k_{i-1}とパーティ ID i−1i-1を入力として HMAC 値hi−1=HMAC(ki−1,i−1)h_{i-1} = HMAC(k_{i-1}, i-1)を計算する

この手順によって各パーティは 2 つの HMAC 値hi,hi−1h_i,h_{i-1}を保持します。

P1:prss1=h1⊕h3P2:prss2=h2⊕h1P3:prss3=h3⊕h2\begin{align*} P_1: prss_1 = h_1 \oplus h_3\\ P_2: prss_2 = h_2 \oplus h_1\\ P_3: prss_3 = h_3 \oplus h_2\\ \end{align*}

すべてのシェアを XOR すると、各 HMAC 値がちょうど 2 回出現するため、結果は 0 になります。

prss1⊕prss2⊕prss3=(h1⊕h3)⊕(h2⊕h1)⊕(h3⊕h2)=0prss_1 \oplus prss_2 \oplus prss_3 = (h_1 \oplus h_3) \oplus (h_2 \oplus h_1) \oplus (h_3 \oplus h_2) = 0

モジュロ演算を用いた PRSS によるシェア変換

加法型秘密分散法シェアから複製型秘密分散法シェアに変換のステップで、各パーティは計算結果uiu_iを持っています。

P1:u1P2:u2P3:u3\begin{align*} P_1&: u_1\\ P_2&: u_2\\ P_3&: u_3\\ \end{align*}

各パーティは PRSS を使ってシェアをマスクします。先に説明したモジュロ演算を用いた PRSS によって、各パーティは以下の PRSS シェアを持っています。

P1:prss1=(r1−r3) mod qP2:prss2=(r2−r1) mod qP3:prss3=(r3−r2) mod q\begin{align*} P_1: prss_1 = (r_1 - r_3) \space mod \space q\\ P_2: prss_2 = (r_2 - r_1) \space mod \space q\\ P_3: prss_3 = (r_3 - r_2) \space mod \space q\\ \end{align*}

まず、各パーティは自身の持つuiu_iを自身の PRSS シェアでマスクします。

P1:v1=(u1+prss1) mod qP2:v2=(u2+prss2) mod qP3:v3=(u3+prss3) mod q\begin{align*} P_1: v_1 = (u_1 + prss_1) \space mod \space q\\ P_2: v_2 = (u_2 + prss_2) \space mod \space q\\ P_3: v_3 = (u_3 + prss_3) \space mod \space q\\ \end{align*}

次に、各パーティPiP_iはviv_iをPi−1P_{i-1}に送信します。送信後、各パーティは以下のシェアを保持しています。

P1:(v1,v2)=(u1+prss1,u2+prss2)P2:(v2,v3)=(u2+prss2,u3+prss3)P3:(v3,v1)=(u3+prss3,u1+prss1)\begin{align*} P_1&: (v_1, v_2) = (u_1 + prss_1, u_2 + prss_2)\\ P_2&: (v_2, v_3) = (u_2 + prss_2, u_3 + prss_3)\\ P_3&: (v_3, v_1) = (u_3 + prss_3, u_1 + prss_1)\\ \end{align*}

これにより、複製型秘密分散法の形式に変換されました。

復元の確認 - モジュロ演算

任意の 2 パーティから 3 つの異なるマスクされたシェアv1,v2,v3v_1, v_2, v_3を集めると、それらを加算することで秘密情報ababを復元できます。

v1+v2+v3=(u1+prss1)+(u2+prss2)+(u3+prss3)=(u1+u2+u3)+(prss1+prss2+prss3)=(u1+u2+u3)+0=u1+u2+u3=ab\begin{align*} v_1 + v_2 + v_3 &= (u_1 + prss_1) + (u_2 + prss_2) + (u_3 + prss_3)\\ &= (u_1 + u_2 + u_3) + (prss_1 + prss_2 + prss_3)\\ &= (u_1 + u_2 + u_3) + 0\\ &= u_1 + u_2 + u_3\\ &= ab \end{align*}

PRSS を用いることで通信内容をマスクしながら、正しく複製型秘密分散法に変換でき、最終的に秘密情報ababを復元することができます。

XOR ベースの PRSS によるシェア変換

二元体GF(2n)GF(2^n)上での計算や XOR ベースの秘密分散法を用いる場合は、先に説明した HMAC/ハッシュ関数を用いた PRSS を適用します。この場合、加算の代わりに XOR 演算を使用します。

P1:v1=u1⊕prss1=u1⊕(h1⊕h3)P2:v2=u2⊕prss2=u2⊕(h2⊕h1)P3:v3=u3⊕prss3=u3⊕(h3⊕h2)\begin{align*} P_1&: v_1 = u_1 \oplus prss_1 = u_1 \oplus (h_1 \oplus h_3)\\ P_2&: v_2 = u_2 \oplus prss_2 = u_2 \oplus (h_2 \oplus h_1)\\ P_3&: v_3 = u_3 \oplus prss_3 = u_3 \oplus (h_3 \oplus h_2)\\ \end{align*}

各パーティPiP_iはviv_iをPi−1P_{i-1}に送信し、以下のシェアを保持します。

P1:(v1,v2)=(u1⊕h1⊕h3,u2⊕h2⊕h1)P2:(v2,v3)=(u2⊕h2⊕h1,u3⊕h3⊕h2)P3:(v3,v1)=(u3⊕h3⊕h2,u1⊕h1⊕h3)\begin{align*} P_1&: (v_1, v_2) = (u_1 \oplus h_1 \oplus h_3, u_2 \oplus h_2 \oplus h_1)\\ P_2&: (v_2, v_3) = (u_2 \oplus h_2 \oplus h_1, u_3 \oplus h_3 \oplus h_2)\\ P_3&: (v_3, v_1) = (u_3 \oplus h_3 \oplus h_2, u_1 \oplus h_1 \oplus h_3)\\ \end{align*}

復元の確認 - XOR ベース

復元の際は、3 つのシェアを XOR することで秘密情報ababを取得できます。

v1⊕v2⊕v3=(u1⊕h1⊕h3)⊕(u2⊕h2⊕h1)⊕(u3⊕h3⊕h2)=(u1⊕u2⊕u3)⊕(h1⊕h1)⊕(h2⊕h2)⊕(h3⊕h3)=u1⊕u2⊕u3⊕0⊕0⊕0=u1⊕u2⊕u3=ab\begin{align*} v_1 \oplus v_2 \oplus v_3 &= (u_1 \oplus h_1 \oplus h_3) \oplus (u_2 \oplus h_2 \oplus h_1) \oplus (u_3 \oplus h_3 \oplus h_2)\\ &= (u_1 \oplus u_2 \oplus u_3) \oplus (h_1 \oplus h_1) \oplus (h_2 \oplus h_2) \oplus (h_3 \oplus h_3)\\ &= u_1 \oplus u_2 \oplus u_3 \oplus 0 \oplus 0 \oplus 0\\ &= u_1 \oplus u_2 \oplus u_3\\ &= ab \end{align*}

このように、PRSS を使って通信内容をランダム化することで、MPC の安全性を高めることができます。

PRSS の流れ

PRSSの流れ s=31 q=256
===== PRSS（疑似乱数秘密分散）の流れ =====


60行の折りたたみ
ステップ1: 各パーティが乱数を生成
パーティ1が生成した乱数: 15
パーティ2が生成した乱数: 26
パーティ3が生成した乱数: 181


ステップ2: 各パーティから他のパーティへ乱数を送信
パーティ1からパーティ2へ乱数 15 を送信
パーティ2からパーティ3へ乱数 26 を送信
パーティ3からパーティ1へ乱数 181 を送信


ステップ3: 各パーティがPRSSシェアを計算
パーティ1のPRSSシェア: 90 = (15 - 181) mod 256
パーティ2のPRSSシェア: 11 = (26 - 15) mod 256
パーティ3のPRSSシェア: 155 = (181 - 26) mod 256


PRSSシェアの合計 (mod 256): 0
  検証: (90 + 11 + 155) mod 256 = 0


===== 秘密値の分散と計算 =====


ステップ4: 秘密値を設定し、加法型シェアを生成
元の秘密値: 31
加法型シェア: s1=138, s2=70, s3=79
  検証: (138 + 70 + 79) mod 256 = 31


ステップ5: 各パーティが加法型シェアとPRSSシェアを組み合わせてマスク
パーティ1のマスク済みシェア v1: 228 = (138 + 90) mod 256
パーティ2のマスク済みシェア v2: 81 = (70 + 11) mod 256
パーティ3のマスク済みシェア v3: 234 = (79 + 155) mod 256


===== 複製型秘密分散法への変換 =====


ステップ6: 各パーティが自分のマスク済みシェアを送信
パーティPiがマスク済みシェアv_iをパーティP_{i-1}に送信する
パーティ1からパーティ3へマスク済みシェア v1: 228 を送信
パーティ2からパーティ1へマスク済みシェア v2: 81 を送信
パーティ3からパーティ2へマスク済みシェア v3: 234 を送信


送信後、各パーティが保持するマスク済みシェア:
パーティ1が保持するシェア: (v1=228, v2=81)
パーティ2が保持するシェア: (v2=81, v3=234)
パーティ3が保持するシェア: (v3=234, v1=228)


複製型秘密分散法の形式:
P1: (v1, v2) = (u1 + prss1, u2 + prss2)
P2: (v2, v3) = (u2 + prss2, u3 + prss3)
P3: (v3, v1) = (u3 + prss3, u1 + prss1)


===== シェアから秘密値の再構築 =====


ステップ7: 各パーティのペアで秘密値を再構築
パーティ1とパーティ2による再構築: 31 (等しいか: True)
  使用したシェア: [228, 81, 234]
  検証: (228 + 81 + 234) mod 256 = 31
パーティ2とパーティ3による再構築: 31 (等しいか: True)
  使用したシェア: [81, 234, 228]
  検証: (81 + 234 + 228) mod 256 = 31
パーティ3とパーティ1による再構築: 31 (等しいか: True)
  使用したシェア: [234, 228, 81]
  検証: (234 + 228 + 81) mod 256 = 31
PRSSの流れ s=42 q=2147483647
===== PRSS（疑似乱数秘密分散）の流れ =====


60行の折りたたみ
ステップ1: 各パーティが乱数を生成
パーティ1が生成した乱数: 151318656
パーティ2が生成した乱数: 1862866817
パーティ3が生成した乱数: 1594654746


ステップ2: 各パーティから他のパーティへ乱数を送信
パーティ1からパーティ2へ乱数 151318656 を送信
パーティ2からパーティ3へ乱数 1862866817 を送信
パーティ3からパーティ1へ乱数 1594654746 を送信


ステップ3: 各パーティがPRSSシェアを計算
パーティ1のPRSSシェア: 704147557 = (151318656 - 1594654746) mod 2147483647
パーティ2のPRSSシェア: 1711548161 = (1862866817 - 151318656) mod 2147483647
パーティ3のPRSSシェア: 1879271576 = (1594654746 - 1862866817) mod 2147483647


PRSSシェアの合計 (mod 2147483647): 0
  検証: (704147557 + 1711548161 + 1879271576) mod 2147483647 = 0


===== 秘密値の分散と計算 =====


ステップ4: 秘密値を設定し、加法型シェアを生成
元の秘密値: 42
加法型シェア: s1=1776888125, s2=1987674048, s3=530405163
  検証: (1776888125 + 1987674048 + 530405163) mod 2147483647 = 42


ステップ5: 各パーティが加法型シェアとPRSSシェアを組み合わせてマスク
パーティ1のマスク済みシェア v1: 333552035 = (1776888125 + 704147557) mod 2147483647
パーティ2のマスク済みシェア v2: 1551738562 = (1987674048 + 1711548161) mod 2147483647
パーティ3のマスク済みシェア v3: 262193092 = (530405163 + 1879271576) mod 2147483647


===== 複製型秘密分散法への変換 =====


ステップ6: 各パーティが自分のマスク済みシェアを送信
パーティPiがマスク済みシェアv_iをパーティP_{i-1}に送信する
パーティ1からパーティ3へマスク済みシェア v1: 333552035 を送信
パーティ2からパーティ1へマスク済みシェア v2: 1551738562 を送信
パーティ3からパーティ2へマスク済みシェア v3: 262193092 を送信


送信後、各パーティが保持するマスク済みシェア:
パーティ1が保持するシェア: (v1=333552035, v2=1551738562)
パーティ2が保持するシェア: (v2=1551738562, v3=262193092)
パーティ3が保持するシェア: (v3=262193092, v1=333552035)


複製型秘密分散法の形式:
P1: (v1, v2) = (u1 + prss1, u2 + prss2)
P2: (v2, v3) = (u2 + prss2, u3 + prss3)
P3: (v3, v1) = (u3 + prss3, u1 + prss1)


===== シェアから秘密値の再構築 =====


ステップ7: 各パーティのペアで秘密値を再構築
パーティ1とパーティ2による再構築: 42 (等しいか: True)
  使用したシェア: [333552035, 1551738562, 262193092]
  検証: (333552035 + 1551738562 + 262193092) mod 2147483647 = 42
パーティ2とパーティ3による再構築: 42 (等しいか: True)
  使用したシェア: [1551738562, 262193092, 333552035]
  検証: (1551738562 + 262193092 + 333552035) mod 2147483647 = 42
パーティ3とパーティ1による再構築: 42 (等しいか: True)
  使用したシェア: [262193092, 333552035, 1551738562]
  検証: (262193092 + 333552035 + 1551738562) mod 2147483647 = 42