SPDZと秘密分散値による算術MPC

ブールMPCはビット（XOR/AND）を扱います。算術MPCは整数または体の要素を扱い、加算と乗算を直接サポートします。機械学習や統計のアプリケーションに適しています。

値x ∈ Z_pは、x = x_1 + x_2 + ... + x_n mod pとして分散されます。分散された値の加算は無料です。各参加者が自分のシェアをローカルで加算するだけで、通信は必要ありません。

シェア[a]と[b]を乗算するために、参加者はc_t = a_t·b_tを満たすBeaverトリプル（[a_t], [b_t], [c_t]）を事前に分配しておきます。オンラインでの乗算には、1ラウンドの通信を使用します。

SPDZ（Damgårdら、2012年）は「Somewhat Homomorphic Encryption-based Distributed Zero-Knowledge」の略です。オフラインフェーズではSHEを使って認証付きトリプルを生成します。オンラインフェーズでは加法的シェアによる高速な評価を行います。

各シェアにはMACが付随します。MAC(x_i) = α·x mod pで、αはグローバルな秘密鍵です。これにより、悪意のある参加者が検知されずに自分のシェアを改ざんすることを防ぎます。

SPDZのオフラインフェーズでは、Somewhat Homomorphic Encryption（BGV/BFV）を使用します。参加者は準同型乗算によってシェアを乗算し、認証付きBeaverトリプルを生成します。このフェーズは計算量が大きい一方、並列化できます。

トリプル（[a],[b],[c]）と入力[x],[y]がある場合、d=x-aとe=y-bを公開します（マスクされているため情報は漏洩しません）。その後、[x·y] = [c] + d·[b] + e·[a] + d·eを計算します。通信は1ラウンドで済みます。

MASCOTはSHEによるオフライン処理をOT extensionに置き換え、小さな体に対してより高速にトリプルを生成します。2者間SPDZでは、オフライン処理にMASCOTを使う方式が一般的です。

複数の病院が、診療記録を共有せずに患者の平均年齢を計算します。各病院はデータを算術シェアとして符号化します。SPDZが合計と件数を評価し、参加者が知るのはその比率だけです。

SPDZ-2k（Cramerら、2018年）は、機械学習に適した固定小数点演算のためにZ_{2^k}へ拡張されています。MP-SPDZライブラリでは、LAN上の2者間で毎秒100万回の乗算というベンチマーク結果が得られています。

算術MPCにおけるBeaver乗算トリプルの目的は何ですか。

算術MPCは、Z_p上の加法的シェアを使用します。加算は無料で、乗算には1ラウンドで処理できるBeaverトリプルを使用します。SPDZは悪意のある攻撃者への安全性のためにMACを追加します。MASCOTはOTを使ってトリプルを高速に生成します。MP-SPDZによって、これらの技術を実用化できます。