【技術】SPDZプロトコル② SPDZの前処理フェーズについて

  • calendar2020.09.23
  • reload2022.10.03
投稿者：R&D
ホーム » 技術 » 【技術】SPDZプロトコル② SPDZの前処理フェーズについて

はじめに

この記事では、秘密分散法をベースにしたマルチパーティ計算(MPC : Multi-party Computation)のプロトコルであるSPDZについて解説します。SPDZは複雑なプロトコルのため、2部構成にして紹介しています。今回の記事はPart 2 になります。

以下の前回のPart 1の記事では、SPDZの概要とオンラインフェーズについて解説しました。

【技術】SPDZプロトコル① SPDZの概要とオンラインフェーズについて

Part 2となるこの記事では、SPDZの前処理フェーズについて解説します。

前処理フェーズの仕組み

前処理フェーズでは、オンラインフェーズで使用する値を生成することが目的です。

オンラインフェーズで使用する値は以下の5種類です。

  • グローバル鍵$\alpha$ のシェア
  • 参加者の秘密鍵$\beta_i$
  • 乱数のシェア$\langle r \rangle, [\![ r ]\!]$
  • 乗算時と出力時に使う値$[\![ t ]\!], [\![ e ]\!]$
  • 乗算トリプル$\langle a \rangle, \langle b \rangle, \langle c \rangle, \langle f \rangle, \langle g \rangle, \langle h \rangle$

今回説明する前処理フェーズでは、上記の値をそれぞれ3つのフェーズに分けて生成します。

  1. 初期化フェーズ
    • $\alpha$ のシェア$,\beta_i$
  2. ペアフェーズ
    • $\langle r \rangle, [\![ r ]\!], [\![ t ]\!], [\![ e ]\!]$
  3. トリプルフェーズ
    • $\langle a \rangle, \langle b \rangle, \langle c \rangle, \langle f \rangle, \langle g \rangle, \langle h \rangle$

各フェーズ内では、4つのサブプロトコルが使用されているため、先にサブプロトコルの説明を行った後に各フェーズについて説明していきます。

それでは、サブプロトコルについて見ていきましょう。

サブプロトコル

平文のゼロ知識証明

平文のゼロ知識証明プロトコル(ZKPoPK)は、各参加者 $P_i$ が生成した暗号文が、本当に$P_i$ が生成したものなのかを証明するために使用します。

ここで、簡単にゼロ知識証明について説明します。例えばAさんが平文$m$ の暗号文$c$ を保持しているとします。このとき、Aさんが第三者のBさんに、暗号文$c$ に対応する平文$m$ を保持していることを、平文$m$ に関する情報を一切漏洩させずに証明することを目指します。

このように、秘密情報を保持していることを第三者に証明する際に、秘密情報に関する情報を一切漏洩せずに証明することをゼロ知識証明といいます。

しかしながら、ZKPoPKのアルゴリズムの詳細は複雑であるため、本記事では割愛いたします。ご興味のある方は、原論文を参照していただければと思います。

再シェア化

再シェア化($\rm Reshare$)は、平文$m$ の暗号文$e_m$ を入力とし、シェア$\langle m \rangle$ と、必要であるならば新たな暗号文$e_m’$ を生成するサブプロトコルです。

数式で表現すると、$\rm Reshare$$(e_m, enc) = \langle m \rangle \ and \ e_m’$ と書けます。

第二引数の$enc$ には二種類の値$\rm NewCiphertext, NoNewCiphertext$ が入ります。この値によって以下の2つの処理を行います。

  • $enc = \rm NewCiphertext$ の場合
    • $\langle m \rangle$ と新たな暗号文$e_m’$ を生成する
  • $enc = \rm NoNewCiphertext$ の場合
    • $\langle m \rangle$ のみ生成する

ここで、なぜ新たな暗号文を生成する仕組みが必要であるかを説明します。実は、前処理フェーズで使用するSHE(制限付き準同型暗号)は、乗算を2回以上行うとエラーが発生します。それを避けるために、一度$e_m$ と等価な新しい暗号文$e_m’$ を生成して、乗算回数をリセットする必要があります。そのため、$enc$ という引数を用意し、必要に応じて新しい暗号文を生成できるようにしています。

以下が詳細な再シェア化のアルゴリズムです。

  1. 各参加者$P_i$ は、$f_i \in (\mathbb{F}_{p^k})^s$ を取得する
    • ただし、$f = \sum_{i=1}^n f_i$ とする
  2. $P_i$ は$e_{f_i} \leftarrow Enc_{pk}(f_i)$ を計算し、ブロードキャストする
  3. $P_i$ はZKPoPK を利用し、$e_{f_i}$ は$P_i$ 自身が作成したものであると証明する
  4. 全ての参加者は$e_f \leftarrow e_{f_1} \boxplus … \boxplus e_{f_n}$ を計算し、さらに$e_{m+f} \leftarrow e_m \boxplus e_f$ を計算する
    • 演算子$\boxplus$ は、暗号文の空間$\mathbb{Z}^{\mathbb{N}}$ 上の加算を意味する
  5. 全ての参加者は$e_{m+f}$ を復号し、$m+f$ を得る
  6. $P_1$ は$m_1 \leftarrow m + f – f_1$ を計算し、その他の$P_i \ (i \neq 1)$は$m_i \leftarrow -f_i$ を計算し、シェアとする
  7. $enc = \rm NewCiphertext$ の場合は、全ての参加者は$e_m’ \leftarrow Enc_{pk}(m+f) \boxminus e_{f_1} \boxminus … \boxminus e_{f_n}$を計算し、暗号文を得る
    • 演算子$\boxminus$ は、$\mathbb{Z}^{\mathbb{N}}$上の減算を意味する

Angle化

Angle化($\rm PAngle$) は任意の平文$m$ に対するシェア$\langle m \rangle$ を生成するためのサブプロトコルです。

$m$ のシェア$m_1, m_2, …, m_n$ と、$m$ の暗号文$e_m$ を入力とし、$\rm PAngle$$(m_1, m_2, …, m_n, e_m) = \langle m \rangle$ を生成します。

以下が詳細なアルゴリズムです。

  1. 全ての参加者は、$e_{m\cdot \alpha} \leftarrow e_m \boxtimes e_{\alpha}$ を計算する
    • 演算子$\boxtimes$ は、$\mathbb{Z}^{\mathbb{N}}$上の乗算を意味する
  2. 全ての参加者は、$(\gamma_1, \cdots, \gamma_n) \leftarrow \rm Reshare$$(e_{m\cdot \alpha}, \rm NoNewCiphertext)$ を計算し、$P_i$は$\alpha \cdot m$ のシェア$\gamma_i$ を取得する
  3. $\langle m \rangle = (0, m_1, \cdots, m_n, \gamma_1, \cdots, \gamma_n)$ を出力する

Bracket化

Bracket化($\rm PBracket$)は任意の平文$m$ に対するシェア$[\![ m ]\!]$ を生成するためのサブプロトコルです。

$m$ のシェア$m_1, m_2, …, m_n$ と$m$ の暗号文$e_m$ を入力とし、$\rm PBracket$$(m_1, m_2, …, m_n, e_m) = [\![ m ]\!]$ を生成します。

以下が詳細なアルゴリズムです。

  1. 全ての参加者$P_i$ は、それぞれ $e_{\gamma_i} \leftarrow e_{\beta_i} \boxtimes e_{m}$を計算する
  2. 全ての参加者$P_i$ は、それぞれ $(\gamma_i^1, \cdots, \gamma_i^n) \leftarrow \rm Reshare$$(e_{\gamma_i}, \rm NoNewCiphertext)$ を計算する
  3. $m\cdot \beta_i$ のシェアである$\gamma_i^j$ を$P_j$ が取得する
    • ただし、$j = 1,\cdots, n$
  4. $[\![ m ]\!] = (m_1, \cdots, m_n, (\beta_i, \gamma_1^i, \cdots, \gamma_n^i)_{i=1, \cdots, n})$ を出力する

以上が、サブプロトコルの説明でした。

次に前処理フェーズのプロトコルを見ていきましょう。

前処理フェーズのプロトコル

前処理フェーズでは、初期化フェーズ、ペアフェーズ、トリプルフェーズがあります。

それぞれについて説明していきます。

初期化フェーズ

初期化フェーズでは、$\alpha$ のシェアと$\beta_i$ を生成します。

以下がそのプロトコルです。

  1. 全ての参加者が公開鍵$pk$ を取得する
  2. $P_i$ は秘密鍵$\beta_i \in \mathbb{F}_{p^k}$ を取得する
  3. $P_i$ は$\alpha_i \in \mathbb{F}_{p^k}$ を生成する
    • ただし、$\alpha = \sum_{i=1}^n \alpha_i$とする
  4. $P_i$ は以下を計算しブロードキャストする
    • $e_{\alpha_i} \leftarrow Enc_{pk}( \rm Diag(\alpha_i))$
    • $e_{\beta_i} \leftarrow Enc_{pk}(\rm Diag(\beta_i))$
      • ただし、$\rm Diag(x)$ は$(x,x, \cdots , x) \in (\mathbb{F}_{p^k})^s$ を表す
  5. $P_i$ はZKPoPK を利用し、$e_{\alpha_i}, e_{\beta_i}$ は$P_i$ 自身が作成したものであると証明する
  6. 全ての参加者は$e_{\alpha} \leftarrow e_{\alpha_1} \boxplus … \boxplus e_{\alpha_n}$ を計算し、$\alpha$ のシェア$[\![\rm Diag(\alpha) ]\!] \leftarrow \rm PBracket(\rm Diag(\alpha_1), …, \rm Diag(\alpha_n), e_\alpha)$ を得る

ペアフェーズ

ペアフェーズでは、$\langle r \rangle, [\![ r ]\!], [\![ t ]\!], [\![ e ]\!]$ を生成します。

以下がそのプロトコルです。

  1. 各$P_i$ は$r_i \in (\mathbb{F}_{p^k})^s$ を生成する
    • ただし、$r = \sum_{i=1}^n r_i$ とする
  2. 各$P_i$ は$e_{r_i} \leftarrow Enc_{pk}(r_i)$ を計算しブロードキャストする
    • ただし，$e_r = e_{r_1} \boxplus … \boxplus e_{r_n}$ とする
  3. $P_i$ はZKPoPK を利用し、$e_{r_i}$ は$P_i$ 自身が作成したものであると証明する
  4. 各参加者は以下の2つを計算し$[\![ r ]\!], \langle r \rangle$ を得る
    • $[\![ r ]\!] \leftarrow$ $\rm PBracket$$(r_i, …, r_n, e_r)$
    • $\langle r \rangle \leftarrow$ $\rm PAngle$$(r_1, …, r_n, e_r)$

なお、オンラインフェーズで必要とする$[\![ t ]\!], [\![ e ]\!]$については、最後の$\rm PAngle$化の処理を省略することによって、同様に生成することができます。

トリプルフェーズ

トリプルフェーズでは、乗算に使用する$\langle a \rangle, \langle b \rangle, \langle c \rangle, \langle f \rangle, \langle g \rangle, \langle h \rangle$ を生成します。

以下がそのプロトコルです。

  1. 各$P_i$ は、$a_i, b_i \in (\mathbb{F}_{p^k})^s$ を生成する
    • ただし、$a = \sum_{i=1}^na_i, b = \sum_{i=1}^nb_i$ とする
  2. 各$P_i$ は以下を計算しブロードキャストする
    • $e_{a_i} \leftarrow Enc_{pk}(a_i)$
    • $e_{b_i} \leftarrow Enc_{pk}(b_i)$
  3. $P_i$ はZKPoPK を利用し、$e_{a_i}, e_{b_i}$ は$P_i$ 自身が作成したものであると証明する
  4. 全ての参加者は、$e_a \leftarrow e_{a_1} \boxplus … \boxplus e_{a_n}$, $e_b \leftarrow e_{b_1} \boxplus … \boxplus e_{b_n}$を計算する
  5. 全ての参加者は、$\langle a \rangle \leftarrow$ $\rm PAngle$ $(a_1, …, a_n, e_a)$ と$\langle a \rangle \leftarrow$ $\rm PAngle$ $(b_1, …, b_n, e_b)$ を生成する
  6. 全ての参加者は、$e_c \leftarrow e_a \boxtimes e_b$ を計算する
  7. 全ての参加者は、$(c_1, …, c_n, e_c’) \leftarrow$ $\rm Reshare$($e_c, \rm NewCiphertext$) を計算する
  8. $\langle c \rangle \leftarrow \$ $\rm PAngle$$(c_1, …, c_n, e_c’)$ を生成する

注意点として、7の処理は、$\rm PAngle$ をそのまま適用すると6の乗算と合わせて乗算回数が2回になってしまい、誤差が大きくなるのを防ぐために実施しています。

以上で初期化フェーズ、ペアフェーズ、トリプルフェーズの説明をしました。これらのプロトコルを実行することで、オンラインフェーズで使用する各種の値を生成することができます。

まとめ

この記事では、SPDZの前処理フェーズについて説明しました。

この記事の要点は以下の通りです。

  • SPDZは、前処理フェーズ及びオンラインフェーズから構成されるpreprocessing-modelを採用している。
  • 前処理フェーズではSHE(制限付き準同型暗号)を使用し、高い効率性と安全性を実現しながら、オンラインプロトコルで使用する値を生成することができる。
  • 前処理フェーズは、初期化フェーズ、ペアフェーズ、トリプルフェーズから構成される。
  • 内部のサブプロトコルとして以下が必要である。
    • 平文のゼロ知識証明
    • 再シェア化
    • Angle化
    • Bracket化

参考文献

PICK UP

【技術】Intel SGXの秘密計算利用の難しさとは？

【技術】楕円曲線暗号②

MOST POPULAR