はじめに

この記事は、セキュアマルチパーティ計算（secure multi-party computation：MPC）技術の入門に適した書籍である「A Pragmatic Introduction to Secure Multi-Party Computation [1]」を参考にした、MPC 技術解説の４回目の記事となります。今回の内容は６章の内容と対応しています。

https://acompany.tech/privacytechlab/mpc-multi-party-computation-1/

https://acompany.tech/privacytechlab/mpc-multi-party-computation-2/

https://acompany.tech/privacytechlab/mpc-multi-party-computation-3/

今回は、malicious モデルで安全なMPCプロトコルのうち代表的なものを紹介し、その仕組みを簡単に説明していく内容となっています。

コンテンツの構成

本記事では、malicious モデルで安全なMPC プロトコルをいくつか紹介します。そのための下準備として、コミットメントやゼロ知識証明と呼ばれる仕組みについて紹介します。続いて、malicious モデルで安全な代表的なMPCプロトコルとして、cut-and-choose・GMW compiler・BDOZ・SPDZ を紹介します。

それぞれのプロトコルの方針は次のようになっています。

cut-and-choose ：Yao's GC で生成される回路（Garbled Circuit）をチェックすることで正しい回路を用いて計算する。
GMW compiler：ゼロ知識証明を用いて、送信されたメッセージがプロトコルに従って計算されたものであることを保障する。メッセージがプロトコルに従って計算されていればsemi-honest 安全なプロトコルが秘密情報を洩らすことはないので、これを実行する。
BDOZ, SPDZ：メッセージ認証コードを用いて、share が改竄されていないことを保障する。

下準備

コミットメント

コミットメントは簡単に言えば、「送信する情報を確定させること（コミット）」と「確定された情報を公開すること（オープン）」が可能なプロトコルです。本記事では、コミットメントは相手の情報を見てから、それに合わせた行動を取るような不正を防ぐために使われます。

コミットメントの定義は次の通りです[1]。

定義：コミットメント

コミットメントは、次の$\mathcal{F}^{Comm}$ の機能を安全に実現する暗号プロトコルである。

パラメータ：

２人の参加者：送信者を$S$ 、受信者を$R$ とする。$S$ は文字列$s\in \{0,1\}^n$ を持つ。

機能：

$S$ は$\mathcal{F}^{Comm}$ に$s$ を送り、$\mathcal{F}^{Comm}$ は"commited" メッセージを$R$ に送る
その後、$S$ が$\mathcal{F}^{Comm}$ に"open" メッセージを送ると、$\mathcal{F}^{Comm}$ は$s$ を$R$ に送る

コミットメントは次の２つの性質を満たします。

Hiding：受信者は送信者によって明らかにされるまではコミットした値について何も知らない
Binding：送信者はコミットした後に値の選択を変更できない

コミットメントはランダムオラクルを仮定すると簡単に実現できます。具体的には、次のようにすれば良いです。

$x$ をコミット：ランダムに$r\in \{0,1\}^\kappa$ を選び、$y=H(x||r)$ を公開する。
オープン：単に$x$ と$r$ を公開する。 $H(x||r)$ を計算することで公開された値がコミットされた値であったことを確認できる。

<aside>📎 $r$ の長さが$\kappa$ で固定であることがわかっているので、$x'||r'=x||r$ なる$x',r'$ は $x'=x, r'=r$ のみです。</aside>

ゼロ知識証明

ゼロ知識証明（zero-knowledge (ZK) proof）とは、「証明者が$C(x) = 1$ となる$x$ を知っているならば、検証者に$x$ に関するそれ以上の情報を与えずに、そのことを確信させることができる」というプロトコルです。本記事では、ゼロ知識証明はGMW compiler でメッセージの正当性を証明するために使われています。

ゼロ知識証明の定義は次の通りです[1]。

定義：ゼロ知識証明

ゼロ知識証明は、次の$\mathcal {F}^{zk}$ の機能を実現する暗号プロトコルである。

パラメータ：

２人の参加者：証明者を$P$ 、検証者を$V$ とする

機能：

$P$ は$\mathcal{F}^{zk}$ に$(C,x)$ を送る．ただし、$C:\{0,1\}^n\rightarrow \{0,1\}$ で$x\in \{0,1\}^n$ 。
$C(x)=1$ ならば、$\mathcal{F}^{zk}$ は$V$ に$({\bf proven},C)$ を送信する．
$C(x)=0$ ならば、$\mathcal{F}^{zk}$ は$V$ に終了記号$\perp$ を送信する．

例

ゼロ知識証明のイメージを掴むため、例を紹介します。

２つの素数$p,q$ に対して$n=pq$ であるとします。また、$n$ は公開されていて、証明者$P_1$ は$p$ を知っているとします。このとき、$P_2$ に具体的な$p,q$ の値を伝えることなく$P_1$ が$p$ を知っていることを証明するのが目標です。

関数$\mathcal G$ を、自然数$m$ を入力とし「$m\neq 1, m\neq n$ かつ、$n$ を$m$ で割った余りが$0$ であること」を判定する関数だとします。$P_1,P_2$ はこの関数$\mathcal G$ を共有し、$P_1$ が秘密の入力$p$ を与えるという形で秘密計算を行います。

もし秘密計算の結果がTrue であれば、$P_2$ は$p$ の実際の値を知らずとも、$P_1$ が$p$ を知っていることを確信することができます。

Garbled Circuit (GC)によるゼロ知識証明の構成

ここでは、ゼロ知識証明の構成方法を紹介します。

ゼロ知識証明はmalicious 安全な計算の特殊ケースであるため、後述するcut-and-choose などを用いて構成することが可能です。しかし、cut-and-choose では多くのGC を必要とし、多くのコストがかかるという問題点があります。一方、Jawurek, Kerschbaum, Orlandi [2] によるJKOプロトコルは、たった1つのGC でゼロ知識証明を実現することができます。

JKOプロトコルのアイデアは、生成した１つのGC を評価とチェックの両方に使用することです。

GC を開く（GC の生成に使用した乱数を全て明らかにする）ことで、そのGC が回路$C$ に対応するものであるかを確認することができます。このようにGC をチェックすることで、GC に不正がないか確認することができます。

一般の回路を考える場合、評価用の回路を開くとGC 生成者の秘密の入力が明らかになってしまいます。しかし、ゼロ知識証明プロトコルでは、検証者は秘密の入力を持ちません。したがって、検証者が回路を暗号化すると、生成されたGC を評価とチェックの両方に使用することができます。

証明者$P_1$ が公開されている関数$\mathcal C$ に対し${}^\exists w:\mathcal C(w)=1$ であることを証明したいとします。このとき、JKOプロトコルは次のように進行します：

検証者$P_2$ は$\mathcal C$ を計算するGC を生成して送信する。
$P_1$ はOT (Oblivious Transfer) を用いて、入力$w$ に対応するワイヤラベルを取得する。
$P_1$ は回路を評価して、出力のワイヤラベルを得る。このワイヤラベルをコミットする。
$P_2$ はGC を開き、$P_1$ はそれが正しく生成されたかどうかをチェックする。$P_1$ はGC が正しく生成されていれば出力ワイヤラベルのコミットメントをオープンする。
$P_2$ は$P_1$ がコミットした値が、GC の１に対応する出力ワイヤラベルであったなら、証明を受け入れる。

ここからは、このプロトコルの安全性について簡単に述べます。

$P_1$ がステップ３でコミットメントを生成した時点ではGC はまだ開かれていません。したがって、$P_1$ が$\mathcal C$ の出力を１にする入力を知らない場合、プロトコルのこのステップで出力１に対応するワイヤラベルを予測することは困難です。このことから、プロトコルは不正な証明者に対して安全です。また、証明者はGC が正しく生成されたことが確認された後にのみその結果を明らかにするので、このプロトコルは不正な検証者に対して安全です。

メッセージ認証コード（Message Authentication Code, MAC）

メッセージ認証コードは、メッセージが改竄されていないことを確認するための符号です。本記事で扱うBDOZ やSPDZ は秘密分散にMAC を組み込んだものとなっています。

MAC の大まかな仕組みとしては次の通りです。

MAC 生成アルゴリズムによって、メッセージに対応するMAC を生成する。
鍵を知らない攻撃者はいくつかのメッセージに対応するMAC を取得したとしても、それらと異なるメッセージに対応するMAC を生成できない。
したがって、攻撃者はメッセージを改竄したときに、そのメッセージに対応するMAC を生成できない。メッセージの受信者は改竄されたメッセージ（とそれに対応していないMAC）を受け取ったとき、受け取ったメッセージに対応するMAC を生成し、受け取ったMAC と比較することによってメッセージが改竄されたことがわかる。

メッセージ認証コードを用いるメッセージ認証は次のように定義されます[7]。

定義：メッセージ認証

メッセージ認証$MAC=(\mathcal{K},\mathcal{M},\mathrm{S},\mathrm{V})$とは、二つの集合と二つのアルゴリズムの組である。ここで、

鍵生成空間 $\mathcal K$: 秘密鍵$k$ の集合
平文空間 $\mathcal M$: 平文$m$ の集合
MAC 生成アルゴリズム $\mathrm{S}$: 秘密鍵$k\in \mathcal K$, 平文$m\in \mathcal M$ を入力としてとり、メッセージ認証子$\tau$ を出力するアルゴリズム。この試行を$\tau\leftarrow\mathrm S(k,m)$ と書く。
MAC 検証アルゴリズム $\mathrm{V}$: 秘密鍵$k\in \mathcal K$, 平文$m\in \mathcal M$, 認証子$\tau$ を入力としてとり、認証子の正しさを判定するアルゴリズム。この試行を$b\leftarrow \mathrm V(k,m,\tau)$ と書く。（$b\in\{0,1\}$ であり、$b=1$ のとき正しいと判定されたとする。）ただし、$\mathrm V$ は${}^\forall k\in \mathcal K,{}^\forall m\in \mathcal M, \tau\leftarrow \mathrm S(k,m)$ に対し、$\mathrm V(k,m,\tau)=1$ を満たす。

である。

MAC の安全性

メッセージ認証の安全性はEUF-CMA ゲームというゲームを通じて定義されます[7]。

EUF-CMA ゲームは次のようなものです[7]。

EUF-CMAゲームは攻撃者$A$ とチャレンジャー$C$ の間で行われるメッセージ認証方式 $MAC=(\mathcal K,\mathcal M,\mathrm S, \mathrm V)$ の安全性を試すゲームである。ゲームは次の手順で行われる。

$C$ は鍵空間$\mathcal K$ から一様ランダムに鍵$k$ を選ぶ。
$A$ は平文$m$ を$C$ に送り、対応する認証子$\tau\leftarrow \mathrm S(k,m)$ （鍵を持つ$C$ はこれを計算できる）を受け取る。平文 $m$ の選び方は$A$ の戦略による。$A$ は合計$q$ 回まで質問 (query) を送ることができる。
$A$ は、平文と認証子の組$(m^,\tau^)$ を出力する。
もし、$m^*$ が$q$ 回の質問で$C$ に送った平文のいずれとも異なり、$\mathrm V(k,m,\tau)=1$ を満たすならば、$A$ の勝ちと定義する。

$A$ が、メッセージ認証方式$MAC$ に対するEUF-CMA ゲームに勝つ確率を、$A$ の$MAC$ に対するアドバンテージと呼び、秘密鍵のサイズを$n(=\log|\mathcal K|)$ として、$\mathrm{Adv}_{A,MAC}^{\mathrm{euf-cma}}(q,n)$ と書きます。

ここで、メッセージ認証の安全性は次のように定義されます[7]。

定義：メッセージ認証の安全性

任意の（計算量やメモリ量を制限しない攻撃者$A$ に対して、あるとき、$\mathrm{Adv}_{A,MAC}^{\mathrm{euf-cma}}(q,n)=2^{-n}$ であるとき、メッセージ認証方式$MAC$ は$q$ 回までの質問に対して（情報理論的に）安全と呼ぶ。

MPCプロトコル

ここからは、malicious モデルで安全である代表的なプロトコルの仕組みを解説していきます。

cut-and-choose

cut-and-choose はYao's GC をベースにしたmalicious モデルで安全なプロトコルです。多くのGarbled Circuit (GC) を生成し、正しく生成されているかをチェックするGC と評価に使用するGC に分けることで不正なGC によって情報が洩れることを回避します。

Yao's GC の問題点

Yao's GC はmaliciousモデルで安全ではありません。

具体的には、次のようなことが起こりえます。

$P_1$ は$P_2$ に秘密計算を行う回路$C$ に対応するGarbled Circuit を送ります。malicious な$P_1$ は$P_2$ が計算することに同意していない別の回路のGC を生成して送るかもしれませんが、$P_2$ はそのGC が正しいことを確認する方法がありません。意図的に生成されたGC の出力は$P_2$ の秘密情報（例えば、$P_2$ の入力全体）を漏らす可能性があります。

主要なアイデア

Yao's GC の問題点を回避するために、$P_2$ に$P_1$ が生成したGC が正当なものか確認する機会を与えます。具体的には、次のようにします。

$P_1$ が計算することに合意した回路$C$ に対する多数のGarbled Circuit をそれぞれ独立に生成し、それを$P_2$ に送る。
$P_2$ はこれらの回路の中からランダムな部分集合を選び、$P_1$ に選んだ回路を「開く」ように要求する。回路を「開く」とは、回路の生成に使用したすべての乱数を明らかにすることを指す。
$P_2$ は、開かれたGC が、合意された回路$C$ から正しく生成されたものであることをチェックする。 GC の生成に使用された乱数が分かれば、それを用いて実際に$C$ からGC を構築するなどして正しさをチェックできる。
開かれたすべての回路が正しいことが確認された場合、$P_2$ はプロトコルを続行する。開かれた回路がすべて正しい場合、$P_2$ は開かれていない回路も正しいと推測できる。開かれた回路の中に誤りがあれば、$P_2$ は$P_1$ が不正を行ったことを知り、プロトコルを中止することができる。
開かれていない回路を、標準的なYao's GC のように評価する。開いた回路は、その秘密がすべて明らかになっているため、秘密計算には使用できない。

出力の生成

当然、開かれた全ての回路が正しいときでも、開かれていない回路の中に不正な回路が入っている場合があります。よって、評価するGC の出力が全て一致しなかった場合にどのように行動するかについて考えておく必要があります。一見、このような場合には中止すれば良いように思いますが、これには次に説明する問題点があります。

例えば、$P_1$ が$s$ 個のGC を生成して、$P_2$ はそれぞれの回路を確率$\frac{1}{2}$ でチェックするとします。このとき、$P_1$ が1つの回路だけを不正に生成した場合、（無視できない）確率$\frac{1}{2}$ でその回路はチェックに選ばれず、評価回路の1つとなります。この場合、$P_2$ は評価回路から一貫性のない出力を得ることになり、これを見て$P_2$ はプロトコルを中止します。

ここで、$P_1$ の不正な回路が、$P_2$ の入力の最初のビットが１の場合に誤った答えを出すように設計されているとします。このとき、$P_2$ は、その入力の最初のビットが１の場合にのみ、誤った出力を得ます。

よって、$P_2$ が誤った出力を得てプロトコルを中止すると、$P_2$ の入力の最初のビットが漏洩することになります。（$P_1$ は乱数を公開する際にどの回路がチェックされたかわかるので、その中止がチェックによるものか評価によるものかを判定できます。）

したがって、$P_1$ が不正行為を行っていることが$P_2$ にとって明らかであるにもかかわらず、入力情報の漏洩を避けるために、問題がないかのように続行しなければならないという状況になります。

このような状況に対応するために、cut-and-choose プロトコルでは、評価された回路の出力のうち最頻のものを採用します。このとき、不正な回路の出力を秘密計算の結果として採用するのは「評価された回路のうち不正な回路の出力が最頻」かつ「チェックした回路は全て正当」である場合に限られ、これはパラメータ（生成するGC の数と回路のチェック確率）次第で無視できる確率となります。このことについては、「具体的なパラメータ」の節で詳しく説明します。

入力の一貫性

cut-and-choose プロトコルでは、$P_2$ は複数のGC を評価します。複数の回路があるためmalicious な参加者が異なるGC に異なる入力を使おうとする可能性があるという、新たな問題が発生します。例えば、各回路ごとにOT で$P_1$ から$P_2$ へワイヤラベルを送信するようにしていると、$P_2$ が回路ごとに異なる入力を選択することができます。また、$P_1$ は回路への入力として、入力の値に対応するワイヤラベルを$P_2$ に与えますが、ここで異なる値に対応するワイヤラベルを選択することが可能です。

$P_2$ の入力に一貫性を持たせることは簡単です。$P_1$ は入力に対応するワイヤラベルを$P_2$ にOT で送信しますが、全ての回路の入力ワイヤラベルを一回のOT で送信すれば、$P_2$ は異なる入力を選択できません。

$P_1$ の入力に一貫性を持たせるひとつの方法は、参加者が$((x,r),y)\mapsto (\mathcal F(x,y),H(x,r))$ を評価するという方法です [3] 。ここで、$H$ は2-univarsal ハッシュ関数です。

<aside>📎 2-univarsal とは任意の$z\neq z'$ について$\Pr[H(z)=H(z')]=\frac{1}{2^\ell}$ を満たすことを言います。ただし、$\ell$ は$H$ の出力bit 長です。</aside>

このアイデアは、$P_1$ にまず（暗号化した）入力をコミットメントさせ、次に$P_2$ がランダムな$H$ を選択して、暗号化する回路を決定するというものです。$P_1$ の入力は$H$ が選ばれる前に（コミットメントによって）固定されているため、入力に矛盾があると$H$ からの出力が異なり、$P_2$ がそれを検出することができます。$H$ の出力から$x$ の入力の情報を洩らさないようにするため、$P_1$ は追加の入力として乱数$r$ を加えており、$r$ が十分に長ければ$x$ の情報は洩れません。

選択的中止[4]

たとえ、全てのGC が正当なものであったとしても、$P_1$ が入力ワイヤラベルを$P_2$ に送信するためのOT で誤ったワイヤラベルを送信することで、不正を行おうとする可能性があります。

例えば、$P_1$ はOT への入力を選択して、$P_2$ の最初の入力ビットが１のときに、$P_2$ が使い物にならないワイヤラベルを受け取るようにすることができます（そして、$P_2$ の中止をもって、最初の入力bit を洩らすことになります）。このような攻撃は、選択的中止（selective abort）攻撃と呼ばれます。

選択的中止攻撃を防ぐために$P_2$ は入力の任意のビット$b$ について、次の操作を行います。

$\bigoplus_{i=1}^s b_i=b$ なる$b_1,\dots,b_s$ をランダムに選び、$P_2$ の（そのビット部分の）入力とする。 $b_1,\dots,b_{s-1}$ をランダムに選び、$b_s = b \oplus \left(\bigoplus_{i=1}^{s-1} b_i\right)$ とすれば、$2^{s-1}$ 通りから一様な確率で$b_1,\dots,b_s$ が選択される。
回路$C$ における$P_2$ が$b$ を入力するワイヤを、新しい$P_2$ の入力$b_1,\dots,b_s$ のXOR を取る回路に変更する。

このとき、$P_2$ の$n$ ビットの入力$y$ に対する中止確率を$p$ 、$n$ ビットの入力$y'(\neq y)$ に対する中止確率を$p'$ とすると、$|p'-p|\leq n2^{-s+1}$ となることがいえます。

これは、$P_2$ のある入力ビットを決定する$s$ 個の入力ワイヤを考えたときに、

１つの入力ワイヤについて、OT の２つの入力が不正である場合 $P_2$ が必ず不正な入力を受け取るため、$P_2$ の入力に関わらず中止確率は１
$1\leq j<s$ 個の入力ワイヤについて、それぞれOT の１つの入力が不正である場合 $j$ 個の入力ワイヤの値は、$P_2$ の入力とは独立であるため、$P_2$ の入力に関わらず中止確率は一定（$1-2^{-j}$）
$s$ 個の入力ワイヤについて、それぞれOT の１つの入力が不正である場合 OT の不正でない入力に対応する値のXOR を取った値が$P_2$ の入力値に一致しない場合は$P_2$ は必ず中止する OT の不正でない入力に対応する値のXOR を取った値が$P_2$ の入力値に一致する場合、（$s-1$ 個の正当な値を送信することに成功したなら、XOR が$P_2$ の入力値に一致するという条件から残り1 個は必ず正当な値を送信することになるので）中止確率は$1-2^{-s+1}$

すなわち、$P_2$ の１ビットの入力に対応する部分で中止確率の差は最大$2^{-s+1}$ となります。これが$n$ ビット分あるので、中止確率の差は最大$n2^{-s+1}$ となります。

したがって、$s$ を十分大きくすれば、$P_2$ の中止をもって$P_2$ の入力を知ることは困難になります。

（入力が$y$ なのか$y'(\neq y)$ なのかさえ、無視できる確率でしか判別できない）

このような入力の変換を行うと$P_2$ の入力長は$s$ 倍になってしまいますが、[4] では入力長を$\max(4n,8s)$ に減らす方法も紹介されています。

具体的なパラメータ

cut-and-choose のメカニズムには、２つの主要なパラメータが存在します。

複製係数（replication factor） $P_1$ が生成しなければならないGC の数
チェック確率 cut-and-choose の段階でチェックされるGC が選ばれる確率

cut-and-choose プロトコルでは、適切なセキュリティを提供するために必要な複製係数を最小化することが一つの目標となります。

上述したcut-and-choose プロトコルでは、攻撃者がセキュリティを破る唯一の方法は評価回路の大部分を不正な回路とし、かつチェックされる回路の全てを正当な回路にすることです。攻撃者の目標は次のような抽象的なゲームで表現できます。

プレイヤーは$\rho$ 個のボールを用意するそれぞれに色がついていて、色は赤か緑赤は不正な回路を表す緑は正当な回路を表す
$c$ 個のボールをランダムに選び、チェックするチェックしたボールのいずれかが赤であるならプレイヤーはゲームに敗北する全て緑なら次へ
チェックされなかったボールのうち過半数が赤であるならプレイヤーはゲームに勝利し、そうでないなら敗北する

ここで、任意のプレイヤーが$2^{-\lambda}$ より良い確率でゲームに勝つことができないように最小の$\rho$ と最適な$c$ を見つけることが目標です。

shelat とShen [3] の分析によると、最小の複製係数は$\rho \approx 3.12\lambda$、最適なチェックする回路の数は、$c=0.6\rho$ です。

GMW(Goldreich-Micali-Wigderson) compiler

GMW compiler はゼロ知識証明を用いてプロトコルが正しく実行されたことの証明を組み込むことで、semi-honest 安全なプロトコルをmalicious 安全なプロトコルに変換する方法です[5]。

アイデア

GMW compiler では、メッセージを送信する際に、そのメッセージが「プロトコルを正当に実行した結果」であることをゼロ知識証明を用いて証明します。

ゼロ知識証明に失敗した場合はプロトコルを中止することにします。このとき、プロトコルが中止されずに終了したなら、プロトコル$\pi$ が正常に実行されたということになります。また、ゼロ知識証明では検証者の入力がないため、証明が成功するかどうかは検証者の入力に依存しません。よって、中止によって検証者の入力が洩れる心配はありません。したがって、$\pi$ がsemi-honest 安全であるなら、新たに生成されたプロトコルはmalicious 安全です。

次に、ゼロ知識証明で使用する回路$C$ をどのように生成するかを考えます。ここでは、簡単のため２パーティとします。

プロトコル$\pi$ では、参加者$P_i$ が次に送信するメッセージを計算する関数$\pi_i$ が指定されています。この$\pi_i$ は$P_i$ の入力、ランダムテープ、$P_i$ が受信した全てのメッセージの３つを入力に持ちます。

$P_1$ から$P_2$ にメッセージ$t$ が送信されたとします。また、$P_1$ の入力を$x$ 、ランダムテープを$r$、　受信した全てのメッセージを$T$ とします。

このとき、$P_1$ が正しくプロトコルを実行しているなら、$t$ は$\pi_1$ に適切な入力$(x,r,T)$ を与えたときの計算結果であるはずです。

回路$C$ は直感的には、$\pi_1(x,r,T)$ を計算して$t$ と一致するかを判定する関数です。しかし、一致の判定に加えて、これらの入力が正当な入力であることも保障する必要があります。入力について、重要なのは次の事項です。

$T$ は「$P_1$ が受信した全てのメッセージ」であり、これは「$P_2$ が送信した全てのメッセージ」（つまりお互いにとって既知）。
$x,r$ 以外の入力で関数の出力を１にすることが（殆ど）できないようになっている必要がある。
$x$ については、プロトコルの実行中に変化することはない。そこで、一貫性を持つようにする必要がある。
ランダムテープ$r$ を恣意的に生成することで不正が行われる可能性がある。

1 は$P_1$ が入力として$T$ を与える必要はなく、$T$ が与えられているものとして回路$C$ を生成すればよいことを表しています。

2, 3 については$P_1$ が$(x,r)$ をコミットメントしておき、「$P_1$ の入力$(x,r)$ とコミットメントを"open" して$P_2$ が得るメッセージが一致するかどうかを判定する関数」とのAND をとって出力するようにすればよいです。このようにすることで、$x,r$ 以外の入力では関数の出力を１にすることが難しくなることに加え、$x$ の一貫性が確保されます。

4 については$P_2$ の生成したランダムテープを$r'$ として、$r'$ を公開し$r\oplus r'$ を$\pi_1$ を計算するためのランダムテープとして用いることで対処します。$P_1$ が$r'$ を見てからランダムテープを決定しては意味がないので、$r$ がコミットメントされてから$r'$ を公開するようにします。

semi-honest な２パーティプロトコル$\pi$ に対するmalicious 安全なプロトコル$\pi^*$ は次のようになります[1]。

パラメータ：

$\pi = (\pi_1,\pi_2)$ $\pi_b(x,r,T)$ は入力$x$ 、ランダムテープ$r$ 、これまでの記録$T$ に対する参加者$P_b$ の次のメッセージを表す。

プロトコル$\pi^*$ :（$P_1$ の入力を$x_1$ 、$P_2$ の入力を$x_2$ とする）

全ての$b\in \{1,2\}$ について、$P_b$ は乱数$r_b$ を選択し、$(x_b,r_b)$ のコミットメッセージ$c_b$ をオープンメッセージ$\delta_b$ と共に生成する。
全ての$b\in \{1,2\}$ について、$P_b$ は乱数$r'_{3-b}$ （相手のランダムテープのshare）を選んで送信する。
参加者はプロトコルが終了するまで、$b=1$ と$b=2$ を交互に次を繰り返す。これまでのプロトコル$\pi$ におけるメッセージの記録を$T$ とする。ただし、初め$T$ は空である。$P_b$ は次のメッセージ$t=\pi_b(x_b,r_b\oplus r'_b, T)$ を計算して送信する。もし$\pi_b$ の出力が終了なら、$P_b$ も同様に（$\pi_b$ が指定した出力で）終了する。 $P_b$ はプライベート入力$x_b,r_b, \delta_b$ と公開されている回路$C[\pi_b, c_b, r'_b, T, t]$ を持つゼロ知識証明の証明者として動作する。ここで、$C[\pi_b, c_b, r'_b, T, t](x,r,\delta)$ は次のように定義される：コミットメッセージ$c_b$ をオープンメッセージ$\delta$ でオープンした結果が$(x,r)$ に一致し、かつ$t = \pi_b(x,r\oplus r',T)$ である場合、１を返す。相手の$P_{3-b}$ は、ゼロ知識証明の検証が失敗した場合、中止する。

<aside>📎$[\pi_b, c_b, r'_b, T, t]$ は$P_1,P_2$ の間での公開情報であることに注意してください。</aside>

BDOZ(Bendlin-Damgård-Orlandi-Zakarias) 認証

Malicious モデルでも、前回説明したMultiplication Triple と同様に、プロトコルを前処理段階とオンライン段階に分けるアプローチを考えることができます。

適切なMultiplication Triple と次の性質を満たす共有方法があれば、malicious 安全性を確保できます[1] 。

share は加法に関して準同型である（以下、準同型と書く）。
share はmalicious な攻撃者に対して、秘密情報を隠す（以下、秘匿性と書く）。
malicious な攻撃者がいる場合でも、確実にshare から元の情報を復元できる（以下、復元の安全性と書く）。

BDOZ 認証[6] はMAC（メッセージ認証コード）を秘密分散に組み込んだものであり、上記の性質を満たす共有方法です。

$\mathbb{F}$ を体とし、$|\mathbb{F}|\geq 2^\kappa$ （$\kappa$ はセキュリティパラメータ）とします。$K,\Delta\in \mathbb{F}$ を秘密鍵と解釈して、$MAC_{K,\Delta}(x)=K+\Delta \cdot x$ と定義します。

この$MAC_{K,\Delta}$ はOne-Time MAC として知られています [7] 。$MAC_{K,\Delta}$ について、「$K,\Delta$ を知らない参加者が$MAC_{K,\Delta}(x)$ を与えられたときに、$x\neq x'$ であるような$x'$ に対して、有効なMAC $MAC_{K,\Delta}(x')$ を生成できる確率は$1/|\mathbb F|$ である」が成り立ちます。

このことは、次の２つからわかります。

$K,\Delta$ が一様ランダムに選択されているため、点$(K,\Delta)$ は直線$K=-x\cdot \Delta + MAC_{K,\Delta}(x)$ 上に一様に分布している。
もしこのような参加者が$MAC_{K,\Delta}(x')$ を計算できると仮定すると、次のようにして$\Delta$ を計算できる。 $$ (x-x')^{-1}\left( MAC_{K,\Delta}(x)- MAC_{K,\Delta}(x') \right)\\ = (x-x')^{-1}\left(K+\Delta \cdot x - K - \Delta \cdot x' \right)\\ =(x-x')^{-1}\Delta(x-x')=\Delta $$ すなわち、$MAC_{K,\Delta}(x')$ を計算することは$\Delta$ を求めることに対応するが、点$(K,\Delta)$ は直線$K=-x\cdot \Delta + MAC_{K,\Delta}(x)$ 上に一様に分布するため、$\Delta$ を$1/|\mathbb F|$ の確率でしか求められない。

言い換えると、鍵$K,\Delta$ を知らない参加者が$x$ を別の値$x'$ に改竄しようとしたときに、対応する$MAC_{K,\Delta}(x')$ を生成する必要がありますが、このMAC の生成に成功する確率は（計算資源を制限しない参加者でも）無視できるほど小さいです。

BDOZのアイデアは、このOne Time MAC を用いて各パーティのshare を認証することです。

簡単のため、２パーティの場合から説明します。各パーティ$P_i$ は、グローバルMAC キー$\Delta_i$ を生成します。ここで、$[x]$ は、$P_1$ が$x_1,m_1,K_1$ を保持し、$P_2$ が$x_2,m_2,K_2$を保持するshare を表します。ただし、それぞれの数は次を満たします。

$x_1+x_2=x$ ($x$ の加法的なshare )
$m_1=K_2+\Delta_2\cdot x_1 = MAC_{K_2,\Delta_2}(x_1)$*
$m_2=K_1+\Delta_1\cdot x_2 = MAC_{K_1,\Delta_1}(x_2)$*

<aside>📎 *以降説明するように、演算を行うときはその入力が持つMAC値から出力のMAC値を計算できます。しかし、回路に入力を与えるときは「$P_1$ が$x_1$ 、$P_2$ が$K_2,\Delta_2$ を与え、$MAC_{K_2,\Delta_2}(x_1)$ を$P_1$ のみに与える」関数を他のプロトコルで秘密計算するなどの工夫が必要になると思われます。</aside>

次に、この共有メカニズムがMultiplication Triple で要求される特性を満たすことを確認します。

秘匿性：個々の参加者$P_i$ は、1つの加法的なshare である$x_i$ しか持っていないため、$x$ について何も知りません。また、$m_i$ は相手の鍵（これは明らかにされない）を知らなければ$x$ について何も明らかにしません。
復元の正当性： share から元の値を復元する際には、各参加者は自分の$(x_p,m_p)$ を公開します。このとき、両パーティが$x=x_1+x_2$ を知ることができます。ここで、$P_1$ は自分のMAC 鍵を使って$m_2 = MAC_{k_1,\Delta_1}(x_2)$であるかどうかを確認し、そうでない場合は中止します。また、$P_2$ は$m_1$ に対して同様のチェックを行います。なお、このshare を別の値にすることは、One-Time MAC を破壊したことと同義です。
準同型：ここでは、$[x]+[x']$ という加法について考えますが、定数加算・定数倍の準同型についても同様です*。次に、share $[x],[x']$ と$[x+x']$ のBDOZ秘密分散の結果を示します。$[x]$ のshare$P_1$ が保持：$x_1,\; K_1,\; MAC_{K_2,\Delta_2}(x_1)$$P_2$ が保持：$x_2,\;K_2,\;MAC_{K_1,\Delta_1}(x_2)$$[x']$ のshare$P_1$ が保持：$x_1',\; K_1',\; MAC_{K_2',\Delta_2}(x_1')$$P_2$ が保持：$x_2',\;K_2',\;MAC_{K_1',\Delta_1}(x_2')$$[x+x']$ のshare$P_1$ が保持：$x_1+x_1',\; K_1+K_1',\; MAC_{K_2+K_2',\Delta_2}(x_1+x_1')$$P_2$ が保持：$x_2+x_2',\;K_2+K_2',\;MAC_{K_1+K_1',\Delta_1}(x_2+x_2')$次に示すように、$\Delta$ が同じMAC は和について準同型です。 $$ MAC_{K,\Delta}(x)+MAC_{K',\Delta}(x')=MAC_{K+K',\Delta}(x+x') $$ MAC の準同型から、$[x+x']$ のshare は確かに$[x],[x']$ のshare を用いてローカルに計算できます。$[x]+[x']=[x+x']$ となるようにshare の加算を定義すれば、share は加法について準同型となります。

<aside>📎 *加法に関して準同型（$[x+x']=[x]+[x']$ ）ならば、定数倍と定数加算は準同型になります。
定数倍
$[cx]=[(c-1)x+x]=[(c-1)x]+[x] =\dots=c[x]$
定数加算定数$c$ をshare にする方法を事前に決めておく（例えば、$P_1$ のみ$c$ で他は$0$）と、加算に帰着。</aside>

BDOZは、簡単な方法で$n$ 人のパーティに一般化できます。

すべての参加者はグローバルなMAC 鍵を持っている。
単一のshare $[x]$ では、参加者は$x$ の加法的な共有を持ち、各参加者のshare は他のすべての参加者のMAC 鍵で認証される。

すなわち、$P_i$ の$P_j$ のshare に対するMAC の鍵を$K_{i,j}$、$m_{i,j} = MAC_{K_{j,i},\Delta_j}(x_i)$ として、$x=\sum_{k=1}^nx_k$ に対する$P_i$ のshare は$x_i,K_{i,1},\dots,K_{i,n},m_{i,1},\dots,m_{i,n}$ のようになります。

Triple の生成

ここまでで、BDOZ の秘密分散法はMultiplication Triples で求められる３つの性質を満たしていることを確認しました。よって、残る問題はTriple の生成方法です。Triple を用いることで、乗算を加算・定数倍・定数加算を用いて計算することができます。詳細は前回の記事をご参照ください。

引用：③

Triple の愚直な生成方法としては、

各参加者$P_i$ は適当な体の乱数$a_i,b_i$ を$a,b$ の加法的なshare とする。
$P_i$ が入力として$a_i,b_i,K_i,\Delta_i$ を与え、$ab=c$ なる$c$ の加法的なshare $c_i$ と$MAC_{K_{i,j},\Delta_j}(a_i)$ といったMAC を出力として受け取る関数を$\mathcal F$ とする。
$\mathcal F$ を他のmalicious 安全なプロトコルで秘密計算する。

というものが考えられますが、非効率です。

効率的な、ビットのBDOZ share を生成するための方法としては、Tiny-OT [8] で使用されている方法があります。この内容については、ここでは扱いません。

SPDZ(Smart-Pastro-Damgård-Zakarias) 認証

SPDZ 認証[9] はBDOZ 認証と同様の方針を取る方式です。

BDOZ 認証では、$[x]$ の各参加者のshare には、他のすべての参加者のMAC が含まれています。すなわち、BDOZ のshare の構成要素数は、パーティの数に応じて線形に変化してしまいます。一方、SPDZ 認証では各参加者のshare の大きさが一定になります。

まず、２パーティの設定を考えます。主なアイデアは、どちらの参加者にも知られていないグローバルなMAC キー$\Delta$ を持つことです。これは、グローバルな$\Delta = \Delta_1+\Delta_2$ の秘密分散と考えることができます。

SPDZ 認証におけるshare $[x]$ では、$P_1$ は$(x_1,t_1)$ 、$P_2$ は$(x_2,t_2)$ を保持しており、$x_1+x_2=x$、$t_1+t_2 =\Delta\cdot x$ を満たします。このように、参加者は$x$ と$\Delta\cdot x$ の加法的なshare を持っています。

次に、Triple に必要な他の３つの特性を満たすことを示します：

秘匿性：参加者は$x,\Delta\cdot x$ の加法的なshare を持ちますが、これは$x$ について何も情報を与えません。
復元の正当性：プロトコル全体を通して$\Delta$ を秘密にしておくことが重要であるため、参加者に単にshare を公開させることはできません。これは、単にshare を公開すると$\Delta$ を明らかにしてしまうためです。$[x]$ から$\Delta$ を公開せずに元の値$x$ を復元するためにプロトコルは次の３つのフェーズで進行します。参加者は$x_1,x_2$ のみを公開する。これにより、$x$ の（認証されていない）候補値が決まる。$x$ の候補値が実際に正しい場合、次が成り立つ： $$ (\Delta_1\cdot x-t_1)+(\Delta_2\cdot x-t_2)=(\Delta_1+\Delta_2)x-(t_1+t_2)\\ =\Delta\cdot x - \Delta\cdot x = 0 $$ ここで、$P_1$ は$(\Delta_1\cdot x -t_1)$ をローカルに計算することができ、$P_2$ は$(\Delta_2\cdot x -t_2)$ をローカルに計算することができる。このステップでは、$P_1$ は値$(\Delta_1\cdot x -t_1)$ をコミットし、$P_2$ は値$(\Delta_2\cdot x -t_2)$ をコミットする。参加者はこれらのコミットメントをopen し、その合計が０でなければ中止する。もし、参加者がコミットしない場合と、最後に値を送信する参加者が合計を０にするように値を選んで不正を行うことができるため、コミットメントが必要です。この公開手順の安全性については次の通りです。$P_1$ がある値$c$ をコミットするとき、$P_2$ が$-c$ をコミットすることに期待している。（例えば、$P_1$ が$\Delta_1\cdot x - t_1$ をコミットするとき、$P_2$ が$\Delta_2\cdot x - t_2 = -(\Delta_1\cdot x - t_1)$ をコミットすることに期待している。実際に$\Delta_2\cdot x-t_2$ がコミットされていたなら、このコミットによって新しく情報が増えることはない。）このことから、これらのコミットメントの公開は簡単にシミュレートできるため、$\Delta$ についての情報は何も漏れない。malicious な攻撃者が$[x]$ を$x'(\neq x)$ に復元することに成功したと仮定すると、その攻撃者は$\Delta$ を推測できる。例えば、このとき正当な$P_2$ は$\Delta_2\cdot x' - t_2$ を送信し、malicious な$P_1$ は$-(\Delta_2\cdot x - t_2)$ を送信する。 $P_1$ にとっては$\Delta_2\cdot x'-t_2, \Delta_1, x',t_1,x_2$ が既知なので、 $$ \Delta = \frac{(\Delta_2\cdot x' - t_2)+\Delta_1\cdot x' -t_1}{x'-x} $$ のように$\Delta$ を計算することができる。すなわち、$x'(\neq x)$ に復元するとき$\Delta$ を知っていることになりますが、実際には$\Delta$ を無視できない確率で得ることはできません。したがって、不正な値$x'$ に変更される確率は無視できます。
準同型： SPDZ のshare $[x]$ では、参加者のshare は$x$ の加法的秘密分散と$\Delta\cdot x$ の加法的秘密分散からなります。これらはそれぞれ個別に準同型であるため、SPDZ 秘密分散は加算と定数倍を自然に（GMWプロトコルのように）行えます。定数$c$ の加算については次に示すとおりです。 $[x]$ のshare $P_1$ が保持：$x_1,\;t_1$ $P_2$ が保持：$x_2,\;t_2$ それぞれのshare の和：$x_1+x_2=x,\; t_1+t_2=\Delta\cdot x$ $[x+c]$ のshare $P_1$ が保持：$x_1+c,\;t_1+\Delta_1\cdot c$ $P_2$ が保持：$x_2,\;t_2+\Delta_2\cdot c$ それぞれのshare の和： $x_1+c+x_2=x+c,\; (t_1+\Delta_1\cdot c)+(t_2+\Delta_2\cdot c)=\Delta\cdot (x+c)$

SPDZ は$n$ パーティでも同様に、$x$ と$\Delta\cdot x$ の加法的なshare を保持すればよいです。このとき、冒頭で説明した通り、share の大きさは固定となります。

SPDZ share の生成

ここまでで、SPDZ のshare がMutiplication Triples に基づく安全な計算に必要な特性を満たしていることを確認しました。よって、残る問題は、SPDZ形式のMultiplication Triple の生成方法です。

SPDZを最初に紹介した論文[9] では、準同型暗号を用いた方法を提案しています。その後の研究では、効率的な拡張OT に基づく代替技術が提案されています[10] 。これらの内容については、ここでは扱いません。

SPDZ については、以前に記事で紹介しています。SPDZ についてより深く知ることができると思いますので、ぜひご参照ください。

https://acompany.tech/privacytechlab/spdz-1/

https://acompany.tech/privacytechlab/spdz-2/

まとめ

本記事では、Malicious モデルで安全な代表的MPCプロトコルについて述べました。

以下、まとめになります。

プロトコルの基本的な構成要素として、コミットメントとゼロ知識証明を紹介した。コミットメントは「送信する情報を確定させること（コミット）」と「確定された情報を公開すること（オープン）」が可能なプロトコル。ゼロ知識証明は「証明者が所与の関数の出力を１にするような入力を知っていることを、その入力を秘密にしたまま検証者に確信させる」ことが可能なプロトコル。
malicious モデルで安全なプロトコルとして、cut-and-choose・GMW compiler・BDOZ 認証・SPDZ 認証を紹介した。 cut-and-choose ：Yao's GC で生成される回路（Garbled Circuit）をチェックすることで正しい回路を用いて計算する。 GMW compiler ：ゼロ知識証明を用いて、送信されたメッセージが正当に計算されたものであることを保障する。メッセージが正当に計算されていればsemi-honest 安全なプロトコルは安全なので、これを実行する。 BDOZ 認証：メッセージ認証コードを用いて、share が改竄されていないことを保障する。各参加者がそれぞれの鍵で、他の参加者のshare をそれぞれ認証する。 SPDZ 認証：メッセージ認証コードを用いて、share が改竄されていないことを保障する。各参加者は鍵の情報を秘密分散して持つ。

参考文献

[1]

David Evans, Vladimir Kolesnikov, and Mike Rosulek. 2018. "A Pragmatic Introduction to Secure Multi-Party Computation".

[2]

Jawurek, M., F. Kerschbaum, and C. Orlandi. 2013. “Zero-knowledge using garbled circuits: how to prove non-algebraic statements efficiently”. In: ACM CCS 13: 20th Conference on Computer and Communications Security. Ed. by A.-R. Sadeghi, V. D. Gligor, and M. Yung. ACM Press. 955–966.

[3]

shelat, a. and C.-H. Shen. 2011. “Two-Output Secure Computation with Malicious Adversaries”. In: Advances in Cryptology – EUROCRYPT 2011. Ed. by K. G. Paterson. Vol. 6632. Lecture Notes in Computer Science. Springer, Heidelberg. 386–405.

[4]

Lindell, Y. and B. Pinkas. 2007. “An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries”. In: Advances in Cryptology – EUROCRYPT 2007. Ed. by M. Naor. Vol. 4515. Lecture Notes in Computer Science. Springer, Heidelberg. 52–78.

https://eprint.iacr.org/2008/049.pdf

[5]

Goldreich, O., S. Micali, and A. Wigderson. 1987. “How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority”. In: 19th Annual ACM Symposium on Theory of Computing. Ed. by A. Aho. ACM Press. 218–229.

[6]

Bendlin, R., I. Damgård, C. Orlandi, and S. Zakarias. 2011. “Semi-homomorphic Encryption and Multiparty Computation”. In: Advances in Cryptology EUROCRYPT 2011. Ed. by K. G. Paterson. Vol. 6632. Lecture Notes in Computer Science. Springer, Heidelberg. 169–188.

[7]

藤﨑英一郎. 2019. 「I240 暗号理論 2019　共通鍵暗号とメッセージ認証 (1)」.

https://www.jaist.ac.jp/~fujisaki/2019/I240-2019-2.pdf

[8]

Nielsen, J. B., P. S. Nordholt, C. Orlandi, and S. S. Burra. 2012. “A New Approach to Practical Active-Secure Two-Party Computation”. In: Advances in Cryptology – CRYPTO 2012. Ed. by R. Safavi-Naini and R. Canetti. Vol. 7417. Lecture Notes in Computer Science. Springer, Heidelberg. 681–700.

[9]

Damgård, I., V. Pastro, N. P. Smart, and S. Zakarias. 2012b. “Multiparty Computation from Somewhat Homomorphic Encryption”. In: Advances in Cryptology – CRYPTO 2012. Ed. by R. Safavi-Naini and R. Canetti. Vol. 7417. Lecture Notes in Computer Science. Springer, Heidelberg. 643–662.

[10]

Keller, M., E. Orsini, and P. Scholl. 2016. “MASCOT: Faster Malicious Arithmetic Secure Computation with Oblivious Transfer”. In: ACM CCS 16: 23rd Conference on Computer and Communications Security. Ed. by E. R. Weippl, S. Katzenbeisser, C. Kruegel, A. C. Myers, and S. Halevi. ACM Press. 830–842.