📝
【MPC技術入門②】MPCのセキュリティ定義
はじめに
この記事は、セキュアマルチパーティ計算（secure multi-party computation：MPC）技術の入門に適した書籍である「A Pragmatic Introduction to Secure Multi-Party Computation [1]」を参考にした、MPC技術解説の２回目の記事となります。今後もMPC技術入門シリーズとして解説していく予定です。
今回はMPCのセキュリティの定義について解説します。
MPC のセキュリティの定義を知ることで、MPC がどのような安全性を保障しているのか理解することができます。
MPC技術解説入門シリーズの１回目の記事はこちらです。
コンテンツの構成
MPCのセキュリティは理想世界と現実世界という概念を使用することで定義されています。まずは、1節でそれぞれがどういったものなのかを解説します。
次に2節では、理想世界と現実世界の議論を展開する際に重要となる識別不可能性について解説します。
その後の3節では、基本的な攻撃者のモデルであるsemi-honest セキュリティとmalicious セキュリティについての定義を解説します。
また4節では、暗号の安全性分析フレームワークを提供する理論である、Universal Composability（プロトコルの汎用的結合可能性） について解説します。
最後に5節では、MPCのセキュリティに関するいくつかのバリエーションを紹介します。
MPCのセキュリティの定義
1. 理想世界と現実世界によるセキュリティ定義
MPCのセキュリティは、理想的な機能を定め、現実のプロトコルがそれと同等の性能を持っていることと定義します。そのために、理想世界と現実世界という概念を導入します。
理想世界（Ideal world）
MPCの目標は、 人の参加者が、自分の入力 を秘匿したまま（中間的な計算結果も明かさずに）、共同で を計算することです。これを行う理想的な方法は、必ず信頼できる参加者 （すなわち、 だけには情報を明かしてもよい）という理想的な参加者を導入すると、次のように表現できます。
- 番目の参加者 は、必ず信頼できる参加者 に秘密の入力 を送ります。
- はそれぞれの秘密の入力を受け取り、 を計算します。参加者 に対する出力を とします。
- はそれぞれの参加者 に計算結果 を返します。
図にすると次のようになります。
このように、必ず信頼できる参加者 を導入することで、MPCの目標とする状態を表現することができます。
しかし、このような の存在は現実的ではありません。このような理想世界は、現実のプロトコルの安全性を判断するための基準として用いられます。
ここで、理想世界で攻撃者が行うことができる攻撃を考えておきます。
攻撃者は完全に信頼できる参加者である を制御することはできませんが、他のいくつかの参加者を制御することができるとします。
このとき、攻撃者が得ることができる情報は （攻撃者は を制御している）のみです。これは、 が知っている情報が秘密情報 と受信するメッセージ のみであることから明らかです。
次に、現実世界について見ていきます。
現実世界（Real world）
現実世界では、理想世界の のように必ず信頼できる参加者は存在しません。そこで、現実世界では、プロトコル を用いて相互に通信することで の機能を実現することを目指します。
ここで、プロトコル とは次のようなものです。
- プロトコル は各パーティ に対して、「次のメッセージ関数」 を指定する。
- の入力
- セキュリティパラメータ
- パーティの入力
- ランダムテープ*
- が受信した全てのメッセージ
- の出力
- 次に送るメッセージ
- 宛先
- 特定の出力（終了指示など）
ランダムテープは確率的チューリング機械が持つテープのひとつで、計算開始時にその内容がランダムに決定されるものです。ここでは、計算に必要な乱数を提供するものだと思っておけばよいです。
このように定義した上で、「現実世界で攻撃者が得る全ての情報が理想世界でも得られるとき、現実世界は理想世界と同等以上に安全である」ということができそうです。
プロトコルはこの状態を目指します。
2. 識別不可能性
現実世界で攻撃者が得る全ての情報が理想世界でも得られるということは、「現実世界で攻撃者が得る全ての情報と理想世界で得られる情報が識別不可能である」ということです。
MPCのセキュリティの定義は「理想世界と現実世界で攻撃者が得る情報についての確率分布を定義し、想定する全ての入力についてそれらを集めてきたものが識別不可能であること」と定義されます。
ここでは、識別不可能性および、それを定義するために必要な用語などを定義していきます。
確率変数
確率変数 は、標本空間 上の値をとる変数であり、 となる確率 が定まっています。
確率分布
確率変数がある値をとる確率を与える関数です。すなわち、確率変数 の確率分布 は、 を満たします。
確率分布族（distribution ensemble）
添字付けされた確率分布の集まりです。すなわち、 であり、 は添字集合で は添字 に対応する確率分布です。
本記事では、特に、確率分布族 を用います。 はセキュリティパラメータ と入力 を受け取ったときの計算結果についての確率分布です。すなわち、 は各入力に対する確率分布を（入力と対応付けて）集めたものです。
無視可能函数（negligible function ）
無視可能函数 は極限において任意の多項式よりも緩やかに増加する関数です。
すなわち、任意の正値多項式 に対し、有限の が存在し、 について、
が成り立ちます。
セキュリティパラメータ
以降、セキュリティパラメータ が登場します。これは、考慮するアルゴリズムのステップ数や、入力長などに、 の多項式による制限を与えるものです。
現実の計算資源には限りがあるので、それを表現しています。
識別不可能性
２つの確率分布族 が与えられるとします。
ここで、任意の定数, 多項式 が与えられて、任意の に対し、 任意のアルゴリズムについて、次のような無視可能函数 が存在するとき、は識別不可能といい、 で表します。
意味合いとしては、 を と のどちらが与えられたのか判定しようとするアルゴリズムだと捉えた場合、どちらを与えてもほぼ同じ答えを返してくるので、どんな判定関数 を作っても とを識別できないということを表現しています。
また、識別不可能性には、計算量的識別不可能性と統計的識別不可能性があります。
をnon-uniform な多項式時間アルゴリズム（固定長の入力に対するアルゴリズムを集めたもの）としたとき計算量的識別不可能性の定義となり、 の計算量を考慮しないとき統計的識別不可能性の定義となります。
3. 攻撃者のモデル
Semi-Honest モデル
ここでは、semi-honest モデルに対して、理想世界と現実世界を考えることでセキュリティを定義します。
semi-honest（passive, honest-but-curious）モデルで想定する攻撃者は、プロトコルには従うものの、計算の過程で得られた情報から秘匿された情報を得ようとします。このとき攻撃者が得る情報は、攻撃者にコントロールされている全ての参加者が得た情報を統合したものとして考えます。
semi-honestモデルにおける、現実世界での攻撃者について考えます。
ある参加者 が計算の過程で得る情報は、次の３つで構成されています。
- の入力
- のランダムテープ
- がプロトコル実行中に受信したすべてのメッセージ
これを、 のビュー とよびます。
ここで、攻撃者 が得る情報は、攻撃者がコントロールしている不正な参加者のビュー の和集合です。図にすると次のようになります。
また、攻撃者ができることは、このビューの和集合を入力とする（現実的な時間で実行可能な）関数を実行して、なんらかの情報を得ることだけです。したがって、単に「ビューの和集合全体を出力する」という攻撃のみを考えればよいです。
次に、理想世界での攻撃者について考えます。
理想的な世界で攻撃者が得る情報は、敵がコントロールしている参加者 の入力 と が から受け取った出力 のみです。
このとき、これらの情報を用いて、攻撃者のビューの和集合のようなものをつくることができるのであれば、前節で説明した通り、実世界において攻撃者が行える任意の攻撃を理想的な世界でも行えることになります。
このような、理想的な世界で攻撃者が得る情報からプロトコルを実行したときに攻撃者が得る情報を生成する関数をシミュレータと呼びます。シミュレータの動作を図にすると次のようになります。
このようなシミュレータが存在することを示せば、semi-honest モデルにおいてプロトコルはセキュアであるといえます。
ここまでの議論を数式を用いて追っていきましょう。
をプロトコル、 を が実行する関数、 を不正な参加者の集合、 をシミュレータのアルゴリズムとします。
ここで、次の確率分布を定義します。
- ここで、各参加者 は、秘密の入力 を用いてプロトコルを逸脱することなく実行する。このときの、参加者 の最終的なビューを とし，参加者 の最終的な出力を とする。
- 出力：，
- 攻撃者のビューの集合と、それぞれの参加者の出力を得る。
- 各参加者の出力を計算する。
- 出力：，
- 不正な参加者の集合とそれらの入出力をシミュレータ関数に入れた時の出力と、全ての参加者の出力を得る。
また、これらの確率分布からなる確率分布族 を
とします。
これらの定義を用いて、semi-honestモデルでのプロトコル の安全性を次のように定義します。
定義１. プロトコル のsemi-honest安全性
プロトコル がsemi-honestな攻撃者の存在下で を安全に実現するとき、任意の不正な参加者の集合 に対し、次のような確率分布族を持つシミュレータ が存在する。
直感的には、この定義の意味するところは、「理想世界の不正な参加者の入出力の情報を用いて、現実世界の攻撃者のビューを生成できる」ときに安全といえるということです。
ところで、 や の出力には が含まれています。
(不正な参加者が存在しない)のとき、であり、となります。
これが識別不可能ということは、理想世界での出力とプロトコルの出力が（ほぼ）同じであることを表しています。すなわち、 を含めることで、プロトコルの出力の正当性を表現しているといえます。
Malicious モデル
malicious（active）モデルで想定する攻撃者は、秘匿された情報を得るために、不正な参加者をそれぞれ所定のプロトコルから逸脱させることができます。そのうえで、semi-honestな攻撃者と同様に、得られた情報に対して分析を行うことができます。
semi-honestモデルと同様に、理想世界との比較によってセキュリティを定義します。この際に、考慮すべき重要な追加事項が２つあります。
- 正当な参加者の出力への影響
プロトコルを逸脱する参加者によって、正当な参加者の出力が影響を受ける可能性があります。また、不正な参加者の出力は自由に変更できるため、考慮しません。
- 攻撃者の入力の抽出
正当な参加者は入力が与えられると、あとはプロトコルに従って行動するため、理想世界でもその入力を に与えることができます。一方、malicious な攻撃者の入力は、そのままではうまく に与えることができません。そこで、malicious な攻撃者の現実世界での行動に対応する理想世界での入力をシミュレータに抽出させます。
が攻撃者のプログラムを表すとき、不正な参加者の集合をとし、シミュレーター によって選択された不正な参加者の集合を とします。
ここで、現実世界と理想世界の確率分布を次のように定義します。
- 各正当な参加者（）は与えられたプライベートな入力 を用いて、正しくプロトコルを実行する。不正な参加者の入力は によって選択され、プロトコル実行時に送信するメッセージについても によって選択される。
- 各正当な参加者 の出力を とし、参加者 の最終的なビューを とする。
- 出力：
- 攻撃者のビューの集合と，正当な参加者の出力を得る。
上記を図示すると、参加者と攻撃者の動作は次の図のようになります。
- まず、 を入力の集合 を出力するまで実行する。
- 次に、各参加者の出力を計算する。
- 次に、 に出力の集合 を与え、 の出力を とする（は攻撃者のビューをシミュレートしている）。
- 出力：
上記を図示すると、シミュレータの動作は次の図のようになります。
また、これらの確率分布からなる確率分布族 を
とします。
これらの定義を用いて、malicious モデルでのプロトコル の安全性を次のように定義します。
定義２. プロトコル のmalicious安全性
プロトコル がmalicious な攻撃者の存在下で を安全に実現するとき、任意の実世界の攻撃者 に対し であるようなシミュレータ が存在し、次のような確率分布族を持つ。
semi-honest モデルのときと同様に、「理想世界の不正な参加者の入出力の情報を用いて、現実世界の攻撃者のビューを生成できる。」ときに安全といえます。大きく異なるのは、シミュレータが不正な参加者の入力を適切に選ばなければならないという部分です。
以上までが、理想世界と現実世界を用いたsemi-honest な攻撃者とmalicious な攻撃者に対するMPCのセキュリティの解説となります。
次節からは、暗号の安全性を分析するフレームワークを提供する理論である、Universal Composability（プロトコルの汎用的結合可能性） について紹介していきます。
4. Universal Composability（汎用的結合可能性）[2][3]
Universal Composability は、暗号プロトコルを記述し、そのセキュリティを分析するための一般的なフレームワークを提供する理論であり、複数のプロトコルを組み合わせた場合においても、その安全性が保たれていることを保証するという特徴があります。
一方、これまで紹介したようなセキュリティモデルの定義の下で、安全なプロトコルの合成可能性は保証されていないことが知られています。具体例をあげると、ゼロ知識証明という機能については参考論文にてこのことが示されています[4]。
Universal Composability（UC）フレームワークを用いると、セキュリティを保持した合成操作によって、複雑なプロトコルをより単純な構成要素に分解して設計・解析することができます。
UCフレームワークでは、環境とよばれる実体を追加します。そして、「ある機能が理想世界で実行されたのか、もしくは現実世界で実行されたのかが環境にとって識別不可能であること」を安全と定義します（詳細はUCエミュレートの節）。
ここでは、文献[2]に合わせて、プロトコルや攻撃者、環境を機械の集合として定義します。
機械の集合とプロトコル
UCの議論においてはプロトコルを機械の集合と捉え、各参加者は複数の機械を持つことができるとします。
また、環境や攻撃者についても機械の集合と捉えます。
それぞれの機械は以下を持ちます。
- 自身のID
- 情報を送信できる機械のIDの集合
- 実行プログラム
また、機械が送信する情報は（入力・出力・バックドア情報）の３種類です。
また、機械 が機械 のサブルーチンであるとは、 がその出力を に送信することができることをいいます。
ここで、プロトコル とは次の２つを満たす機械の集合であると定義できます。
- が機械 に入力を与える機械 を含むならば、 は を含む。
- が機械 と機械 のサブルーチンである機械 を含む場合、 は に入力を与えることができる。 が機械 を含まず、機械 のサブルーチンである機械 を含む場合、機械 を のメインマシンと呼ぶ。
また、プロトコル に対し （すなわち、 の機械の部分集合）なる がプロトコルであるとき を のサブルーチンプロトコルといいます。
UCエミュレート
次に、UCエミュレートという言葉を定義しておきます。UCエミュレートは、プロトコルが別のプロトコルを模倣することを意味します。
まず、次の確率分布を定義します。
- はビット列 を環境 の入力としたときの、攻撃者 と環境 を含めてプロトコル を実行した際の環境 の（1bit の）出力の確率分布とする。
- は や の各参加者（メインマシン）に入力を与え、出力を得ることができる。
- は の参加者や、そのサブルーチンとバックドアを介してやり取りすることができる。
- 環境 と攻撃者 は の多項式時間で動作する。
攻撃者 と環境 を含めたプロトコル の実行は次の図のようになります。
また、この確率分布からなる確率分布族 を以下のように定義します。
ここで、プロトコル がプロトコル をUCエミュレートするとは、任意の攻撃者 に対し、攻撃者 が存在し、任意の環境 について、 が成り立つことをいいます。
このUCエミュレートの定義は、環境 が出力する１ビットが「 が（ と の）どちらのプロトコルと作用したのかを判定した結果」だと捉えると、想定するどんな環境 にとっても、どちらと作用したのか判定できないということを意味しています。
UC実現
さらに、UC実現という言葉を定義します。UC実現は、プロトコルがある機能を実現することを意味します。
まず、以下のような理想的なプロトコル を定義します。
- プロトコル と同じ数の参加者を持つ
- 参加者が信頼できる理想的な参加者 に入力する
- が機能 を実行した結果を全ての参加者に返す
このとき、あるプロトコル が機能 をUC実現するとは、 が をUCエミュレートすることをいいます。
UC定理
最後に、UC定理を紹介します。UC定理は結合操作のもとでプロトコルの安全性が保たれることを保障します。
UC定理の主張は以下です。
「プロトコル がプロトコル をサブルーチンプロトコルとして持ち、プロトコル は をUCエミュレートする場合、 のサブルーチンプロトコル を に置き換えたプロトコル は をUCエミュレートする。」
これを示すためには、 が をエミュレートするが故に存在するシミュレータ を用いて、 の攻撃者 に対するシミュレータ を作ればよいです。
は環境 との通信を と同じくし、 （ から を除いたもの）との通信も と同じくします。そして、 との通信は を通して行い、 との通信はダミーの攻撃者（ からメッセージを受け取りそれを にそのまま送信する） を通して行います。
すなわち、次の図のようになります。
図では、わかりやすさのために複数の機械からなる や をひとつのボックスで表現しています。また、 は からメッセージを受け取りそれを にそのまま送信するので、 と合わせて とみなすことができます。
ここで、 からなる部分を環境 とみなすことができて、次の図のようになります。
図は、「 と を含めて を実行したときの の出力がもつ確率分布族」と、「 と（とダミーである ）を含めて を実行したときの の出力が持つ確率分布族」が等しいことを表しており、同様に、 と が等しいことを表しています。
は をUCエミュレートするので、攻撃者 に対し、シミュレータ が存在し、環境 について、 を満たします。
かつ なので、 を満たします。
以上により、UC定理を示すことができました。
UC定理により、ある機能 をUC実現するプロトコル がサブルーチンとして別の機能 を利用しているとき、 との作用を をUC実現するプロトコル に置き換えてよいです。このことにより、複雑なプロトコルの設計やその安全性の証明を簡略化することができます。
5. その他のセキュリティのバリエーション
さらに、セキュリティの定義には次のようなバリエーションがあります。
中止を伴うセキュリティ（Security with abort）
メッセージベースの2PCプロトコル（参加者数が2のMPCプロトコル）では、一方の参加者が他方の参加者より先に最終出力を知ることになります。
先に最終出力を知った参加者がmalicious で、出力のメッセージを送ることを拒否すると、もう一方の参加者は出力を知ることができなくなります。
理想世界では、ある参加者が出力を受け取るとき全ての参加者に出力が与えられることになっています。そのため、このような行動は理想世界に反します。
「ある参加者が出力を受け取るとき全ての参加者に出力が与えられる」という性質は出力の公平性（output fairness）と呼ばれ、すべてのMPCの機能がこの性質を満たしながら計算を行えるわけではないということが知られています[5][6][7]。
そこで、理想世界の機能を次のように修正します。
- malicious な参加者を特定できる。
- 全ての参加者が入力したのち計算を実行し、その出力をmalicious な参加者のみに与える。
- malicious な参加者からの「配信」または「中止」のコマンドを待つ。
- 「配信」を受け取ったら正当な参加者に出力を与える。
- 「中止」を受け取ったら正当な参加者に中止を意味する出力（）を与える。
このように理想世界を定めると、malicious な参加者が「中止」というコマンドを持つような場合のセキュリティを定義することができます。
これにより、例えば一度でも中止のコマンドが実行された場合には、そのMPCシステムを停止させることで、malicious な参加者にさらに秘密情報を取得されるリスクを軽減させることができます。
動的な不正 （Adaptive corruption）
ここまでの理想世界と現実世界の定義では、不正な参加者の集合は固定されていました。これによって、静的な（不正な参加者の集合が変化しない）攻撃に対するセキュリティを定義できていました。
しかし、攻撃者がプロトコルの実行中に得た情報を用いるなどして、プロトコル開始時には正当であった参加者を制御できてしまう可能性も考えられます。このような攻撃をadaptive corruption と呼びます。
adaptive corruption に対するセキュリティは、敵が「corrupt 」というコマンドを使用できるようにすることで、現実世界と理想世界のパラダイムによってモデル化することができます。
現実世界では、「corrupt 」を行うことで、 の現在のビューを得て、その後のプロトコルメッセージの制御を行うことができるようになります。理想世界では、シミュレータは参加者を制御したときに、制御された参加者の入力と出力からビューをシミュレートします。
adaptive corruption に対するセキュリティでは、シミュレータが断片的にビューを生成することが課題となります。 が制御されたとき、シミュレータは のビューを正当な の秘密の入力について知らずに生成します。
しかし、その後に が不正となったときに生成するビューは のビューと整合性がとれていなければなりません。（のビューはメッセージのやりとりなどで互いに相関があります。）
このように、adaptive corruption のシミュレートは複雑であり、MPCの多くの研究はadaptive corruption ではない攻撃についてのものであるため、ここでは紹介のみに留めておきます。
adaptive corruption について詳しくは[8]を参照してください。
以上がさまざまなセキュリティのバリエーションの紹介となります。
まとめ
- MPCでは理想世界と現実世界の区別がつかないことをセキュリティの定義とする。
- Semi-honest な参加者はプロトコルには従うが、その過程で得られた情報を用いて秘密情報を得ようとする攻撃者のモデルである。
- Malicious な参加者はsemi-honest の行動に加え、プロトコルから逸脱する可能性のある攻撃者のモデルである。
- UC定理が成り立てば、理想世界のプロトコルをサブルーチンとして使用するプロトコルは、その理想世界のプロトコルをUCエミュレートする現実世界のプロトコルに置き換えられる。
参考文献
[1]
David Evans, Vladimir Kolesnikov, and Mike Rosulek. 2018. "A Pragmatic Introduction to Secure Multi-Party Computation".
[2]
Ran Canetti. 2020. "Universally Composable Security: A New Paradigm for Cryptographic Protocols∗".
[3]
岡本 龍明. 2005. 「暗号理論の最近の話題について」. 2005 巻 Spring-Meeting 号 p. 83-92.
[4]
O. Goldreich and H. Krawczyk. "On the Composition of Zero-Knowledge Proof Systems".
SIAM. J. Computing, Vol. 25, No. 1, 1996.
[5]
Cleve, R. 1986. “Limits on the Security of Coin Flips when Half the Processors Are Faulty (Extended Abstract)”. In: 18th Annual ACM Symposium on Theory of Computing. ACM Press. 364–369.
[6]
Gordon, S. D., C. Hazay, J. Katz, and Y. Lindell. 2008. “Complete fairness in secure two-party computation”. In: 40th Annual ACM Symposium on Theory of Computing. Ed. by R. E. Ladner and C. Dwork. ACM Press. 413–422.
[7]
Asharov, G., A. Beimel, N. Makriyannis, and E. Omri. 2015a. “Complete Characterization of Fairness in Secure Two-Party Computation of Boolean Functions”. In: TCC 2015: 12th Theory of Cryptography Conference, Part I. Ed. by Y. Dodis and J. B. Nielsen. Vol. 9014. Lecture Notes in Computer Science. Springer, Heidelberg. 199–228. Doi: 10.1007/978-3-662-46494-6_10.
[8]
Ran Canetti. et al. 2001. "On adaptive vs. non-adaptive security of multiparty protocols" .