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

  • calendar2020.06.19
  • reload2022.10.03
投稿者：R&D
ホーム » 技術 » 【技術】SPDZプロトコル① SPDZの概要とオンラインフェーズについて

はじめに

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

MPC・秘密分散法については以下の記事を参考にしてください。

【技術】秘密計算とは
【技術】Multi Party Computationとは

SPDZは、高い効率性と安全性を実現するMPCプロトコルの一つです。主に以下のような特徴を持っています。

  • $n$人のplayerのうち、$n-1$人がactive adversary(攻撃的敵対者)であったとしても安全である
  • preprocessing-modelを採用しており、前処理フェーズ及びオンラインフェーズにおいて、高い効率性と安全性を実現している
  • 前処理フェーズにおいてSHE(制限付き準同型暗号)を使用する

以前紹介したBGWプロトコルは、「参加者の半数未満のプロトコルから逸脱しない不正者に対して耐性がある」ものでしたが、SPDZは「$n$人の参加者のうち、$n-1$人がプロトコルから逸脱する不正を行ったとしても耐性がある」プロトコルです。

BGWプロトコルについては以下記事を参考にしてください。

【技術】BGW プロトコルとは シャミア法を用いたMPCを紹介！

SPDZの概要

前述の通り、SPDZはpreprocessing-model を使用しています。preprocessing-model とは、「前処理フェーズ(preprocessing phase)」と呼ばれる、MPCの実行時に使用される特殊な値を生成するフェーズと、「オンラインフェーズ(online phase)」と呼ばれる、MPCを実行するフェーズの2つから構成されるモデルです。本記事では、後者の「オンラインフェーズ」の仕組みについて紹介します。

また事前知識として「加法的秘密分散(Additive Secret Sharing)」と「Beaver’s Trick(Beaver’s multiplication triple)」が必要です。これらについては以下の記事を参照してください。

【技術】秘密分散法とは？ 数式を用いて解説
【技術】Beaver Multiplication Triples とは

それでは、「オンラインフェーズ」の仕組みについてみていきましょう。

オンラインフェーズの仕組み

記号の定義

SPDZプロトコルでは、2つの記号( $\langle m \rangle, [\![ m ]\!]$ )が重要な値を表現します。それぞれ秘密にしたい情報$m$ のシェアを意味しますが、単一の値を表現しているものではなく、様々な値の組を表現します。それぞれ見ていきましょう。

まず、$\langle m \rangle$ はメッセージの完全性(欠損や不整合がないこと)が認証されたシェアを意味します。数式的に表すと、以下の表現になります。

$\langle m \rangle = (\delta, (m_1, m_2, \cdots, m_n), (\gamma(m)_1, \gamma(m)_2, \cdots, \gamma(m)_n))$

<m>の仕組み

$\delta$ はプロトコルへの参加者$P_i$ が参照できる公開情報です。$m_i$ は$P_i$ のみが保持する$m$ のシェアであり、以下の制約を満たします。

$m = \sum_i m_i$

また$\gamma$ はメッセージの完全性を認証するMAC関数を表しており、$\gamma(m)_i$ は$P_i$ のみが保持する$\gamma(m)$ のシェアであり、以下の制約を満たします。

$\gamma(m) = \sum_i \gamma(m)_i = \alpha(m + \delta)$

ここで新たな値$\alpha$ が登場しました。これは、MAC関数の計算に必要なグローバル鍵です。この鍵$\alpha$ を用いることによって、MAC検証を行うことができます。また$\alpha$ は計算が終了した後に公開されます(計算前に公開すると、各$P_i$ がMACを偽造することができてしまうため)。

次に、$[\![ m ]\!]$ は$P_i$ の秘密鍵$\beta_i$ によって認証されたシェアを意味します。数式的に表すと、以下の表現になります。

$[\![ m ]\!] := ((m_1, \cdots, m_n), (\beta_i, \gamma(m)_1^i, \cdots, \gamma(m)_n^i)_{i=1, \cdots, n})$

[m]の仕組み

$m_i$ については$\langle m \rangle$ と同様の制約を満たします。

$\gamma(m)_i^j$ は、参加者$P_j$ が保持する、$\gamma(m)_i$ のシェアという意味で、以下の制約を満たします。

$\sum_j\gamma(m)_i^j = \gamma(m)_i = m\beta_i$

$\langle m \rangle$ と$[\![ m ]\!]$ の違いは、「$\alpha$ がないとMAC検証ができないのが$\langle m \rangle$、$\alpha$ なしに$m$ を復元できるのが$[\![ m ]\!]$」です。したがって、オンラインフェーズで$\alpha$ を公開する前に値$m$ が必要な場合は$[\![ m ]\!]$ を利用し、$\alpha$ を公開してからMAC検証する場合は$\langle m \rangle$ を使用します。

ここまでで、SPDZプロトコルで使用する記号の説明が終了しました。次に、本題のオンラインプロトコル について説明していきます。

オンラインプロトコル

オンラインプロトコルでは、ある秘密情報に対して以下の手順で秘密計算の実行を行います。

  1. 初期化
  2. 入力
  3. 計算
    • 加算
    • 乗算
  4. 出力

初期化

このフェーズでは、前処理フェーズで生成しておいた以下の値を各参加者$P_i$ が読み込みます。

  • $[\![ \alpha ]\!]$ のシェア
  • 乗算で使用するシェア$(\langle a \rangle, \langle b \rangle, \langle c \rangle)$
  • 入力フェーズで使用する$r$ のシェア$\langle r \rangle, [\![ r ]\!]$
  • 乗算、出力フェーズで使用する$t, e$ のシェア$[\![ t ]\!], [\![ e ]\!]$

入力

以下の手順で$P_i$ が持つ秘密情報$x_i$ をシェアにします。

  1. $P_i$ は$[\![ r ]\!]$を復号して$r$ を得る
  2. $P_i$ は$\epsilon \leftarrow x_i – r$ を自分以外の参加者に送信する
  3. 全ての参加者は、$\langle x_i \rangle \leftarrow \langle r \rangle + \epsilon$を計算しシェアとする

加算

シェア$\langle x\rangle, \langle y \rangle$ の加算は加法準同型性があるため、シンプルに加算して計算します。

  • $\langle x + y \rangle = \langle x \rangle + \langle y \rangle$

乗算

Beaver’s Trick($c=ab$ となる$a,b,c$ のシェアを利用する方法)を使用して乗算を計算します。ただし、参加者の不正を検知するために、検証用のシェア($h=fg$ となる$f,g,h$) を用意し、$c=ab$が成立しているか確認します。

  1. 各参加者はシェア $(\langle a \rangle, \langle b \rangle, \langle c \rangle), (\langle f \rangle, \langle g \rangle, \langle h \rangle)$を読み込む
  2. 各参加者は$[\![ t ]\!]$ を復号する
  3. 各参加者は $\rho = t\cdot\langle a \rangle – \langle f \rangle$，$\sigma = \langle b \rangle – \langle g \rangle$を計算し復号する
  4. 各参加者は$t\cdot\langle c \rangle – \langle h \rangle – \sigma\cdot \langle f \rangle – \rho \cdot \langle g \rangle – \sigma \cdot \rho$ を計算し復号する
    1. 復号結果が0 以外の場合は不正が発生しているため計算を終了する(補足1)
    2. 復号結果が0 の場合は次のステップに進む
  5. 各参加者は$\epsilon = \langle x \rangle – \langle a \rangle, \delta = \langle y \rangle – \langle b \rangle$ から$\langle z \rangle \leftarrow \langle c \rangle + \epsilon \langle b \rangle + \delta \langle a \rangle + \epsilon\delta$ を計算する

出力

各参加者が持つ出力値$y$ のシェア$\langle y \rangle$ が正しい値になるか検証します。

  1. $a_1, \cdots, a_T$ をこれまでに復号されたシェアとする(ただし、$\langle a_j \rangle = (\delta_j, (a_{j, 1}, \cdots, a_{j, n}), (\gamma(a_j)_1, \cdots, \gamma(a_j)_n))$ が成立)
  2. $[\![ e ]\!]$ を復号する
  3. 全ての参加者は$e_i = e^i \ (i = 1, \cdots, T)$を計算する
  4. 全ての参加者は$a \leftarrow \sum_je_ja_j$ を計算する
  5. 各参加者$P_i$ は$\gamma_i \leftarrow \sum_je_j\gamma(a_j)_i$を計算し、システムにコミットする
  6. 各参加者$P_i$ は$y$ のシェア$y_i$ と$\gamma(y)_i$ をシステムにコミットする
  7. $[\![ \alpha ]\!]$を復号する
  8. システムがコミット済みの$\gamma_i$ を公開し、各参加者が$\alpha(a + \sum_je_j\delta_j) = \sum_i\gamma_i$ が成立するか確認する
    1. 成立していなければ不正のためシステムを終了する(補足2)
    2. 成立していれば次のステップに進む
  9. システムがコミット済みの$y_i, \gamma(y)_i \ (i = 1, …, n)$を公開する
  10. $y := \sum_i y_i$を計算し、$\alpha(y + \delta) = \sum_i \gamma(y)_i$が成立するか確認する
    1. 成立した場合$y$ を正しい出力値とする

以上がオンラインフェーズのプロトコルの紹介でした。主に乗算と出力フェーズにおいて、悪意のあるユーザによる数値の改竄を検知し、システムを終了させることで高い安全性を実現しています。

まとめ

この記事では、SPDZのオンラインプロトコルについて説明しました。続いての記事では、SPDZの前処理フェーズのプロトコルについて説明します。

この記事のまとめは以下になります。

  • SPDZは、高い効率性と安全性を実現するMPCプロトコルの一つ
  • $n$人のplayerのうち、$(n-1)$人がactive adversary(攻撃的敵対者)であったとしても安全である
    • MACによる検証を行っているため改竄を検知できる
  • preprocessing-modelを採用しており、前処理フェーズ及びオンラインフェーズにおいて、高い効率性と安全性を実現している

補足

1

正しい値の場合、以下の通り0になる

$$ \begin{array}{l} t\cdot c- h – \sigma\cdot f – \rho \cdot g – \sigma \cdot \rho \\ = t\cdot (ab)- (fg) – (b-g)\cdot f – (t\cdot a – f)\cdot g – (b-g)\cdot (t\cdot a – f) \\ = tab- fg – (bf-fg) – (tag – fg) – (tab – bf -tag + fg) \\ = tab-fg-bf+fg-tag+fg-tab+bf+tag-fg \\ =0 \end{array} $$

2

実際に計算して得られた値が正しい値かどうか、検証してから出力します。

さらに、1, 2では公開情報を元にMAC値を計算しておりますので、公開情報をほんの一部を改竄しただけでも、不正が検知できるようになっています。

ここで、4の正当性をチェックしてみましょう。

$$ \begin{array}{ccl} \sum_i\gamma_i &=& \sum_i (\sum_j e_j\gamma(a_j)i) \\ &=& \sum_i (\sum_j e_j(\alpha(a{j,i} + \delta_{j, i}))) \\ &=& \alpha \sum_i \sum_j e_j(a_{j,i} + \delta_{j, i}) \\ &=& \alpha \sum_j \sum_i e_j(a_{j,i} + \delta_{j, i}) \\ &=& \alpha \sum_j e_j(a_{j} + \delta_{j}) \\ &=& \alpha \sum_j (e_ja_{j} + e_j\delta_{j}) \\ &=& \alpha (a + \sum_je_j\delta_j) \end{array} $$

公開情報の一部を改竄すると、値が変化し、MAC検証に失敗する仕組みになっています。

参考文献

PICK UP

【技術】Function Secret Sharing (FSS)とは？

【技術】MPCにおける基数ソート(Oblivious Radix Sort)の解説

MOST POPULAR