A Pragmatic Introduction to Secure Multi-Party Computation
概要
A Pragmatic Introduction to Secure Multi-Party Computationを読んだまとめ
2020/4にエラッタされて以下に変更されました
実用的なMPCについてまとめた本
プライバシー保護アプリケーションの開発者や、研究者に向けた内容
関連
1. Introduction
MPCはプライバシー保護計算を実現するために1980年代に発表された
Andrew YaoのGarbled Circuit Protocol が有名
秘密計算と呼ばれるものは2種類ある
1. アウトソースコンピュテーション
データの所有者が、分析者にデータを提供し、その結果を得る方法
ただし、暗号化したデータに対して分析を行うため、分析者に情報が漏れない
限定的な利用に留まる
2009年にGentryが初めてFHEの実装方法を提案したことで発展
ただし、乗算を用いる場合の計算コストが莫大
複数の鍵で暗号化することができる方法も提案されている
Mukherjee and Wichs, 2016
MPCと比較すると数1000倍以上の速度差があり、遅い
2017年のChillotti のFHE実装と比較
一般的な設定かつ、一般的なアプリケーションにおいて
FHEとMPCを比較する
FHEは計算コストがかかる
発展に伴って、計算効率は改善される余地は十分にある
例えば、乗算によるノイズを除去するための効率の良いアルゴリズムを発見するなど
MPCは通信コストがかかる
通信帯域自体の発展は難しいので、より抜本的に効率の良いプロトコルが発見される必要がある
例えば、通信回数を格段に減らすなど
究極的にはMPCとFHEは完全に競合になり、使用用途に応じて使い分けることになる
2. マルチパーティコンピュテーション
複数のデータ所有者自身で計算を行う
ただし、データ所有者以外にはその情報は漏洩しない
データの所有者同士が信頼し合う必要はない
歴史
1982年にm 人の参加者で秘匿計算$ f(x_1, x_2, \cdots,x_m)を行う方法をAndrew Yaoが発表した
Yao's Garbled Circuit Protocol
その後20年間は理論的な議論が進行した
2004年にFairplayというMPCの実用的な実装が登場した
ただし、データ数10のソートされた数列2つの中央値を計算するに留まる
Yaoの方法は汎用計算を実行可能な方法
用途を限定した方法も提案されている
Private Set Intersection（PSI）など
こちらの方が汎用MPCよりも効率がいい
研究におけるMPCアプリケーション例
Yao's ミリオネア問題
二人の富豪がいたときに、どちらがより資産を持っているかを判定する。ただし、二人の資産の値をお互いが知ることはない。
実用的なアプリケーションではないが、YaoがMPCとは何かを説明するために用いた
セキュアオークション
入札額を他の入札者に秘密にしたままオークションを実現する
他の入札者の額を参考にして入札することができない
投票
投票結果の集計をする。
ただし、他の参加者の投票内容を知ることはできない
セキュアマシンラーニング
データ提供者と学習済みのモデル提供者がお互いにその情報を知ることなく、予測結果を計算する
学習済みのモデルを構築する方法としてMiniONN(Liu et al., 2017)が提案されている
その他
ネットワークの監視
Burkhart 2010
ゲノミクス、遺伝学
Wang 2015, Jagadeesh 2017
安定マッチング
Doerner 2016
広告コンバージョン
Kreuter 2017
暗号メールのスパムフィルタ
Gupta 2017
実世界へのMPC適用例
デンマークテンサイオークション
植物のテンサイのオークションをMPCで実施
3者間MPCを構築
農家連合、加工会社、研究機関
農家は加工会社に入札額を知られたくない
生産能力がバレてしまうから
加工会社はオークションをセキュアに行いたい
会社にとって最も重要な契約であるため
エストニアの学生に対する調査
学生の税金と教育に関するデータを用いて相関性があるか調査した
元々はk匿名化で調査していたが、有意な結果が得られなかった
結局、MPCで計算してみても有意な結果は得られなかった
3者間MPC
エストニア情報省、財務省、Cybernetica(ツールSharemindの開発元)
ボストンの賃金平等性調査
ボストンの労働者の賃金と、その属性の関係を調べる調査を行った
賃金の情報は秘匿化した状態で調査を行った
鍵管理
秘密鍵の管理をMPCで行う
秘密鍵をシェアに分けて複数のサーバにおく
鍵の認証は、本来の鍵の所有者とサーバー群の間でMPCを通して行う
これによって、鍵自体の復号をする必要がなくなる
2. Defining Multi-Party Computation
記法
$ Enc_k (m) : キーkで暗号化されたメッセージm
$ Dec_k (m) : キーkで復号されたメッセージm
$ P_1, P_2 : パーティまたは参加者
$ A : 敵
$ ν : N → R : 漸近的に0に近づく関数
$ κ : 敵のオフライン計算によって破壊されるかもしれない問題の強度（128 や256などの値）
$ σ : 攻撃の強度（40や80などの値）
$ (\frac{1}{2})^{\sigma} + ν(κ): セキュリティが侵害される確率
無限の計算能力をもつ敵の場合は$ κを省略し$ ν=0を必要とする
$ \in_R : 分布からのランダムな抽出
$ choose \ k \in_R \{ 0, 1 \}^κ: kは一律にランダムに選ばれたκ-bitの文字列
$ v \in_R A(x): $ vはランダムアルゴリズム$ Aに$ xを入力した時の返り値
$ D_1, D_2 : セキュリティパラメタによって索引付けられた確率分布
以下が成り立つと$ D_1 と D_2が計算量的識別不可能性である（Aは全てのアルゴリズム）
$ Pr[A(D1(n)) = 1] − Pr[A(D2(n)) = 1] ≤ ν(n)
多項式時間アルゴリズム : 解くべき問題の入力サイズnに対して、処理時間の上界としてnの多項式で表現できるものが存在するアルゴリズム
統計的識別不可能性は情報理論的安全性を意味する
敵の想定
計算量的セキュリティの場合
多項式時間アルゴリズムを実行することができる
情報理論的でキュリティの場合
無限の計算リソースをもつ
重要な技術的要素
(t,n)-secret sharing
t-1 個までのシェアでは復元できず、t 個のシェアでは復元ができる性質
シェアの総和をとることで復元できる秘密分散法
ランダムオラクル
ハッシュ関数のヒューリスティック（経験的にうまくいく）なセキュリティモデル
ハッシュ関数を理想的なランダム関数として扱うためのもの
ランダム選択関数を実現する$ \{0, 1\} \rightarrow \{0, 1\}^κ
入力に対し一様にランダムな値を返す
同一の入力に対しては同一の値を返す
内部の具体的な関数が漏洩するとセキュアでなくなる
大量の入力と出力の組から関数を特定する攻撃
MPCのセキュリティ
real-idealパラダイムでセキュリティモデルを議論する
http://u.cs.biu.ac.il/~lindell/research-statements/mpc-ppdm_files/image005.gif
Ideal World（実際はない）
完全に信頼されたパーティ$ Tが各パーティからインプット$ x_iを受け取り、$ F(x_1, ..., x_n)を計算し結果を返す
$ Tはfunctionalityとも呼ばれる
$ Tは乗っ取られることはない
$ Tは完全に信頼できる
Ideal な理由
$ Tは計算結果しか返さない
敵は$ F(x_1, x_2, ..., x_n)以外の情報を得ることができない
あるパーティを乗っ取っても、他のパーティは独立して入力する
攻撃者は結局、秘密情報を得られない
$ x_iと計算結果のみ
Ideal Worldは実際のプロトコルを考える際のベンチマークになる
Real World
信頼できるパーティは存在しない
各パーティはプロトコル$ \piによってコミュニケートする
$ \piは関数$ \pi_iを各パーティ$ P_iに提供する
引数は以下
セキュリティパラメタ
$ P_iの秘密情報$ x_i
ランダムテープ
乱数を提供してくれるやつ
これまでに$ P_iが受け取った全てのメッセージ
出力は以下のどちらか
次のメッセージを目的地に送信する
結果を出力して終了する
敵がプロトコルに従う場合とプロトコルを逸脱する場合の二つのモデルを想定する
Semi-Honest Security
Malicious Security
Real World におけるプロトコル$ \piは以下の時セキュアであると見做される
Real World において攻撃者が達成できる効力は Ideal World においても達成できる
攻撃者が Ideal World で出来ることは Real World で出来ても許容するしかない
Ideal Worldの方がセキュアな環境であるのに、そこでも可能な攻撃に対しては回避不可
Real World のプロトコルが目指すのは Ideal World と同等のセキュリティ（仮定を置いた上で）
Semi-Honest (passive) Security
参加者はプロトコルに則った行動をするが、受け取ったメッセージや計算結果から、秘密情報を知ろうとする
共謀して情報を共有することも含む
実際のユースケースで考えると以下
参加者同士は基本的に信頼している
しかし、各参加者のストレージが将来に渡って信頼できることは保証できない
パーティのviewは以下
自分の秘密情報
ランダムテープ
既知のメッセージ
敵はコラプトしたパーティの全てのviewを知ることができる
実質的にviewを集めることが唯一の攻撃
プロトコルをセキュアにするにはReal Worldの敵のviewと区別がつかないものをIdeal Worldで生成できなければならない
Real World を Ideal World において分析可能とするため
Ideal Worldでの敵はSimulatorと呼ぶ
$ Tからの出力とコラプトしたパーティの入力のみを得る
シミュレートされたviewをReal Worldでのviewとする
各種定義
$ \pi: プロトコル
$ \mathcal{F}: functionality
$ C: コラプトされたパーティ集合
$ Sim: シミュレータアルゴリズム
プロトコル実行：$ Real_\pi(κ, C; x_1, ..., x_n)
$ κ:セキュリティパラメタ
$ x_i:$ P_iの秘密情報
出力：$ \{V_i | i \in C \}, (y_1, y_2, ..., y_n)
$ V_i:$ P_iの最終的なview
$ y_i:$ P_iの最終計算結果
シミュレーション:$ Ideal_{(\mathcal{F}, Sim)}(κ, C; x_1, ..., x_n)
出力 : $ Sim(C, \{(x_i, y_i)| i \in C\}), (y_1, ...,y_n)
Real WorldでSemi-Honestな攻撃者が居る中で$ \piが$ Fをセキュアに実現するには以下の条件が必要
任意の攻撃者の組$ Cと任意の入力の組$ (x_1, ... , x_n)に対し、$ Real_{\pi}(\kappa , C; x_1, ... , x_n)と$ Ideal_{(\mathcal{F}, Sim)}(\kappa,C; x_1, . . ., x_n)が区別不能となる$ Simが存在する
Semi-Honestでは$ C = \emptysetであろうと、$ C ≠ \emptysetであろうとアウトプットの分布はRealとIdealでほぼ同じ
プロトコルにしたがっているので、計算結果を改変することはない
Malicious (active) Security
悪意のある参加者がプロトコルを逸脱し、任意の行動をとることで秘密情報を知ろうとする
支配、操作、メッセージインジェクション
2つの考えるべき重要なこと
出力への影響
攻撃者が任意の計算結果を出力することができる
コラプトされたパーティからの出力を保証することができない
抽出
敵パーティはプロトコルで未定義な入力をすることができる
セキュアなプロトコルにおいて、攻撃者が Real Worldで実現可能なことは、Ideal Worldでも実現可能であるべき
$ Tへの入力を適切に選択することによって。
Real Worldでのコラプトされたパーティの入力をIdeal Worldでシミュレートするのが抽出
シミュレーションはブラックボックスで行う
Real Worldでの敵の行動を実装したオラクルにアクセスするのみで、その実装コードにはアクセスしない
各種定義
$ A : 敵を表現するプログラム
$ corrupt(A) : コラプトされたパーティの集合
$ corrupt(Sim) : シミュレータ$ Sim（$ Ideal Worldでの敵）によってコラプトされたパーティのセット
プロトコル実行 : $ Real_{\pi, A}(κ; x_i | i \notin corrupt(A) )
$ κ:セキュリティパラメタ
$ P_i : honestなパーティそれぞれ
$ x_i:$ P_iの秘密情報
コラプトされたパーティのメッセージ : $ A（パーティの次のメッセージを返す関数）に従って選択される
出力 :$ Output(\{V_i|i \in corrupt(A)\}, \{ y_i | i \notin corrupt(A)\})
$ y_i : $ P_iの計算結果
$ V_i: $ P_iの最終的なView
$ Sim実行:$ Ideal_{\mathcal{F}, Sim}(\kappa; \{x_i | i \notin corrupt(A)\})
$ input: $ \{x_i | i \in corrupt(A)\}
計算結果を出力 :$ Compute(y_1, ..., y_n) \leftarrow F(x_1, ..., x_n)
$ \{ y_i | i \in corrupt(A)\}を$ Simに提供
出力 : $ Output(V^*, \{y_i | \ i \notin corrupt(Sim)\})
$ V^* : $ Simの最終的なView
$ \piは以下の条件を満たす時、Malicious な攻撃者の存在の下でセキュアに$ \mathcal{F}を実行できる
全ての$ Aに対し$ corrupt(A) = corrupt(Sim)となる$ Simが存在する
全ての入力$ \{ x_i | i \notin corrupt(Sim)\}に対し$ Real_{(\pi,A)}(\kappa ; \{x_i | i \notin corrupt(A)\})と$ Ideal_{(\mathcal{F},Sim)}(\kappa; \{ x_i | i \notin corrupt(Sim)\})が区別不能
$ Realはコラプトされたパーティが入力を持つと想定しない
$ Idealはコラプトされたパーティの入力をシミュレータが決定する
$ Realでのコラプトされたパーティの入力を定義することはできるが、"提案"にしかならない
敵はどんな入力でプロトコルを実行するかわからないから
Reactive functionality
$ Idealでは、1ラウンドで関数実行する
1入力に対して、1出力を返す
ラウンド間での秘密の内部状態は保持する
これをReactiveと呼ぶ
コミットメント functionality
$ P_1が$ Fに対してあるビット$ bを送信し、$ Fは$ P_2にコミット済みであることを送信する
後に、$ P_1が開示を要求したら、$ Fは$ P_2に$ bを開示する
Security with abort 計算結果の公平性
計算結果を先に得たパーティが他のパーティに送信しないことが可能であるため不公平
悪意のあるパーティのみが計算結果を受け取って、善良なパーティが受け取ることができない問題がある
解決するには計算結果のデリバリーが失敗した段階でアボートする方法がある
コラプトされたパーティのIDを$ Fが知っている場合に以下を実行する
計算結果をコラプトパーティだけに送信する
$ Fはコラプトパーティから「デリバー」か「アボート」を受け取るまで待つ
「デリバー」なら他のホネストパーティにも計算結果を送信する
「アボート」なら「アボート」をホネストパーティに送信する
この設定だと、ホネストパーティが結果を受け取れず、コラプトパーティだけが結果を受け取ることができてしまう
Maliciousな攻撃者を想定する時は計算結果の公平性を一般に保証不可能
計算結果のコントロール権を攻撃者が持っているため
Adaptive corruption
攻撃者がコラプトするパーティを動的に変更すること
特定のパーティに対して対策できない
対義語としてStatic corruptionがある
コラプトパーティが固定されていること
Adaptive corruptionは$ Real-Idealパラダイムでモデル化できる
敵に「$ corrupt ~ P_i」というフォームを提出することを許可する
$ Realでは
敵が$ P_iの現在の$ Viewを知れる
プライベート情報も知れる
敵が$ P_iのプロトコルメッセージを乗っ取れる
$ Idealでは
コラプトパーティの入力と出力のみを知れ、それを使って$ Viewをシミュレートする
Adaptive corruptionの困難な点はシミュレーションを一つ一つ行う必要があること
コラプトパーティ$ P_iをシミュレートする要求に対して$ Viewを作る
$ P_jが$ P_iに送信されたメッセージについても$ P_jのプライベート入力を知らずにシミュレートする要求に対してViewを作る
シミュレータはコラプトした$ P_jのプライベート情報を含んだ$ Viewを作る
それが持っていたプライベート入力が何であれ、ある程度プロトコルメッセージとの一貫性が保たれるように説明する必要がある
ほとんどの研究ではStatic corruptionを前提にしている
本書でもStatic corruptionを前提として以下の話をする
Hybrid World and Composition
モジュール性の観点において、他の完成された（理想的な）関数を用いるのはプロトコル設計に役立つ
$ \piの設計に$ F以外の関数を想定することで便利になる（例として$ Gを導入する）
$ \piは$ Fを実現するプロトコル
$ G：メッセージのやりとりに使用する関数
$ Gを導入した$ Realを$ G - hybrid ~ worldと呼ぶ
セキュリティモデルへの要件としてcomposition(構成)がある
以下の状況の時に$ \pi と \rhoを自然に統合することは$ Fがセキュアなプロトコルで構成されていること意味する
$ \pi：$ Fをセキュアに実現する$ G - hybrid ~ protocol
$ \rho：$ Gをセキュアに実現するプロトコル
逆に、各プロトコルがセキュアでも、組みあわせて使った場合にセキュアでなくなるものはcomposabilityが無いと言える
保証されたcompositionを達成するための方法として$ universal \ composability(UC)フレームワークがある
UCフレームワークは$ environmentと呼ばれるセキュリティモデルを使用する
$ environmentの目的はプロトコルが実行される「文脈」を掴むこと
あるプロトコルはより大きなプロトコルの一つのステップとして呼び出される
$ environment: $ Idealと$ Realの両方に含まれ、$ honest partyへの入力を選択し、出力を受け取る
敵パーティとも任意にやりとりをする
$ environmentのゴールは$ Realと$ Idealのいずれかの世界でインスタンス化されたかどうかを判断すること
出力される0, 1のビットでその推測結果を示す
$ Real, Idealの違いを吸収することができる
この本でマリシャスセキュアなプロトコルとはUC-セキュアなプロトコルである
$ Realと$ Idealがそれぞれ1を出力する確率の差が0に近づく時、UC-セキュアである
$ | Pr[Real_{\pi, A, Z}(k) = 1] - Pr[Ideal_{F, Sim, Z}(k) = 1] | がほとんど0
$ Real：1, $ Ideal：0とした場合に、どちらの世界でも同じ確率で$ Zが1を出力することは、世界の区別をすることができない
送信者が0, 1で構成された文字列を送信するが、受信者がどちらの文字列を受け取ったのかを送信者は知ることが無い通信
以下の時、$ Rは$ x_bを受信し、$ Sはアボートを受け取る
$ S:送信者
$ R:受信者
$ Sのインプット:$ x_0, x_1 \in \{0, 1 \}^n
$ Rのビット:$ b \in \{0,1 \}
上のものは1-out-of-2 OTであるが、送る情報をk個に拡張した1-out-of-k OTも考案されている
$ F^{OT}で表現される
コミットメント
送信者が秘密の情報をコミットし、後に受信者にその情報を開示すること
送信者$ Sは$ F^{Comm}にコミットしたい文字列$ sを送信する
$ F^{Comm}は受信者$ Rに「コミット済み」メッセージを送信する
時間を開けた後に、$ Sは「オープン」を$ F^{Comm}に送信する
$ F^{Comm}は$ Rに$ sを送信する
コミット済みの情報は変更不可（binding プロパティ）
オープン前の情報は閲覧不可（hiding プロパティ）
コミットメントはランダムオラクルモデルにおいて使いやすい
$ xをコミットするために、ランダムな値$ r \in_R\{0,1\}^kを選び、$ y = H(x || r)を公開する
時間を開けた後に、$ xと$ rをアナウンスすればオープンできる
ゼロ知識証明
証明者$ Pは、検証者$ Vに秘密情報$ xを教えることなく、$ xを知っていることを証明すること
$ Pは$ (C, x)を$ F^{zk}に送信する
$ C: $ \{0, 1\}^n \rightarrow \{0, 1\}
$ C(x) = 1の時、$ F^{zk}は$ Vに$ (proven, C)を送信する
$ C(x)= 0の時、$ Vにアボートを送信する
3. Fundamental MPC Protocols
この章で説明するのは全てPassive security
malicous securityは6章で述べる
全てOTをベースに開発されている
コメント
BGWとBMRが現在使われているものらしい
BGW->JIFFで使用
BMR->SPDZで使用
table:protocol
名前 参加者 ラウンド 回路
Yao's GC 2 固定 ブール
GMW 複数 回路の深さ ブール or 算術
BGW 複数 回路の深さ ブール or 算術
BMR 複数 固定 ブール
GESS 2 固定 ブール式
2つのパーティ$ P_1, P_2を想定する
$ P_1, P_2それぞれの入力$ x,yを知られずに$ f(x,y)の計算結果だけを共有する方法
MPCでは最も有名な方法
定数ラウンドで遅延が少ない
GMWの基盤となっている
Function as a look-up table
https://gyazo.com/bb032475b696ac58f2c4875461874eee
予め秘密の入力の組$ (x,y)とそれに対応する計算結果を書いた表$ Tを作っておく
計算結果は入力の組に対応する行を参照することで得る
表の行数は$ x, yの定義域を$ X, Yとしたら$ |X| \times |Y|となる
$ |X|=2, |Y|=2なら表のサイズは4
$ P_1 は入力$ x, yに対応するランダムに生成された鍵で$ Tを暗号化する
各$ x, yに対し異なる鍵$ k_x, k_y \in \{0, 1\}^{\kappa}を割り当てる
暗号化された表$ <Enc_{k_x,k_y}(T_{x,y})>を$ P_2に送信する
$ x,yに対応する行を$ k_x, k_yで暗号化し、シャッフルする
$ P_2はどの行がどの入力の組$ (x, y)に対応しているのか分からない
$ P_2は暗号化された表の対応する行を復号することで計算結果を得ることができる
$ P_1は$ P_2に$ k_xを送信する($ k_xから$ xは分からない)
$ P_1は$ P_2がどの$ yに対応する$ k_yを選択し受け取ったか分からない
この時点で$ P_2は$ <Enc_{k_x,k_y}(T_{x,y})>と、秘密の入力$ (x,y)に対応する鍵$ (k_x, k_y)を持つ
$ P_2は$ k_x, k_yを使って$ <Enc_{k_x,k_y}(T_{x,y})>を復号し、出力$ F(x, y)を得る
受け取った鍵の組$ (k_x, k_y)に対応する行以外は復号できない点に注意
Point-and-Permute
どのようにして$ P_2は復号すべき行を知るのか？
$ P_1が目印$ \sigmaを正しい復号結果の末尾に追加しておく
$ P_2は全ての行を復号していき、末尾に$ \sigmaがある復号結果を正しい結果として受け入れる
しかし、上記の方法は$ P_2に対する計算コストが大きすぎる
これを解決するのがPoint-and-Permute
鍵の一部に復号すべき行の情報を入れておく方法
鍵末尾の$ log{|X|}bitを翻訳すると、どの行を復号すべきか分かる
Managing look-up table size
テーブルのサイズが大きくなると効率的でなくなる
ブール回路はサイズが4なのでOK
$ Fをブール回路で表現したい
しかし、途中のゲートで平文を開示することはできない
回路$ Cの各ワイヤ$ w_iに対し、$ P_1はワイヤの値に対応する鍵$ k_i^0, k_i^1を割り当てる
$ k_i^0, k_i^1をワイヤラベルと呼ぶ
平文をワイヤバリュと呼ぶ
計算中に使用される入力とそれに対応する鍵をそれぞれ$ active ~ value,$ active ~ labelと呼ぶ
評価者は$ active ~ lavelのみを知ることができ、対応する$ valueと$ inactive ~ valueを知ることはできない
$ P_1は次のようなゲート用テーブルを作成する
https://gyazo.com/545ac128ddbdacea9ce998770688ddaf
ANDゲートであれば以下のようになる
https://gyazo.com/7920649f310e7fc3d33e7b071c882306
テーブルのそれぞれのセルはゲートで計算された出力に対応するラベルを暗号化する
評価者$ P_2は値を知ることなく、アクティブラベルを知ることができる
$ P_1は$ P_2に全てのゲート用テーブルを送信する
アクティブラベルの鍵が手に入れば復号できる
$ P_1の入力に対応したワイヤラベルの鍵はシンプルに送信する
$ P_2の入力に対応するワイヤラベルの鍵はOTにより送信される
復号した結果を$ P_1に送信する
復号にはデコーディング表を使ってラベルから対応するバリュを知る
デコーディング表は$ P_1が事前に送信しておく
circuit-based constructionはセミオネストモデルにおいて安全
$ P_1は何もメッセージを受け取らない
$ P_2は同じワイヤのラベルは一つしか知り得ない
一つのゲートにつき一つの暗号文しか復号できない
ラベルと平文の関係性を知ることも無い
ただし、最終結果のラベルと平文の対応表は持っている
$ Sim_{P_2}が得る最終的なviewは以下
全てのゲートのインアクティブな暗号文
最終結果のラベルとその平文
GMW(Goldreich-Micali-Wigderson) Protocol
Yao's GCを2パーティ以上に一般化した方法
ブール回路と算術回路の両方で使える
https://gyazo.com/fbd4c8fe182e628117b54bb2b0e2b99e
２パーティ（$ P_1, P_2）の場合
share化は以下のように行う
$ P_1, P_2の秘密情報をそれぞれ$ x, y \in \{0, 1\}^n とする
$ P_1は$ xの各ビット$ x_iに対し、ランダムビット$ r_i \in_{R} \{0, 1\}を生成する
全ての$ r_iを$ P_2に送信し、$ P_2はそれを$ xのシェアとする
$ P_1は各$ iにおける$ x_i \oplus r_iを$ xのシェアとする
$ P_2も同じ手順で$ yをシェア化する
最終的に$ P_1が所持するシェア
$ xのシェア$ x^1: $ \langle x_i \oplus r_i ~|~ i = 1,...,n \rangle
$ yのシェア$ y^1: $ \langle r_i^{\prime} ~|~ i = 1,...,n \rangle
最終的に$ P_2が所持するシェア
$ xのシェア$ x^2: $ \langle r_i ~|~ i = 1,...,n \rangle
$ yのシェア$ y^2: $ \langle y_i \oplus r_i^{\prime} ~|~ i = 1,...,n \rangle
各$ x_iの復元：$ x_i^1 \oplus x_i^2 = (x_i \oplus r_i) \oplus r_i = x_i \oplus (r_i \oplus r_i) = x_i \oplus 0 = x_i
$ P_1, P_2は回路$ Cをゲートごとに評価していく
あるゲート$ Gが入力ワイヤ$ a, bと出力ワイヤ$ cを持つとする
入力ワイヤ$ aは$ a^1 \oplus a^2 = aとなる2つのシェアに分かれる
$ P_1はシェア$ a^1, b^1を$ P_2はシェア$ a^2, b^2を持つ
それぞれがワイヤ$ a, bに対応する
$ a = a^1 \oplus a^2
$ b = b^1 \oplus b^2
回路$ CはNOT, XOR, ANDゲートで構成されるとして一般性を失わない
任意の回路をこれらの組み合わせで表現可能なため
NOTゲート
通信不要で実現できる
$ P_1がローカルで自分の入力に否定を取ることで効率的に実現できる
$ \overline{a} = \overline{a^1} \oplus a^2
XORゲート
$ P_1, P_2がローカルでXORをすることで実現
$ c = a \oplus bを求めたい
$ c = a \oplus b = (a^1 \oplus a^2) \oplus (b^1 \oplus b^2) = (a^1 \oplus b^1) \oplus (a^2 \oplus b^2) = c^1 \oplus c^2
$ P_1, P_2がローカルでそれぞれ以下を計算することで効率的に実現できる
$ c^1 = a^1 \oplus b^1
$ c^2 = a^2 \oplus b^2
ANDゲート
1-out-of-4 OT により実現する
$ P_1が送信者で$ P_2が受信者
$ P_2の取り得るシェア$ (a^2, b^2) \in \{(0, 0), (0, 1), (1, 0), (1, 1)\}全てに対しAND演算をした結果のテーブルを作って送る
$ S = S_{a^1, b^1}(a^2, b^2) = (a^1 \oplus a^2) \land (b^1 \oplus b^2)
以下の表を作る
ランダムビット$ r \in_R \{0, 1 \}
https://gyazo.com/db810af140cb8adcb12c1f51ecc98c22
$ P_1が送信者、$ P_2が受信者として、1-out-of-4 OTを実行する
$ P_1はテーブル行を4つの秘密の入力として使用する
$ P_2は、その2ビットシェアを対応する行の選択に使用する
$ P_1は$ rをゲート出力ワイヤ値のシェアとして保持
$ P_2はOTの実行で受け取った値を使用する
最終的に以下になる
$ P_1は$ rをもつ
$ P_2は$ r \oplus S()をもつ
ただし、$ S()は$ P_2がもつシェアに対応した値になる
n-パーティへの拡張
あるパーティ$ P_jは自分以外の全てのパーティ$ P_i ~(i \neq j)にランダムビット$ r_i \in_R \{0, 1\}を送信する
$ P_jの秘密情報$ x_jは以下のようにシェア化される
$ x_j^i = r_i ~ (i \neq j)
$ x_j^j = x_j \oplus r_1 \oplus ... \oplus r_{i-1} \oplus r_{i+1} \oplus ... \oplus r_n
パーティ$ P_1 , ... , P_nは回路$ Cをゲートごとに計算する
各ゲート$ Gを次のように計算する
XOR ゲート
$ c = a \oplus bを求めたい
$ a = a_1 \oplus a_2 \oplus ... \oplus a_n
$ b = b_1 \oplus b_2 \oplus ... \oplus b_n
ただし$ a_1,..., a_nと$ b_1, ..., b_nは$ a, bのシェア
2パーティの時と同様に、各パーティがローカルで XOR を行い送信する
$ c = a \oplus b = (a_1 \oplus ... \oplus a_n) \oplus (b_1 \oplus ... \oplus b_n) = (a_1 \oplus b_1) \oplus ... \oplus (a_n \oplus b_n) = c_1 \oplus ... \oplus c_n
各パーティがローカルでそれぞれ以下を計算することで効率的に実現できる
$ c_i = a_i \oplus b_i
$ a_i, b_iは$ P_iが所持するシェアなのでローカルで計算可能
ANDゲート
$ c = a \wedge bを計算する
ただし、$ a_1,..., a_nと$ b_1, ..., b_nは$ a, bのシェア
$ a = a_1 \oplus a_2 \oplus ... \oplus a_n
$ b = b_1 \oplus b_2 \oplus ... \oplus b_n
$ c = a \wedge b = (a_1 \oplus ・・・ \oplus a_n) \wedge (b_1 \oplus ・・・ \oplus b_n) \\ = (\underset{i = 1}{\overset{n}{\oplus}} \underset{j = 1}{\overset{n}{\oplus}} a_i \wedge b_j) = (\underset{i = 1}{\overset{n}{\oplus}} a_i \wedge b_i) \oplus (\underset{i \neq j}{\oplus} a_i \wedge b_j)
$ P_iはローカルで$ a_i \oplus b_iを計算する
各パーティのペア$ P_i, P_jで通信をして$ a_i \wedge b_jを計算する
それらを全てXORすることで最終的なANDの計算結果が得られる
BGW(Ben-Goldwasser-Wigderson) Protocol
Nパーティに対応したMPCプロトコル
CCDプロトコルとほとんど同じもの
「加算」「乗算」が定義された体$ F上で算術回路を計算する
シャミアの秘密分散法をベースとしている
値$ v \in Fのパーティによって保持されたシェアを$ \langle v \rangleと書く
ディーラー(シェアを分配する人)は$ t次のランダムな多項式$ pを選ぶ
$ p(0)が$ vである
各パーティ$ P_iが$ p(i)をシェアとして持つ
$ t個まではシェアが集まっても秘密情報$ vが得られない
$ t + 1個のシェアがあれば$ vを復元できる
$ BGWプロトコルの不変性は、算術回路で使われる各ワイヤー$ wに対して、パーティーは値$ v_wのシェア$ \langle v_w \rangleを持っていること
以降で、この不変性を担保するためのプロトコルを説明する
Input wires
$ P_iは秘密の値$ vをシェア$ \langle v \rangleとして全てのパーティに分配する
Addition gate
$ v_\gamma = v_\alpha + v_\beta を行う
$ \alpha, \beta：入力ワイヤ
$ \gamma：出力ワイヤ
各パーティでシェア$ \langle v_\alpha \rangle , \langle v_\beta \rangleを保持している
$ v_\alpha, v_\betaに対応する多項式$ p_\alpha, p_\betaとする
最終的に各パーティが$ \langle v_\alpha + v_\beta \rangleを得ることが目的
$ p_\gamma(x) = p_\alpha(x)+p_\beta(x)
$ v_\gamma = v_\alpha+v_\beta = p_\alpha(0)+p_\beta(0) = p_\gamma(0)
以下の計算をローカルで行う
各パーティ$ P_iが$ p_\gamma(i) = p_\alpha(i)+p_\beta(i)をローカルで計算する
加算ゲートは通信不要で実現できる
multiplication-by-constant gates
$ v_\gamma = k_\alpha \cdot v_\betaを行う
$ \alpha, \beta：入力ワイヤ
$ \gamma：出力ワイヤ
$ k_\alphaは定数
各パーティでシェア$ \langle v_\beta \rangleを保持している
$ v_\betaに対応する多項式$ p_\betaとする
最終的に各パーティが$ \langle k_\alpha \cdot v_\beta \rangleを得ることが目的
$ p_\gamma(x) = k_\alpha \cdot p_\beta(x)
$ v_\gamma = k_\alpha \cdot v_\beta = k_\alpha \cdot p_\beta(0) = p_\gamma(0)
以下の計算をローカルで行う
各パーティ$ P_iが$ p_\gamma(i) = k_\alpha \cdot p_\beta(i)をローカルで計算する
定数乗算ゲートは通信不要で実現できる
Multiplication gate
$ v_{\gamma} = v_{\alpha} \cdot v_{\beta} を行う
$ \langle v_\alpha \rangleと$ \langle v_\beta \rangleから$ \langle v_\alpha \cdot v_\beta \rangleが手に入れば良い
各パーティがローカルで掛け合わせると$ q(x) = p_{\alpha}(x) \cdot p_{\beta}(x)上の点を得ることになる
次数が$ 2tになり復元が困難
次数を減少させるステップを行う
$ q(0)はラグランジュ補間により次の線形和で表される
$ q(0) = \sum_{i = 1}^{2t + 1} \lambda_iq(i)
$ \lambda_iはラグランジュ係数
ラグランジュ補間：ある$ n次関数が通る一点を、$ n + 1点の情報から求める
次数を減少させるステップは以下の手順で行う
各パーティ$ P_iは閾値$ tのシェア$ \langle q(i) \rangleを作成して分配する
補間に必要な点の数である$ 2t + 1個のパーティが実行する
パーティは以下の計算をローカルで行う
$ \langle q(0) \rangle = \sum_{i = 1}^{2t + 1} \lambda_i \langle q(i) \rangle
加算と定数乗算はローカルで実施する
結果的に、閾値$ tの$ \langle q(0) \rangleを獲得できる
ただし、$ 2t + 1 \le n
したがって、BGW は$ 2t \lt nにおいて$ tパーティまでコラプトされても良い
過半数がホネストであれば良い
Output wires
ある出力ワイヤ$ \gammaについては、いずれそのワイヤに関わる各パーティは値の$ \langle v_\gamma \rangleシェアを保持することになる
各パーティはその値のシェアを、それぞれに容易にバラまけるので、最終的に全てのパーティに$ v_\gammaが行き渡る
MPC From Preprocessed Multiplication Triples
$ MPCプロトコルを構築しやすくするため、以下の２つのフェーズに分けて考えるパラダイムがある
前処理フェーズ(パーティーの入力が判明する前)
このフェーズでは各パーティに関係のある値を作成する
後のオンラインフェーズにて消費される
オンラインフェーズ(入力が与えられた後)
このパラダイムは、第6章で議論されている主要なMalicious-secure MPC protocolsでも使用される
BGWプロトコルにおいて唯一の実質的コストになるのは全ての乗算ゲートで要求されるコミュニケーションだが、関連するコストのいずれにおいても前処理フェーズに移行させる方法は明らかでない
なぜならその肝心のコストはオンラインフェーズでしか決定できない秘密値の値の操作に起因するので (すなわちコストが回路の入力に基づいているため)
そんな中、ビーバーさん(1992)がそのコミュニケーションの大部分を前処理段階に移行するBeaver triple(multiplication triple)を使って賢い解決策を考えた！すごい！
Beaver triple (multiplication triple) を用いた乗算
秘密値$ \langle a \rangle , \langle b \rangle , \langle c \rangleの3つを前処理フェーズで用意する
$ a, bは体$ F上でランダムに選ばれた定数
$ c = ab を満たす
各パーティはシェア$ \langle v_\alpha \rangle , \langle v_\beta \rangleを持つ
乗算ゲートを処理する毎に$ a, b, cは消費される
次の３つのステップを実行する
各パーティはローカルで$ \langle v_\alpha - a \rangleと$ \langle v_\beta - b \rangleを計算し、全パーティに送信する
各パーティは集まった$ \langle v_\alpha - a \rangle , \langle v_\beta - b \rangleから$ d = v_\alpha-a , e = v_\beta-bを復元する
$ d, eは全パーティに認知された定数となる
$ a, bの値が漏れない限り、$ d, eから秘密情報に関する情報は得られない
$ v_\alpha v_\betaを以下の計算式で求める
$ v_\alpha v_\beta = (v_\alpha-a+a)(v_\beta-b+b) \\= (d+a)(e+b) \\= de + db + ae + ab \\= de + db + ae + c
このうち、$ d, eは既知の情報であり、$ \langle a \rangle, \langle b \rangle, \langle c \rangleは各パーティが事前に保持しているので、以下の計算をローカルで実行することで$ \langle v_\alpha v_\beta \rangleを得る
$ \langle v_\alpha v_\beta \rangle = de + d \langle b \rangle + e \langle a \rangle + \langle c \rangle
結果的に、乗算ゲート毎に2つの値をブロードキャストするだけで実現できる
ただし、事前のトリプル生成コストが発生することに注意
Abstraction
Beaver triple はシャミア秘密分散法の次元削減の処理を取り除くことができる
$ a, b, cはシェアの状態で全てのパーティに共有されている
その値を知ることは無い
ただし、秘密の値$ v_iを分配する$ P_iは$ v_i - aを行うなために$ aを知っている
Instantiations
半数未満がコラプトパーティでも問題ない
BMR(Beaver-Micali-Rogaway) Protocol
今まで提案されてきたGMW, BGW, CCDは全てFを計算する回路Cの深さのラウンドが線形オーダーだが、BMRは定数オーダー
$ t \lt nにおける任意の$ tのセキュリティを達成できる
BMRのメインのアイデアはGCの生成を分散して行うこと
どのパーティもGC生成における秘密情報(ラベルと暗号文との関係性)を分からなくするため
ワイヤラベルの生成はMPCを用いて全パーティが並行して実行する
GCを生成する回路$ C_{GEN}は全ての計算回路$ Cに対して定数の深さを持つ
並行にゲートの処理をするため、GCの生成は計算回路$ Cの深さから独立している
MPCで計算された$ C_{GEN}はGCを出力する
GCは指定のプレイヤー($ P_1など)に送信される
あとは、アクティブなインプットを上記の指定パーティに届ければ良い
暗号化されたテーブルを分散して生成するのはハイコスト
MPC内でハッシュ関数や擬似乱数関数の評価が必要であるため
MPC外のローカルで実行する方法が提案されている
入力$ w_a^{v_a}, w_b^{v_b}、出力$ w_c^{v_c}のゲート$ G_i
$ w_a^{v_a}はサブラベル$ w_{a,j}^{v_a}の結合
$ w_{a,j}^{v_a}は$ P_jにより生成される
対応するGCの行は以下のように表される
$ e_{v_a, v_b} = w_c^{v_c}\underset{j=1}{\overset{n}{\oplus}}(F(i,w_{a,j}^{v_a}) \oplus F(i,w_{b,j}^{v_b}))望ましい
$ F : \{0,1\}^\kappa \rightarrow \{0,1\}^{n \cdot \kappa}は$ \kappaビットを$ n \cdot \kappaに拡張するPRG(pseudo-random generator)
Garbled Table は、ほぼ完全にローカルで実行される
各パーティ$ P_jがローカルで$ F(i, w_{a, j}^{v_a}) \oplus F(i, w_{b,j}^{v_b})を計算しMPCに送信する
MPCは受け取った値を全てXORすることで、Garbled rowを生成する
フリップビットを利用して平文とアクティブラベルの対応関係を隠す
各プレイヤーはワイヤー$ w_aに$ nフリップビットのXORをとった$ f_{a, j}を加える
$ f_a = \oplus_{j=1...n} ~ f_{a, j}がワイヤラベル$ w_a^vに対応する平文のビットを示す
フリップビットの追加によって、どのプレイヤーもワイヤのフリップビットを知ることができない
Information-Theoretic Garbled Circuits
情報理論的安全性を持ったGCを構築することを考える
一般的なGCはテーブルを暗号化して送信しているので、秘密鍵が逆計算され得る。
計算量的安全性に担保されているので、情報理論的安全性ではない
（パーティ間ではなく）ワイヤ間でシェアを保持することで秘密情報が漏れない
トレードオフは通信帯域とレイテンシ
通信できるデータ量がGCと比較して少ない
大きな計算回路が必要とされるような場合に必要となると考えられる
機械学習など
情報理論的安全性は典型的に高いコストをもって実現されるが、これはその限りでは無い
単一ビットの暗号化で実現できることで、高いパフォーマンスを発揮できる
ビットごとの排他的論理和とビットのシャッフルによって情報理論的安全な暗号化される
典型的なAESなどとは異なるため、暗号文が短くなる
Kolesnikovによる$ GESS~(Gate~ Evaluation~ Secret~ Sharing)
最も効率的な情報理論的安全性を持ったGCである
2パーティでブール式$ Fを以下の通信複雑度で実現できる
$ \sum d^2_i
$ d_i：$ Fの$ i番目の葉の深さ
Booleanゲート$ Gによる暗号化の下で計算を行う
$ Gの出力ワイヤラベルは２つのシークレット
$ P_1は2つの入力ワイヤのラベルに対応した４つのシェアを作成する
GESSは、シェア(1ワイヤあたり1シェア)の妥当な組み合わせによって出力ワイヤの対応ラベルが再構築できることを保証する
GESSはGCの一般化とみなせる(garbledテーブルを必要としないので)
シェア化処理はゲート毎に行う(Yao's GCのアプローチと同じように)
ただし、値のデコードも再構築も行わない
２つの入力を持つゲート$ Gを考える
出力として有り得るのが$ s_0, s_1である時、$ P_1は入力ラベル$ (sh_{10}, sh_{11}), (sh_{20}, sh_{21})を生成する
$ (sh_{1i}, sh_{2j}) ~ (i,j \in \{0, 1\})は$ G(i,j)の再構築を可能にする
しかし、再構築に必要な情報以外は持たない
$ P_2が入力に対応したシェアを獲得した時、出力ワイヤのラベルを再構築することができる
しかし、それ以外の情報は持たない
確かにあり得るゲートの出力は秘密なまま共有され、入力ワイヤの復号(シェア)によって再構築されていることがわかる
https://gyazo.com/9372d06d563a44cf7372d90450963992
２入力バイナリゲートの$ GESS
ゲート関数$ G:\{0,1 \}^2 \rightarrow \{00,01,10,11 \}
これはBooleanゲートを一般化したものと言える
e.g. $ G(0,1)=01
秘密情報の定義域を$ D_s = \{0,1\}^nとする
秘密情報$ s_{00},...s_{11} \in D_s
秘密情報$ s_{ij}は出力ワイヤの値$ G(i,j)に対応する
$ GESSの直感的な説明
まず、ランダムに２つの文字列$ R_0, R_1 \in_R D_sを生成し、シェア$ sh_{10}, sh_{11}とする
$ sh_{10}, sh_{11}はそれぞれ１つ目の入力ワイヤの出力0と1に対応する
同様に、$ sh_{20}, sh_{21}はそれぞれ２つ目の入力ワイヤの出力0と1に対応する
$ sh_{20}は以下の状態を満たしたい
$ s_{00}：$ sh_{10}が与えられた時
$ s_{10}：$ sh_{11}が与えられた時
同様に$ sh_{21}は以下の状態を満たしたい
$ s_{01}：$ sh_{10}が与えられた時
$ s_{11}：$ sh_{11}が与えられた時
$ sh_{20}は２つのブロックから構成される
$ s_{00} \oplus R_0(sh_{10})は、$ R_0(sh_{10})と合わさり$ s_{00}を復元する
$ s_{10} \oplus R_1(sh_{11})は、$ R_1(sh_{11})と合わさり$ s_{10}を復元する
$ sh_{21}も同様に構成される
$ s_{01} \oplus R_0(sh_{10})は、$ R_0(sh_{10})と合わさり$ s_{01}を復元する
$ s_{11} \oplus R_1(sh_{11})は、$ R_1(sh_{11})と合わさり$ s_{11}を復元する
下図のWire 2の左ブロックは$ R_0と組み合わさるべきである
同様に、右ブロックは$ R_1と組み合わさるべきである
そこで、$ R_0には$ 0を、$ R_1には$ 1を先頭ビットに追加する
先頭ビットを確認することで、どちらのブロックを用いて復元するかが分かる
$ 1を確認したら、ブロックを左右逆にすることで実現
最終的には、$ R_0, R_1の先頭ビットの数字から情報漏れすることを防ぐために以下の手順をふむ
ランダムビット$ bを生成する
$ b=1ならば、Wire 2のブロック順を両方とも逆転する
$ b, \bar{b}をそれぞれWire 1の入力$ 0,1の先頭ビットとする
Wire 1の先頭ビットはポインタとする
$ 0：左ブロックと指定
$ 1：右ブロックを指定
Wire 2の指定されたブロックとWire 1をXORすることで復元できる
ただし、Wire 1の先頭ビットは除く
https://gyazo.com/ab4b714292fcf5b7ba7fe9824b4bbff2
Reducing Share Growth
Wire2のシェアが秘密情報の2倍の大きさになるのが問題
指数関数的シェアの拡大を防ぐための方法が考案されている
ANDとORのみ説明する
NOTゲートは生成者がビットを反転させれば良い
XORは後ほど説明する（関係するYao' GCの改善に依存するため）
Wire 2の左右のブロックは同じ意味を表す場合がある
AND : $ s_{00} = s_{01}
OR : $ s_{10}=s_{11}
Wire2の2つのシェアを、1つのブロックを除いて同じものと見なすことで、サイズを減少させる
4つのシェアがそれぞれ$ nブロックから成り、$ j番目のブロックのみで異なるとする
$ s_{00} = (t_1, ... , t_{j-1} , t_j^{00} , t_{j+1}, ... , t_n)
$ s_{01} = (t_1, ... , t_{j-1} , t_j^{01} , t_{j+1}, ... , t_n)
$ s_{10} = (t_1, ... , t_{j-1} , t_j^{10} , t_{j+1}, ... , t_n)
$ s_{11} = (t_1, ... , t_{j-1} , t_j^{11} , t_{j+1}, ... , t_n)
ただし、$ t_i, t_j^{00}, t_j^{01}, t_j^{10}, t_j^{11} \in \{0,1 \}^k
$ j番目の列以外の全ての列は同じブロックをもつ
$ jは秘密のまま
アイディアは「列ごとに」秘密情報をシェアすること
各列を準秘密情報のタプルとして扱い、シェア化して別々に共有する
$ n = 3, j = 2の場合の例
https://gyazo.com/b3048958cc0620b97cfc48174ee100f2
1列目をシェア化する場合について考える
4つの全てのサブシークレットは等しい($ = t_1)
Wire 1の両方のサブシェアを、ランダムな文字列$ R_1 \in_R D_sとする
Wire 2の両方のサブシェアを$ R_1 \oplus t_1とする
サブシークレット：$ t_1, t_2, t_3
サブシェア：$ R_1, R_1 \oplus t_1, R_2, R_2 \oplus t_2, R_3, R_3 \oplus t_3
3列目も1列目と同様にシェア化する
2列目は、図の通りにWire 2を構築して共有することで、$ GESSのような先頭ビットの反転やブロックの並び替えを省略する
復元は対応するシェアのブロックの排他的論理和を取ることで行う
例: $ sh_{10}, sh_{21}が与えられた場合、$ s_{01}を復号する
$ s_{01} = (R_1 \oplus (R_1 \oplus t_1)), ~ R_2 \oplus (R_2 \oplus t_2^{01})), ~ R_3 \oplus (R_3 \oplus t_3))
このままだと、ブロックの並び方で秘密情報が漏れてしまう
同じランダム並び替え$ \piをWire 2のブロックに適用する
2ビットのポインタをWire 1のブロックそれぞれに追加する
列1,3は二つのシェアに同一のポインタを追加する
列2は異なるポインタを各シェアに追加する
e.g. $ R_1:1, $ R_2:2, $ R_2':3, $ R_3:4
$ Gは$ OR,ANDゲートのどちらかであるため、両シェアのタプルが「$ j番目のブロック以外のタプルのシェアは等しい」という性質を保持する
これにより$ OR, ANDゲートへ$ GESSの繰り返し適用が可能になる
Oblivious Transfer
セキュアに計算するために必要不可欠なプロトコルのひとつ
OTを共通鍵で実現する問題は$ P \neq NPを示唆している（難しい）
OTは公開鍵により実現されているので計算量が多い
Beaverは、バッチOT（まとめて）を実行する際には公開鍵の操作回数は少なく済むと述べた
擬似ランダム関数は回路で表現され、MPCで実行されるため、non-black-boxで構築できる
Ishaiは超絶効率的なバッチOTを提案した
バッチ全体で$ κ回の公開鍵処理と、OT毎に2,3のハッシュで実現できる
公開鍵に基づいたsemi-honest OT
前提
$ S：送信者
秘密の入力$ x_0, x_1 \in \{0, 1\}^nを持つ
$ R：受信者
ビット$ b \in \{0, 1 \}を選択する
プロトコル
$ Rは秘密鍵・公開鍵のペア$ sk, pkを生成する
さらに$ Rはランダムな鍵$ pk^{\prime}を公開鍵と同じ空間から生成する
$ b = 0の時
$ Rは鍵のペア$ (pk, pk^{\prime})を$ Sに送信する
$ b = 1の時
$ Rは鍵のペア$ (pk',pk)を$ Sに送信する
$ Sは鍵のペア$ (pk_0, pk_1)を受け取る
暗号化した$ e_0 = Enc_{pk0}(x_0), e_1 = Enc_{pk_1}(x_1)を$ Rに送り返す
$ Rは$ e_0, e_1を受け取ったら、秘密鍵$ skを用いて$ e_bを復号する
$ Rはもう一方の暗号文に対応する復号鍵を持っていないため、$ e_bのみしか復号できない
ただし、$ Rがランダムな鍵$ pk^{\prime}とペアになる秘密鍵$ sk^{\prime}を作成していたら成立しない
$ Sの入力$ x_0, x_1をどちらも復号できてしまう
つまり semi-honest を前提として初めてセキュアが保証される
Public Key Operations in OT
上記の単純な実装の場合、OT毎に送信者、受信者に1回の公開鍵処理が必要になる
ブール回路のYao's GCの場合、回路を実行するパーティの入力ビット毎にOT実行が必要
算術回路のGMWのようなプロトコルの場合、各ANDを評価する毎に1つのOTが必要
したがって、いかにOTの公開鍵処理を減らすことができるかが肝になる
Beaver's non-black-box construction
Yao's GCの公開鍵暗号の処理回数を小さくすることでOTの数を多項式量にすることができた
前提
$ Sは送信者
$ Rは受信者
$ mはバッチOTにおけるOTの数
$ m個のOTをバッチにしたという意味
$ Sの入力は$ m個の秘密情報のペア$ (x_1^0, x_1^1), ... , (x_m^0, x_m^1)
$ Rの入力は$ mビットの選択用のバイナリ列$ b = (b_1, ..., b_m)
関数$ \mathcal{F}を実現する回路$ Cを構成する
$ Rから少数のビットを入力として受け取る
ランダムに選ばれた$ \kappaビットの文字列$ rを$ Rの入力とする
$ Gを、$ \kappaビットの入力値を$ mビットに展開する擬似乱数生成器とする
$ Rは$ b \oplus G(r)を$ Sに送信する（乱数によるマスク処理を意味する）
$ G(r): $ mビットのランダム文字列（$ Rの入力バイナリ列$ bの長さ$ mと揃えるために使用）
$ Sは以下を関数$ Fに入力する
$ m個の秘密情報ペア$ (x_1^0,x_1^1), ..., (x_m^0, x_m^1)
$ mビット文字列$ b \oplus G(r)
関数$ Fは文字列$ rが$ Rにより与えられた時、$ G(r)と$ b \oplus G(r)から$ bを得る
さらに、$ Fは$ Rに対応する秘密情報$ x_{b_i}を出力する
$ m回のOTを実現するために、$ \kappa回の$ OTを行えば良い
$ Rからはたかが$ \kappaビットの入力しか与えられないため？？？？？
1OTが何を示しているのかがわかればOK
Reducing the number of public key operations
上記の方法は実利用には非効率である（大きな回路を処理したいので）
ゴールは共通鍵暗号による$ m回のOTである（$ k << m）
$ kは、計算理論的安全なパラメータ$ \kappaに基づいて選ばれる
以下にIshaiによる方法を示す
semi-honest環境下で、$ m1-out-of-2 OTを達成している
$ Rは以下の条件を満たすように選択ビット$ r \in \{0,1\}^mと$ m \times k行列$ T, Uを生成する
$ j行目の行$ t_j, u_j \in \{0, 1\}^k
行列はランダムに選ばれる
$ t_j \oplus u_j = r_j \cdot 1^k \stackrel{\mathrm{def}}{=} \begin{cases}1^k ~~ if ~ r_j = 1 \\ 0^k ~~ if ~ r_j = 0 \end{cases}
$ r_j = 0なら$ T, Uの$ j行目の値は全て等しい
$ r_j = 1なら$ T, Uの$ j行目の値は全て異なる
$ k回のOTを行う（$ k << m）
$ Sは任意の文字列$ s \in \{0, 1\}^kを選択する
$ i番目のOTにおいて$ Rは$ t^iと$ u^iを送り、$ Sは$ s_iによってどちらか一方を受け取る
$ t^iと$ u^iはそれぞれ$ Tと$ Uの$ i列目を指す
$ s_i = 0の時$ q^i = t^i
$ s_j = 1の時$ q^i = u^i
$ mビットの文字列をOTで送りたい時に、それらをある共通鍵で暗号化してOTを使わずに送信し、両パーティ共通のランダムオラクル$ Hがその共通鍵を生成できる短い文字列を代わりにOTで送信することで、実質$ k( << m)ビットのOTで$ mビットのOTを実現できる
上記のように$ q^iを定義すると、結局$ Qは次のように書ける
$ q^i : $ Qの$ i列目
$ q_j : $ Qの$ j行目
$ q_j = t_j \oplus (r_j \cdot s) = \begin{cases} t_j ~~ if ~ r_j = 0 \\ (t_j \oplus s) ~~ if ~ r_j = 1 \end{cases}
$ Hは$ S, Rで共通のランダムオラクル
$ Sは$ H(q_j)と$ H(q_j \oplus s)を計算する
$ Rは$ H(t_j)を通じて、どちらか一方しか計算できない
$ q_jは$ t_jか$ t_j \oplus sのどちらかに等しい
これは$ Rの選択したビット$ r_jに基づく
$ t_jは$ q_jか$ q_j \oplus sのどちらかに等しいことと同値
$ t_jを知っていることは、$ q_j, q_j \oplus sのどちらかを知っていることになる
$ Rは$ sが分からないため$ H(q_j)と$ H(q_j \oplus s)から何の情報も得られない
最終的に$ Rと$ Sがもつ情報は以下になる
$ R:
$ T, U, r, H(t_j)
$ S:
$ Q, s, H(q_j), H(q_j \oplus s)
OTを行う手順
$ Sが任意の秘密情報$ A, Bを$ H(q_j)\oplus A, H(q_j \oplus s)\oplus Bとして$ Rに送信する
$ Rは自身の$ H(t_j)を用いて$ H(q_j)\oplus Aと$ H(q_j \oplus s)\oplus Bの復号を試みる
$ Rは片方のみ復号に成功し、情報を得る
$ Sは$ Rの受け取った値を知ることはない
これを、二つのシークレット$ s_0, s_1を受け取る、より一般的な1-out-of-2 OTに拡張するために以下の手順を追加する
$ Sは、さらに追加で2つのOTシークレットを、2つの鍵$ H(q_j)と$ H(q_j \oplus s)によって暗号化し、2つの暗号文(例: $ H(q_j) \oplus s_0, $ H(q_j \oplus s) \oplus s_1) )を$ Rへ送信する
$ Rは$ r_jの値によって$ H(q_j) \oplus s_0もしくは $ H(q_j \oplus s) \oplus s_1のどちらかのみを受け取る
$ r_j = 0（$ t_j = q_j）の時：$ H(q_j) \oplus s_0
$ r_j = 1（$ t_j = q_j \oplus s）の時：$ H(q_j \oplus s) \oplus s_1
Coding interpretation and cheaper$ 1-out-of-$ 2^\mathscr{l}OT
上記のIKNPプロトコルを$ 1-out-of-2^lOTに拡張する方法
$ r_jを$ C(r_j)に置き換えて、次元を拡張して実現
詳細は割愛
Custom Protocols
回路ベースのプロトコルは回路の規模に応じた線形の帯域コストがかかってしまう
大きめの計算はコストが高すぎることにより制限される
RAM(Random Access Machine:任意のメモリ領域にアクセスできる計算機)と比較して大きなデータ構造を処理するのは非常にコストが高い
解く問題によってカスタムするのが一般的
その中でも、以下のPSIは特筆するに値する
Private Set Intersection（PSI）
PSIのゴールは、各パーティの入力集合の積集合を計算すること。
ただし、集合の情報を公開することはない
サイズの上限の情報は漏れる
PSI from OPRF(Obliviouse PRF)
PSIをOPRFによって実現するプロトコルがある
PSSZ (Pinkas-Schneider-Segev-Zohner)プロトコル
以下割愛
4. Implementation Techniques
最初の一般的な実装は2004年のFairplay
高水準の関数記述言語(Secure Hardware Description Language:SHDL)を持つ
回路に変換し、実行する環境を含んでいる
4章ではYao's GCプロトコルの改善の話が主
しかし、一部は他のプロトコルにも適用できる
Fairplayのベンチマーク
10個の16ビットの数字を含む2つのソート済みの配列の中央値を求めるベンチマーク
4383ゲートを要し、ローカルネットワークにて7秒かかった
Less Expensive Garbling
Garbled Row Reduction
FreeXOR
FreeXOR: Integrating GESS XOR into GC
5. Oblivious Data Structures
6. Malicious Security
7. Alternative Threat Models
8. Conclusion
MPCは実用レベルの速度で計算ができるようになっている
アクティブセキュリティで10Gbps LANで2PCであれば80万ゲート/sで計算できる
パッシブセキュリティで10Gbpsで3PCであれば10億ゲート/sで計算できる
しかし、以下の課題により、実用例が少ないことが問題になっている
1. コスト
計算ゲートの数と比例して通信帯域が必要になる
一般的に、通信帯域は単一のクラウドデータセンターであれば、コストはかからない
しかし、単一のデータセンターに全てのマシンが置いてあるようなモデルではMPCの意味がない
異なる環境における計算機を繋ぐ場合には、通信帯域のコストは無視できないものになる
対策
通信帯域を大量に使用する場合には、準同型暗号などを組み合わせた方法を用いること
ただし、まだ発展途上の研究である
Private Set Intersection, RAM-MPC, ABY
用途に専用のMPCを構築することで不要な通信コストを下げる
ただし、専用のMPCを構築する開発コストと、それが他のものに活かせるかが重要になる
ただし、CPU開発元のIntelやARMが実装と鍵の管理を行うので、単一障害点になる
2. 情報漏れとのトレードオフ
計算アルゴリズムの計算効率改善の限界値はすでに示されている
Zahur et al., 2015
より一層の効率化を望む場合は、セキュリティレベルとのトレードオフになる
対策
まだ改善の余地が残されているORAMプロトコルの改善
ランダムメモリーアクセスの方法が非効率
大きなデータを扱う場合には、ORAMのアクセス速度がMPCの計算の限界値になる
3. 計算結果の情報漏れ
MPCは入力データの秘匿性は保証するが、計算結果は秘匿化しない
使用用途によっては入力データよりも計算結果の方が秘匿にしたいことがある
対策
end-to-endの秘匿化MPCが提案されているので、その発展を待つ
計算結果に対する秘匿化の処理を行う
4. 信頼の問題
MPCの理論的な安全性だけでは、意味のある信頼を得ることができない
全ての状況に置いて安全であることを保証できない
MPCのソフトウェアを提供している会社や、各デバイスの開発会社、OSの開発会社などが不正や、深刻なバグを含んでいる場合に、サイドチャネル攻撃が全くないことを保証することは計算機における本質的に難しい問題である
対策
MPCが持っている本質的なデータの暗号化（秘密分散化）によって、単一のノードが乗っ取られたり、サイドチャネル攻撃されたとしても、意味のあるデータが流出することがない点をアピールすること
この性質は、準同型暗号や、TEEでさえも持たない性質である
MPCが提供している安全性とそこから生まれる価値を、一般の人が理解し、教授できるようにすることが必要
作者のまとめ
個人のデータが企業によって不適切に扱われていることが増えており、ヨーロッパではGDPRにより、企業が個人情報を適切に扱うことを義務付ける法律が成立している
MPCは（もしくは秘匿計算の分野）にはまだチャレンジングなことが残っているが、上記の個人情報に関する課題を解決することができる力がある。
秘匿計算の分野は、まだ若く、刺激的であり、作って、開発して、実用化する機会がたくさんあります！
参考文献
公式
A Pragmatic Introduction to Secure Multi-Party Computation
David Evans, Vladimir Kolesnikov, Mike Rosulek