SPDZはsomewhat準同型暗号(以下SHE)を使うことで高い効率性と安全性を実現したマルチパーティ計算プロトコルです。

SHEによる効率的なプリプロセスフェーズの実現。
semi-honest secureよりも高い、active secureの効率的な実装。
active secureなので、n個のパーティのうちn-1がcorruptされていてもUC安全性が保障される。

のような性質を持っています。これについて解説します。

はじめに
- 加算と乗算
- MACでの認証
サブプロトコル
プリプロセス（オフライン）フェーズ
まとめ
参考文献

はじめに

ここから登場する記号は太字の場合はすべて $\mathbf{v} \in (\mathbb{F _ {p ^ k}}) ^ s$ である有限体上の $s$ 次元ベクトル $\mathbf{v}$ です。そうでなければ $v \in \mathbb{F _ {p ^ k}}$ である有限体の要素 $v$ です。

SHEとは加算と乗算に対して準同型性を持つが、計算回数が制限されたものです。SHEのなかでもBVというスキームを活用します。BVでは暗号文のまま十分な数と加算と1回の乗算を行うことが出来ます。暗号文での乗算が1回を超すと、正しく復号できなくなることに注意してください。

SPDZではSHEの準同型性を生かし、平文を暗号化し、暗号文の状態でブロードキャストや計算を行います。この時、

暗号文なので平文の情報は漏れない。
SHEの準同型性によって暗号文のまま計算ができる。

となります。こうして、プリプロセスフェーズで必要な情報を各パーティが使用可能な状態にしておくことで、オンラインフェーズでの計算量を減少させます。

加算と乗算

オンラインフェーズでも述べますが、加算と乗算の方法について説明します。秘密分散方式として、加法的秘密分散を使っています。 $m$ を $m=m _ 1+\dots+m _ n$ を満たすような $m _ i$ に分割します。このことを $m=\Sigma _ i m _ i$ と書き、各 $m _ i$ のことをシェアということにします。

例えば $m=10$ として、 $(m _ 1,m _ 2,m_ 3,m _ 4)=(1,5,2,3)$ とすると、

$m=\Sigma _ i m _ i=1+5+2+3=10$

　が明らかです。更にそのまま加算を行うこともできます。 $P _ 1$ が $m$ に $5$ を足したい場合は、 $m _ 1$ に $5$ を足します。実際、

$m=\Sigma _ i m _ i=(1+5)+5+2+3=15$

　なので加算できています。

乗算の場合はMultiplication Triplesを使います。Multiplication Triplesについては以下のサイトが参考になります。

acompany.tech

ここではMultiplication Triplesのことをトリプルと呼ぶことにします。

MACでの認証

さて、SPDZには二つの値表現が登場します。SPDZではシェアをパーティの持つ秘密鍵やグローバル鍵で認証してあげることで、不正を検出します。この認証に使う認証子をMAC（Message Authentication Code）と呼ぶことにします。

$\langle \mathbf{m} \rangle$ はMACで認証されたシェアです。この値は単一の値を表現しているわけではなく、以下のような状態を表します。

f:id:ATen:20200712130212p:plain — <m>の表す状態

$Private$ は各パーティ $P _ i$ が個人で所持している値です。 $Public$ はすべてのパーティが参照できる値です。

$\delta$ はMACの条件を維持するために利用します。詳しい役割についてはオンラインフェーズで述べます。
$\ \mathbf{m _ 1} ,\mathbf{m _ 2},\dots,\mathbf{m _ n}$ は計算は各パーティ $P _ i$ の所持するシェアです。
$\gamma ( \mathbf{m} ) _ i$ はその計算における不正を検証するためのMACです。

なお、このMACは $\alpha$ がないとチェックできないので計算が全て終わってからでないと誰かが不正したことを検出できません。

$[ \mathbf{m} ]$ は秘密鍵 $\beta _ i$ で認証された値です。この値も単一の値を表現しているわけではなく、以下のような状態を表します。論文や図では〚〛を使用していますが、texで出す方法が分からないので以降は[]で代用しています。

f:id:ATen:20200712130704p:plain — [m]の状態

$\ \mathbf{m _ 1} ,\mathbf{m _ 2},\dots,\mathbf{m _ n}$ は計算は各パーティ $P _ i$ の所持するシェアです。
$(\gamma ( \mathbf{m} ) ^ i _ 1,\dots,\gamma ( \mathbf{m} ) ^ i _ n) _ {i=1,\dots,n}$ はその計算における不正を検証するためのMACです。

この状態では、ブロードキャストしあってシェアを集めることで $\beta _ i$ に認証された $\alpha$ を復元できます。例えば、下の図の赤く囲われた部分をブロードキャストしあって集めることで $\beta _ 1$ に認証された $\alpha$ を復元できます

f:id:ATen:20200712130208p:plain — [m]の表す状態２

$\beta _ 1$ を持っている $P _ 1$ なら値の正しさを検証できます。 $P _ 1$ 以外の $P_ i$ についても同様です。

$\langle \mathbf{m} \rangle$ との違いは $\alpha$ なしに $\mathbf{m}$ を手にいられることです。そのため、オンラインフェーズで $\alpha$ を公開するより前に値が必要な時に利用されています。

この表現はMACの認証に使用するグローバル鍵 $\alpha$ の公開を遅らせるために存在しています。各パーティ $P _ i$ が $\alpha$ がなければMACを確認することができないませんが、 $\alpha$ があると偽造できてしまいます。偽装を防ぐために各パーティの秘密鍵 $\beta _ i$ で認証させて、 $\alpha$ の公開を遅らせます。

サブプロトコル

プリプロセスフェーズでは同じような処理を繰り返し行う部分があるため、それを一般化したものを定義します。 $PBracket(\mathbf{m} _ 1,\dots,\mathbf{m} _ n,e _ \mathbf{m})$ のようになっていますが、 $\mathbf{m} _ 1,\dots,\mathbf{m} _ n$ は各パーティ $P _ i$ のローカルに保持する値であることに注意してください。

平文のゼロ知識証明

任意の平文に対する正しい暗号文を共有するために以下の処理を行います。これを $PoPK(\mathbf{m _ i})$ としましょう。

各パーティ $P _ i$ はメッセージ空間から $\mathbf{m _ i}\in (\mathbb{F _ {p ^ k}}) ^ s$ を選ぶ。各パーティの生成した平文の和は $\mathbf{m}=\Sigma _ i \mathbf{m _ i}$ となる。
各パーティ $P _ i$ が $e _ {\mathbf{m _ i}} \leftarrow Enc _ {pk}(\mathbf{m _ i})$ のように暗号化してブロードキャストする。
各パーティ $P _ i$ は暗号文 $e _ {\mathbf{m _ i}}$ に対応する平文 $\mathbf{m _ i}$ を知っていることを証明する。
各パーティ $P _ i$ は $e _ {\mathbf{m }}\leftarrow e _ {\mathbf{m _ 1}}\boxplus \dots \boxplus e _ {\mathbf{m _ n}}$ を計算する。

暗号文 $e _ {\mathbf{m _ i}}$ に対応する平文 $\mathbf{m _ i}$ を知っていることを証明する。

この処理により $e _ {\mathbf{m _ i}}$ を正しく共有し、 $e _ {\mathbf{m }}$ を入手できます。

PAngle

$PAngle$ は任意の平文に対するシェアを生成するために以下の処理を行います。これを $PAngle(\mathbf{m} _ 1,\dots,\mathbf{m} _ n,e _ \mathbf{m})$ としましょう。

$PAngle(\mathbf{m} _ 1,\dots,\mathbf{m} _ n,e _ \mathbf{m})=\langle \mathbf{m} \rangle$

暗号文 $e _ {\mathbf{m}}$ と、平文 $\mathbf{m}$ のシェアを入力に $\langle \mathbf{m} \rangle$ を生成する。各パーティ $P _i$ はグローバル鍵 $\alpha$ の暗号文 $e _ {\alpha}$ と $e _ {\mathbf{m}}$ の積を計算し、 $e _ {\mathbf{m} \cdot \alpha}$ を計算します。 $e _ {\mathbf{m} \cdot \alpha}$ は $\alpha$ で認証したMACの暗号文であり、これをReshareすればMACを共有できます。暗号文での乗算回数は1回です。

PBracket

$PBracket$ は任意の平文に対するシェアを生成するために以下の処理を行います。これを $PAngle(\mathbf{m} _ 1,\dots,\mathbf{m} _ n,e _ \mathbf{m})$ としましょう。

$PBracket(\mathbf{m} _ 1,\dots,\mathbf{m} _ n,e _ \mathbf{m})=[ \mathbf{m} ]$

　暗号文 $e _ {\mathbf{m}}$ と、平文 $\mathbf{m}$ のシェアを入力に $[\mathbf{m} ]$ を生成します。各パーティ $P _i$ は秘密鍵 $\beta _ i$ の暗号文 $e _ {\beta _ i}$ と $e _ {\mathbf{m}}$ の積を計算し、 $e _ {\gamma _ i}$ を計算します。 $e _ {\gamma _ i}$ は $\beta _ i$ で認証したMACの暗号文であり、これをReshareすればMACを共有できます。暗号文での乗算回数は1回です。

Reshare

$Reshare$ は暗号文からシェアを生成するプロトコルです。

$Reshare(e _ \mathbf{m},enc)=\langle \mathbf{m} \rangle\ and\ e' _ \mathbf{m}$

　暗号文 $e _ {\mathbf{m}}$ に対応する平文 $\mathbf{m}$ のシェアを秘密分散します。第二引数に $NewCiphertext$ のコマンドを入力されると、平文 $\mathbf{m}$ を暗号化しているが暗号文 $e _ {\mathbf{m}}=e' _ {\mathbf{m}}$ のような暗号文 $e' _ {\mathbf{m}}$ も同時に生成します。暗号状態での乗算回数は0回です。

$Reshare$ は乗算を1回も行わないので、 $PAngle$ や $PBracket$ と組み合わせても乗算回数が1回を超えることがありません。

プリプロセス（オフライン）フェーズ

サブプロトコルを活用して平文の情報を一切明かすことなく、プロトコルの初期化やトリプルとペアの共有を行うことができます

具体的にはオンラインフェーズで利用する

$\langle \mathbf{a} \rangle,\langle \mathbf{b} \rangle,\langle \mathbf{c} \rangle,\langle \mathbf{r} \rangle,\langle \mathbf{f} \rangle,\langle \mathbf{g} \rangle,\langle \mathbf{h} \rangle$

$[\mathbf{r}],[Diag(\alpha)],[\mathbf{t}],[\mathbf{e}]$

を生成します。 $Diag(\alpha)$ とは $\alpha$ を $s$ 個を並べた $(\alpha,\dots,\alpha)$ を表します。 $\alpha$ は $s$ 次元ベクトルでないので、 $s$ 次元に拡張しています。

プリプロセスは初期化、ペアの生成、トリプルの生成の3段階に分けることが出来ます。

初期化

まずトリプルやペアの生成のために、鍵を共有します。具体的には各パーティ $P _ i$ が $[Diag(\alpha)$ ]と $\beta _ i$ を持っている状態にします。

暗号化のためにプロトコルは公開鍵 $pk$ をセットする。
各パーティ $P _ i$ はメッセージ空間から $\beta _ i\in \mathbb{F _ {p ^ k}}$ を選ぶ。
$\mathbf{m _ i}:=Diag(\alpha _ i)$ とし、 $PoPK(Diag(\alpha _ i))$ を行う。各パーティ $P _ i$ は $e _ {\alpha _ i}$ と $\alpha _ i$ を所持した状態になる。（ここでだけ $e$ の添え字は $Diag(\alpha _ i)$ とならない）
$e _ {\alpha _ i}$ と $Diag(\alpha _ i)$ を使い、 $PBracket(Diag(\alpha _ 1),\dots,Diag(\alpha _ n),e _ \alpha)$ を行う。プロトコルは $[ Diag(\alpha) ]$ を手に入れる。

トリプル

Multiplication Tripleを共有することを考えます。オンラインフェーズで一回の乗算ごとに2セットのトリプル

$\langle \mathbf{a} \rangle,\langle \mathbf{b} \rangle,\langle \mathbf{c} \rangle\\ \langle \mathbf{f} \rangle,\langle \mathbf{g} \rangle,\langle \mathbf{h} \rangle$

を消費します。消費するだけ生成しておく必要があります。 $\langle \mathbf{f} \rangle,\langle \mathbf{g} \rangle,\langle \mathbf{h} \rangle$ の必要性についてはオンラインフェーズで述べます。

トリプル $\langle \mathbf{a} \rangle,\langle \mathbf{b} \rangle,\langle \mathbf{c } \rangle$ は $\mathbf{c}=\mathbf{ab}$ を満たし、 $\langle \mathbf{f} \rangle,\langle \mathbf{g} \rangle,\langle \mathbf{h} \rangle$ も同様に $\mathbf{h}=\mathbf{fg}$ を満たします。

$\mathbf{m _ i}:=\mathbf{a _ i}$ とし、 $PoPK(\mathbf{a _ i})$ を行う。各パーティ $P _ i$ は $e _ {\mathbf{a _ i}}$ と $\mathbf{a _ i}$ を所持した状態になる。
$e _ {\mathbf{a _ i}}$ と $\mathbf{a _ i}$ を使い、 $PAngle(\mathbf{a} _ 1,\dots,\mathbf{a} _ n,e _ \mathbf{a})$ を行う。 $\langle \mathbf{a} \rangle$ を手に入れる。
ここまでの処理を $\mathbf{m _ i}:=\mathbf{b _ i}$ に対しても行う。（実際には $\mathbf{a}$ と平行に行っている）
$e _ \mathbf{c } = e _ \mathbf{a} \boxtimes e _ \mathbf{b}$ を計算する。
$e _ \mathbf{c}$ を入力に $Reshare(e _ \mathbf{m},NewCiphertext)$ を呼び出す。
$e _ {\mathbf{c }}$ と $\mathbf{c _ i}$ を使い、 $PAngle(\mathbf{c} _ 1,\dots,\mathbf{c} _ n,e _ \mathbf{c})$ を行う。 $\langle \mathbf{c} \rangle$ を手に入れる。

$5$ で $Reshare$ を $NewCiphertext$ としているのは $e _ \mathbf{c}$ が $4$ の時点で1回乗算された暗号文となっているためです。そのまま $6$ で $PAngle$ を使うと $e _ \mathbf{c}$ の乗算回数が2回になってしまいます。よって、 $e' _ {\mathbf{c}}$ に変換して乗算回数をリセットする必要があります。

ペア

ペアというのは以下の乱数の組です。オンラインフェーズで乱数として活用します。

$\langle \mathbf{r} \rangle,[\mathbf{r}]$

$\mathbf{m _ i}:=\mathbf{r _ i}$ とし、 $PoPK(r _i)$ を行う。各パーティ $P _ i$ は $e _ {\mathbf{r _ i}}$ と $\mathbf{r _ i}$ を所持した状態になる。
$e _ {\mathbf{r _ i}}$ と $\mathbf{r _ i}$ を使い、 $PAngle(\mathbf{r} _ 1,\dots,\mathbf{r} _ n,e _ \mathbf{r})$ を行う。プロトコルは $\langle \mathbf{r} \rangle$ を手に入れる。
$e _ {\mathbf{r _ i}}$ と $\mathbf{r _ i}$ を使い、 $PBracket(\mathbf{r} _ 1,\dots,\mathbf{r} _ n,e _ \mathbf{r})$ を行う。プロトコルは $[ \mathbf{r} ]$ を手に入れる。