MPC
概要
マルチパーティ計算（Multi Party Computation：MPC）
複数のサーバーが協力して計算を行う
サーバーからは、入力データ・計算の途中結果・計算結果を知ることはできない
分散計算の宿命として、悪意のあるノードの存在を仮定した対応をする必要がある
シェアの状態になったデータを各ノードが計算を行う
結果を集めたものが計算結果になる
シェアのまま計算したものは、それだけでは意味を持たない
ノードは計算の中身について知ることはできない
計算コストは低いが、多数のコミュニケーションコストがかかる
https://gyazo.com/6cf771310f7e62957d63bab168191cad
MPCの歴史
https://gyazo.com/9d6c864492652778e4672e7faad6b843
詳細
$ N人の参加者$ A_iがいる場合に、参加者は自身の秘密情報$ s_iを持っているとする。
参加者が実行したい計算$ f(s_1, s_2, \cdots, s_N)を行う場合、秘密情報$ s_iを明かすことがないプロトコル。
MPCを用いた加法の例
参加者はシャミアの秘密分散法を用いて$ s_iをシェア$ v_{i,j}に分ける
各シェアと法$ qを全ての参加者に秘密裏に分配する
全員の秘密情報のシェアが全員に行き渡る
参加者は自身の持つ全てのシェア$ v_{1,j}, v_{2,j}, \cdots, v_{N,j}に対して加法を適用する
$ v_j = v_{1,j} + v_{2,j} + \cdots + v_{N,j}
全ての参加者が計算した$ v_1, v_2, \cdots, v_Nを集めて、計算結果を復号する
注意点
全ての参加者が正しく行動をするとは限らない
別途、検証する機構が必要になる
ネットワークモデル
参加者はP2Pで秘密通信可能
同期型ネットワーク
同期の取り方はビザンチン耐性を持つ方法で行う
代表的なMPCプロトコル
BGW/CCD型の秘密計算
情報理論的安全な方法
Passiveな攻撃者なら半数未満まで許容
正規のプロトコルに違反はしないが、受け取った情報から他の参加者の秘密情報を得ようとする
Activeな攻撃者なら$ \frac{1}{3}未満まで許容
正規のプロトコルから逸脱してもいい。
参加者の秘密情報を得ようとする
プロトコル自体を失敗させようとする
さらに2つのパターンあり
static
最初に攻撃者が固定されている
adaptive
正直な参加者をのっとることで情報をさらに獲得する
Yao's Garbled Circuit
2パーティー間でのMPC
Passiveな攻撃者を想定
Obliviouse Transferを使用
情報の転送時に外部にその内容が漏れない状態
GMW（Goldreich-Micali-Wigderson）
1987年に開発された基本的な手法
線形秘密分散を使用
主要な技術
線形秘密分散（Linear Secret Sharing：LSS）
シェア状態の$ [s_1],[s_2] に対して、定数$ a,bとした時に以下を満たす
$ [as_1 + bs_2] = a[s_1] + b[s_2]
シェアの状態で加算を行うことは、加算を行なった後にシェアにすることと同じである性質
乗算も可能だが計算時間がかかる
検証可能線形秘密分散（Verifiable Linear Secret Sharing：VLSS）
Activeな攻撃者がいても、攻撃者を検知して排除することができる
実装例
BGW VSS
Garbled circuit
Oblivious Transfer
通信方法による攻撃耐性
2者間Obliviouse Transfer
Passive, Active攻撃者に対して任意の攻撃耐性あり
ブロードキャストとP2P通信
Active攻撃者に対して n/2 まで耐性あり
P2P通信
Passive攻撃者に対して n/2 まで耐性あり
Active攻撃者に対して n/3 まで耐性あり
MPCの実装（ツールキット）
こちらに全てのリストがある
https://gyazo.com/bb2708caf5e9d86e72d5fb516c7c3fea
大きくActive SecureかPassive Secureで分類できる
論文でよく言及されているものをあげる
Active Secure
SCALE-MAMBA
FRESCO
HoneyBadgerMPC
Passive Secure
Obliv-C
ABY3
Sharemind
Googleが出した2者間のテーブルを用いたMPCツール（2019/06/20）
Private Join and Compute
Private Set Intersectionを用いて2者間のテーブルを結合する
テーブルは準同型暗号で暗号化して結合される
統計処理を行うことができる
参考文献
スライド
マルチパーティ計算の理論
藤崎英一郎 北陸先端科学技術大学大学院
高速秘密計算説明資料
NECセキュリティ研究会
NECの秘密計算技術のご紹介
NECセキュリティ研究会
秘密計算のシステムとその原理
NTTセキュアプラットフォーム研究所
Secure Multi-Party Computation
Ashutosh Satapathy 工業技術研究会
Secure Multi Party Computation
A Survey of MPC Offerings - Boston University
Mayank Varia
論文
Secure multi-party computation for analytics deployed as a lightweight web application
Andrei Laoets ボストン大学
Students and taxes: a privacy-preserving study using secure computation
Dan Bogdanov タルツ大学(エストニア)
SoK: General Purpose Compilers for Secure Multi-Party Computation
Marcella Hastings ペンシルバニア大学
書籍
Applying secure multi-party computation in practice（144ページ）
RIIVO TALVISTE タルツ大学(エストニア)
A Pragmatic Introduction to Secure Multi-Party Computation（180ページ）
David Evans バージニア大学
Applications of Secure Multiparty Computation（264ページ）
Peeter Laud, Liina Kamm
Web
Resources for Getting Started with MPC
Yehuda Lindell
A curated list of multi party computation resources and links.
rdragos/awesome-mpc
Theory and Practical of Multi-Patry Computation Workshop
Google、プライバシーを保護しながらデータセットを解析する「Private Join and Compute」をオープンソース化
ITmedia
Eiichiro Fujisaki
藤崎英一郎 北陸先端科学技術大学大学院 教授
ADVANCES IN PRACTICAL MULTIPARTY COMPUTATION