SPDZ
概要
最も主要な実装の一つ
アクティブな攻撃者の存在がいても秘密計算を行うことができる
$ (n-1)/nのアクティブな攻撃に対して UC (Universal Composability)セキュアである
アクティブな攻撃 : コントロール権の支配
2者間以上の参加者に対応
オフラインフェーズとオンラインフェーズで構成される
オフラインフェーズで準備
オンラインでの計算内容に非依存
事前に乗算計算に必要なパーツを作成する
信頼できるディーラーが行う
オンラインフェーズで計算の実行
乗算で使用する素材の計算にSHEを使用する
SPDZコンパイラとVMで動く
高級言語からバイトコードに変換
VMで計算をMPCで実行する
関連プロトコル
BDOZ
TinyOT
MiniMAC
MASCOT
SPDZ-2
https://gyazo.com/bb16208c4d906a11d675ea23536fcd9c
詳細
任意の有限体に対して計算を行える
プレイヤー同士はセキュアな$ point-to-pointチャネルで結ばれている必要がある
$ shareの構成
$ P_iのもつ$ xの$ share
$ (x_i, \gamma(x)_i)
$ x = x_1+x_2+...+x_n
$ \alpha x = \gamma(x) = \gamma(x)_1 + \gamma(x)_2 + ... +\gamma(x)_n
$ \alphaは共有秘密鍵
$ \gamma(x)_iは$ MAC
$ \gamma(x)_iは線形関数
$ \gamma(x+y)_i = \gamma(x)_i + \gamma(y)_i
$ \alpha \gamma(x)_i = \gamma(\alpha x)_i
$ shareは線型性をもつ
$ \langle x \rangle + \langle y \rangle = \langle x+y \rangle
$ (x_i, \gamma(x)_i) + (y_i, \gamma(y)_i) = (x_i + y_i, \gamma(x)_i + \gamma(y)_i) = (x_i + y_i, \gamma(x+y)_i)
$ \beta \langle x \rangle = \langle \beta x \rangle($ \betaは定数 )
$ \alpha (x_i, \gamma(x)_i) = (\alpha x_i, \alpha \gamma(x)_i) = (\alpha x_i, \gamma(\alpha x_i))
$ z = kx + y の計算が正しく行われたかの検証 ($ kは定数 )
$ \gamma(z) = \alpha zであれば正しい
$ \because \gamma(z) = \gamma(z)_1 + ... + \gamma(z)_n
$ = \gamma(kx+y)_1 + ... + \gamma(kx+y)_n
$ = k\gamma(x)_1 + \gamma(y)_1 + ... k\gamma(x)_n + \gamma(y)_n
$ = k \sum_i \gamma(x)_i + \sum_i \gamma(y)_i
$ = k \gamma(x) + \gamma(y)
$ = \alpha k x + \alpha y
$ = \alpha (kx + y) = \alpha z
$ \alphaは計算終了まで明かされない
$ SPDZでは乗算に$ Beaver's ~ Trickを利用
乗算：$ \langle x \rangleと$ \langle y \rangleから$ \langle z \rangle = \langle xy \rangleを求める
$ c = abなる定数$ a, b, cの$ share$ \langle a \rangle , \langle b \rangle , \langle c \rangle を用意する
$ a, b, cは$ x,yに非依存
$ P_iは$ x_i - a_iと$ y_i - b_iを計算しブロードキャストする
各パーティはブロードキャストされた値を元に手元で$ x-a, y-bを復元できる
$ x-a = \sum_i (x_i - a_i)
$ y-b = \sum_i (y_i - b_i)
$ P_iは$ z_i = c_i + (x-a)b_i + (y-b)a_iとして$ \langle z \rangleを得る
ある一つのパーティ$ P_kが$ x-aと$ y-bの積を自分のシェアに加える
$ z_k = c_k + (x-a)b_k + (y-b)a_k + (x-a)(y-b)
$ \sum_i z_i = c + (x-a)b + (y-b)a + (x-a)(y-b) = xy = z
$ Beaver's ~ Trickにより加算と定数倍のみで乗算の機能を実現
$ shareの線形性を保持したまま乗算を行う $ \longrightarrow$ MACを機能させることが可能
$ \langle a \rangle , \langle b \rangle , \langle c \rangleを事前に用意する前処理を行うことで高速な乗算を実現
暗号化と復号
秘密情報の空間は有限体$ \mathbb{F}_{p^k}
暗号文の空間は剰余環$ \mathbb{Z}^N
$ pk, sk: 秘密情報の暗号化に用いる公開鍵と、復号のための秘密鍵
$ pk, skは次のように生成される
$ a \in A_q と$ s, e \in D_{Z^N ,s} を用意する
$ a, s, eは同じ空間のものとして扱う
$ b \leftarrow (a \cdot s) + (p \cdot e)
$ pk \leftarrow (a, b)
$ sk \leftarrow s
$ skは生成後$ shareとして分配される
$ sk_i = (s_{i,1}, s_{i,2})($ P_iの持つシェア )
$ s = $ s_{1,1} + ... + s_{n,1}
$ s \cdot s = s_{1,2} + ... + s_{n,2}
$ Enc_{pk}(m, r) = ct
公開鍵$ pkと乱数$ rにより秘密情報$ mを暗号文$ ctに変換する関数
$ Enc_{pk}(m, r) = ctの暗号化アルゴリズム
暗号化の対象$ m
乱数$ rを$ ParamGen(1^\kappa, M)より得る
$ ParamGen(1^\kappa, M)
乱数など各種パラメータを生成する関数
$ rを$ (u, v, w)にパースする $ (r = u+v+w)
$ c_0 \leftarrow (b \cdot v) + (p \cdot w) + m
$ c_1 \leftarrow (a \cdot v) + (p \cdot u)
$ ct \leftarrow (c_0, c_1, 0)を返す
以下の議論で$ rは重要でないので省略して$ Enc_{pk}(m) = ctと書く
$ Dec_{sk}(ct) = m
秘密鍵$ skにより暗号文$ ctから秘密情報$ mを復元する関数
$ Dec_{sk}(ct) = mの復号アルゴリズム
復号の対象$ ct = (c0, c1, c2)
$ m = c0 − s \cdot c1 − s \cdot s \cdot c2 ~~ mod ~~ p
$ Enc_{pk}, ~ Dec_{sk}は単写である
暗号文上の演算は次のように定義される
$ ct_1 = (c_{10}, c_{11}, c_{12})
$ ct_2 = (c_{20}, c_{21}, c_{22})
加法（＋）
$ ct_1 + ct_2 = (c_{10}+c_{20}, c_{11}+c_{21}, c_{12}+c_{22})
乗法（・）
$ ct_1 \cdot ct_2 = (c_{10} \cdot c_{20}, ~ c_{11} \cdot c_{20} + c_{10} \cdot c_{21}, ~ -c_{11} \cdot c_{21})
ただし、乗法は第３要素$ c_{i2} = 0の場合のみ定義される（準同型の制約）
次の性質を満たす
$ Dec_{sk}(Enc_{pk}(m_1) + Enc_{pk}(m_2)) = m_1 + m_2
$ Dec_{sk}(Enc_{pk}(m_1) \cdot Enc_{pk}(m_2)) = m_1 \cdot m_2
加法について証明（途中）
$ Dec_{sk}(ct_1 + ct_2) = Dec_{sk}((c_{10}+c_{20}, c_{11}+c_{21}, c_{12}+c_{22})) \\ = c_{10} + c_{20} - s \cdot (c_{11}+c_{21}) - s \cdot s \cdot (c_{12}+c_{22})
乗法について証明（途中）
$ Dec_{sk}(ct_1 \cdot ct_2) = Dec_{sk}((c_{10} \cdot c_{20}, ~ c_{11} \cdot c_{20} + c_{10} \cdot c_{21}, ~ -c_{11} \cdot c_{21})) \\ = c_{10} \cdot c_{20} - s \cdot (c_{11} \cdot c_{20} + c_{10} \cdot c_{21}) - s \cdot s \cdot (-c_{11} \cdot c_{21})
$ Distributed ~ Decryption ~ Protocol
各パーティ$ P_iの秘密鍵$ s_iを公開せずに復号を行うプロトコル
各パーティ$ P_iは暗号文$ ct = (c_0, c_1, c_2)に対して以下を計算する
$ v_i = \begin{cases} c_0 - (s_{i,1} \cdot c_1) - (s_{i,2} \cdot c_2) ~ (i=1) \\ -(s_{i,1} \cdot c_1) - (s_{i,2} \cdot c_2) ~ (i = 2,3,...,n)\end{cases}
$ t_i = v_i + p \cdot r_i ($ r_iは乱数 )
パーティ集合$ Sに含まれるパーティのみが復号して良い場合
各パーティ$ P_iが$ t_iを$ P_j \in Sに送信する
受け取ったパーティは$ t^{\prime} = t_1+...+t_nを計算する
$ m^{\prime} \leftarrow Dec_{sk}(t^{\prime} ~ mod ~ p)として復号結果を得る
$ Reshare ~ Protocol
秘密情報である値$ mのシェアを生成する手順
$ mを所有するパーティが$ ct_m = Enc_{pk}(m)をブロードキャストする
各パーティ$ P_iがローカルで乱数$ f_iを生成する
各$ P_iは$ ct_{f_i} = Enc_{pk}(f_i)をブロードキャストする
全パーティは$ ct_{m+f} = ct_m + ct_f = ct_m + \sum_i ct_{f_i}を計算する
全パーティは$ m+f = Dec_{sk_1,...,sk_n}(ct_{m+f})を得る
$ m+fを用いてシェアを作る
$ P_1のシェアを$ m_1 = (m+f)-f_1とする
$ i \neq 1なる$ P_iのシェアを$ m_i = -f_iとする
必要であれば$ mのフレッシュな暗号文$ ct^{\prime} = Enc_{pk}(m+f)-ct_fを生成する
フレッシュな暗号文 : 一度も乗算が行われていない状態の暗号文
$ Beaver's ~ Trickに用いる$ \langle a \rangle , \langle b \rangle , \langle c \rangleの生成手順
事前仮定
$ \alpha: 共有秘密鍵
$ ct_{\alpha} = Enc_{pk}(\alpha)
$ c = ab
$ \langle a \rangleの生成
各パーティ$ P_iがローカルで乱数$ a_iを生成する
各$ P_iは$ ct_{a_i} = Enc_{pk}(a_i)をブロードキャストする
各$ P_iは$ ct_{\alpha a} = ct_{\alpha} \cdot ct_{a} = ct_{\alpha} \cdot \sum_i ct_{a_i}を計算する
$ Reshare(ct_{\alpha \cdot a})を実行する
各$ P_iは$ \gamma_i(a) = (\alpha a)_iを得る
各$ P_iは$ (a_i, \gamma_i(a))として$ \langle a \rangleを得る
$ \langle b \rangleも同一の手順により得られる
$ \langle c \rangleの生成
$ ct_c = ct_a \cdot ct_bを計算する
$ Reshare(ct_c)を実行する
各$ P_iは$ c_iを得る
$ cに対するフレッシュな暗号文$ ct^{\prime}_cを得る
各$ P_iは$ ct_{\alpha c} = ct_{\alpha} \cdot ct^{\prime}_cを計算する
フレッシュな暗号文を用いることで乗算回数を一回までに抑えている
$ Reshare(ct_{\alpha c})を実行する
各$ P_iは$ \gamma_i(c) = (\alpha c)_iを得る
各$ P_iは$ (c_i, \gamma_i(c))として$ \langle c \rangleを得る
オフラインフェーズ
セキュアな乗算一度につきオフラインフェーズを一回実行する必要がある
オンラインでの計算内容に非依存
制限付き準同型暗号 (Somewhat Homomorphic Encryption) をベースとしている
$ Brakerskiのスキームを拡張したもの
プレイヤーの数$ nに対して$ O(n^2/s)の時間計算量
$ sは暗号システムにおけるパラメータ
公開鍵の操作がボトルネックとなっている
3 人のプレイヤーで 64-bit 乗算を一回行うためのオフラインフェーズの実行時間は 13 ms
オンラインフェーズ
プレイヤーの数$ nに対して$ O(n)の時間計算量
3 人のプレイヤーで 64-bit 乗算を一回行った時の実行時間は 0.05 ms
SPDZ-2のアーキテクチャ
高級言語の中身
https://gyazo.com/bef99af843ff8bb3911c0a6c4cc5f50f
VMでの実行
https://gyazo.com/45151fdd5660684024483ca55446ed6a
参考動画
https://www.youtube.com/watch?v=N80DV3Brds0&list=PLXF_IJaFk-9BFn8M-dsEm5x3-5Cvji3V9&index=12
https://www.youtube.com/watch?v=Ce45hp24b2E
https://www.youtube.com/watch?v=0mIqn8TqzmA
参考文献
Web
What is SPDZ? Part 1: MPC Circuit Evaluation Overview
Bristol Cryptography Blog
The SPDZ Protocol, Part1
Morten Dahl
スライド
Multi Party Computation: From Theory to Practice
Nigel P. Smart
論文
Multiparty Computation from Somewhat Homomorphic Encryption
Ivan Damgard
Valerio Pastro
Nigel Smart
Sarah Zakarias
Secure Computation for Machine Learning With SPDZ
Valerie Chen, et al.