秘密分散ベースのMPCプロトコルSPDZ

最近のECDSAの閾値署名のペーパー読んでたら、まずSPDZ（スピーズ）について理解しておく必要がありそうだったので、秘密分散ベースのMPCプロトコルであるSPDZの仕組みについてまとめてみる。

秘密分散とは？

ある要素aを持っていた場合、それをa = a1 + a2という関係を満たすようランダムに分割する。そしてa1をAさんに、a2をBさんに与える。AさんもBさんもaの値自体については知らないが、協力して値を合算すればaが分かる。この時分割された断片a1やa2をシェアと呼び、シェアを集めると元の秘密の値が分かる仕組みを秘密分散と呼ぶ。

シークレット値をシェアに変換する方法はいくつかあって、↑のようにa = a1 + a2と加算する方法もあれば、a = a1 * a2となるような乗算的な方法や、シャミアの秘密分散法のように多項式を利用して予め指定した閾値分だけシェアを集めればシークレット値を復元できるような方法もある。

※ 上記のようにあるシークレット値aが全ての参加者間で秘密分散されていることを示すのに＜a＞という表記を使用する。

秘密分散法を使った秘密計算

この秘密分散を利用して秘密計算を行うプロトコルの１つがSPDZで、演算回路の共同計算を可能にするMPCプロトコルになる。

といっても分かりづらいので、もう少しかいつまんで言うと、↑のように秘密分散のシェアを入力として使って、そのシェアに対して加算や乗算を行うことで、情報を秘匿したまま演算を行い、その結果を集めて復元すると秘密の値に対して演算したのと同じ結果を復元することができる。つまり秘密計算ができる。さらに加算と乗算ができるということは、計算したい内容を加算と乗算の組み合わせによる（ANDゲート、XORゲート、NOTゲートなどの任意の論理ゲートで構成される）回路として表現できる、つまり任意の関数を計算することができる。

ちなみに秘密計算を実現する方法としては、秘密分散法以外にも↓の方法などがある。

Garbled circuitを使う方法
二者間でプライベート入力を介してトラストレスに機能を共同評価可能な暗号プロトコル。評価する関数はBoolean circuitとして記述する。
準同型暗号を使う方法
完全準同型暗号を使う方法

SPDZは加法型の秘密分散方式（↑のa = a1 + a2パターン）を採用しており、この方式でどのように加算、乗算がサポートされるのか見ていこう。

加算

加算は簡単だ。シークレット値a, bがあり、そのシェアをそれぞれ ${a_i, b_i}$ とし各参加者が保持していると仮定する。

各参加者はローカル環境で ${a_i + b_i}$ を計算できる。 ${a = \sum_i a_i , b = \sum_i b_i}$ かつ ${\sum_i a_i + \sum_i b_i = \sum_i (a_i + b_i)}$ であるため、各参加者が計算した値 ${a_i + b_i}$ はa + bの秘密分散値とも言える。

そのため各参加者からそれぞれ ${a_i + b_i}$ を集めるとa + bの値が分かる。

またこの他、ある値αをシェア ${a_i}$ に乗算すると、 ${\sum_i αa_i = α\sum_i a_i}$ であるため、各参加者はαaのシェアを持つという性質もある。

上記のように加法型の秘密分散値は線形特性があるので、こういった演算を通信を必要せずに行えるのがメリットになる。

乗算

乗算は加算より複雑になる。シークレット値x, yがあり、そのシェアをそれぞれ ${x_i, y_i}$ とし各参加者が保持していると仮定すると、乗算のゴールはシェア ${x_i, y_i}$ を入力としてx * yを計算すること。

乗算を行うには ${x_i, y_i}$ 以外に、c = a * bの関係を満たす３つの要素a, b, cを用意し各参加者はそのシェア ${(a_i, b_i, c_i)}$ を持つ。

各参加者は、上記のシェアを使って、 ${x_i - a_i}$ と ${y_i - b_i}$ をブロードキャストする。
全員の１が揃うと(x - a), (y - b)が分かる。
参加者は２のデータを使って、 ${z_i = c_i + (x - a)b_i + (y - b)a_i}$ を計算することができる。
3のシェアを集めると ${\sum_i z_i = c + (x - a)b + (y - b)a}$ が計算できる。
４に対して (x - a) * (y - b)を加算すると ${\sum_i z_i + (x - a) * (y - b) = c + (x - a)b + (y - b)a + (x - a) * (y - b) = xy}$

となり、x * yが得られる。つまり、 ${z_i}$ はx * yのシェアであると考えることができ各参加者はそれを持っていることになる。

↑のようにc = a * bの関係を満たす要素（トリプル）を使えば、秘密分散データの乗算が可能になる。つまり、多数のトリプルを用意すれば、秘密分散データに対して多数の乗算を行うことができ、どんな算術回路も計算できるということ（※ただしトリプルは再利用できず、乗算毎にそれぞれ異なるトリプルを用意する必要がある。再利用すると秘密に関する情報が明らかになるため）。

トリプルは秘密分散データとの依存性は無く、評価する回路（関数）とも無関係なので、回路を評価する前に事前に準備しておくことができる。

SPDZプロトコルの概要

SPDZは↑の加算型の秘密分散法を利用して入力が共有されるプロトコルで、オフラインフェーズ（前処理フェーズとも呼ぶ）とオンラインフェーズの２段階のフェーズで構成される。

オフライン（前処理）フェーズ

オフラインフェーズでは↓を行う（オフラインとあるけど、厳密にオフラインではなく参加者間の通信は行われる）。

入力や評価対象の関数とは無関係に、↑の乗算に使用するc = abの関係を満たす乗算トリプルを生成する。オリジナルのペーパーでは準同型暗号を使用。
回路に入力を提供する際に各参加者が使用するランダム値rの生成。

各参加者は生成した以下の値を保持する。

多数のトリプルのシェア
${r = \sum_i r_i}$ となるランダム値rのシェア ${r_i}$

※ 上記に加えて、出力値が正しく計算されているか最後に検証するために使用するMAC鍵に同意し、そのシェアを各参加者は保持する。この段階でMACの鍵のデータを知るユーザーはおらず（いたら値の偽造ができるので）、各参加者はそのシェアを持つのみ。

オンラインフェーズ

オンラインフェーズは、オフラインフェーズで用意したトリプルを使って、実際に回路を評価する。

入力値を秘密分散

回路を評価する前に、最初に回路への入力を用意する。入力を提供するのがPiでその入力値を ${X_i}$ とすると、そのまま提供すると秘密計算にならないので、以下の計算を行って ${X_i}$ のシェアを作る。

Piはオフラインフェーズで生成されたランダム値ｒをオープンする（最初からPiが入力を提供すると分かっている場合、オフラインフェーズで実行可能）。これはオフラインフェーズでシェア ${r_i}$ を持つ参加者がそれをPiに送ることで、全部集まればPiがそれを合計してrを計算できる。
Piは ${ε = X_i - r}$ を計算してブロードキャストする。
各参加者は自身が持つrのシェア ${r_i}$ とεを使って ${X_i}$ のシェア ${x_i = r_i + ε}$ を計算する。

SPDZでは↑のようにして入力値のシェアを作成する。

回路の評価

入力値のシェアが作成できたら↑の加算や、オフラインフェーズで生成したトリプルを使って乗算の操作ができるようになるので、入力シェアを使って回路を評価する。実際の計算は↑の加算・乗算の組み合わせ。

各参加者による計算が終わったら、各参加者が持っている出力値のシェアを集めれば最終的な出力値を入手できる。

MACを利用したデータの正しさの検証

出力値が正しいのは各参加者が正しく計算した場合のみで、悪意ある参加者が意図しない計算をしていた場合、出力値は意図する値ではなくなる。このため、最終的な出力値を計算した際に、それが正しく計算されたものかどうか検証する仕組みが必要になる。この検証のためにMACを使用する。詳しくは追ってないけど、各参加者は結果をオープし、MAC鍵のシェアの組み合わせに対して線形なコミットメントを作成し、共有する。その後MACの鍵をオープンして、結果の整合性を検証するっぽい。

以上がSPDZの概要。SPDZが発表されて以降、オフラインフェーズを中心にさまざまな最適化や改善の提案があり、いろんなバージョンのSPDZが存在する。

Develop with pleasure!

福岡でCloudとかBlockchainとか。