📝
【MPC技術入門③】Semi-honest モデルで安全な代表的プロトコル
はじめに
この記事は、セキュアマルチパーティ計算（secure multi-party computation：MPC）技術の入門に適した書籍である「A Pragmatic Introduction to Secure Multi-Party Computation [1]」を参考にした、MPC技術解説の３回目の記事となります。今後もMPC技術入門シリーズとして解説していく予定です。
今回は、semi-honest モデルで安全なMPCプロトコルのうち代表的なものを紹介し、その仕組みを簡単に説明していく内容となっています。
コンテンツの構成
本記事では、semi-honest モデルで安全なMPCプロトコルをいくつか紹介します。そのための下準備として、ランダムオラクルやOblivious Transfer と呼ばれる仕組みについて紹介します。続いて、semi-honest モデルで安全な代表的なMPCプロトコルとして、Yao's Garbled Circuit・GMWプロトコル・BGWプロトコルを紹介します。最後に乗算を効率的に行うための技術であるMultiplication Triples について説明します。
下準備
ここでは、MPCの重要な構成要素であるランダムオラクルとOblivious Transfer について説明します。
ランダムオラクル
ランダムオラクルはハッシュ関数をパブリックな理想化されたランダム関数として扱うというものです。ランダムオラクルモデルの下で、全ての参加者は公開された関数 にアクセスできます。この は入力 に対し、次のように出力します。
- 過去に が入力として与えられていない場合 をランダムに選び、ペア を記憶して、 を出力する。
- 過去に が入力として与えられている場合 とランダムな値 のペアを記憶している。これを見つけ、 を出力する。
ランダムオラクルモデルにおけるハッシュ関数 は理想的な関数であり、具体的な関数とは異なるものです。「ランダムオラクルでは安全ですが、 を具体的な関数で置き換えると必ず安全でなくなる」ような（作為的な）暗号方式が存在することが知られています[2]。
このような問題点があるものの、ランダムオラクルモデルを仮定して設計された多くのプロトコルは標準モデルで設計されたものよりも効率的であり、実用上ランダムオラクルモデルは受け入れられると考えられています[3]。
標準モデルとは「ある暗号方式が ”安全” であるとは、すべての確率的多項式時間チューリング機械に対してもその方式が破れないことと定義する」ようなモデルです[4]。
Oblivious Transfer (OT)
Oblivious Transfer(OT) は安全な計算プロトコルに不可欠な構成要素であり、一部のMPC プロトコルでは、情報を送信する際にOT を用いることがあります。
OT では送信者と受信者が存在します。そして、OTとは「送信者の持つ秘密のうち受信者が（内容を見ずに）選択したものだけを受け取り、送信者は受信者がどの秘密を受け取ったのか知ることができない」というプロトコルです。
中でも、「送信者が２つの秘密を持ち、受信者がそのうち１つを受け取る」という設定は1-out-of-2 OT と呼ばれます。1-out-of-2 OT の定義は次のようになります。
定義. 1-out-of-2 OT
1-out-of-2 OTは次のを安全に実装した暗号プロトコルである。
1-out-of-2 OT の機能
パラメータ：
２人の参加者：送信者を 、受信者を とする。 は２つの秘密 を持ち、 は選択ビット を持つ。
機能：
次を順に行う。
- は に を送り、 は に を送る。
- は を受け取り、 は終了記号 を受け取る。
また、この自然な拡張として、 個の送信された情報から１つを取得する、1-out-of- OT も定義できます。1-out-of- OTは1-out-of-2 OT から構成できることが知られています。
OT は理論的にはMPCと同等ということが知られています[5]。すなわち、OT が与えられると、追加の仮定無しでMPC を構築でき、逆にMPC で直接OT を構築することができます。
ここからは、OT の実装について説明します。
公開鍵ベースOT
まずは、semi-honest モデルの公開鍵ベースOT です。そのプロトコルは次の通りです。
公開鍵ベースOT
パラメータ：
- 二人の参加者：送信者 と受信者
の入力：秘密情報
の入力：セレクタビット
プロトコル：
- は、公開鍵と秘密鍵のペア を生成し、公開鍵空間からランダムな鍵 を取得する。もし なら、 はペア を に送信し、 なら を送信する。
- は を受け取り、 を に送信する。
- は を受け取り、秘密鍵 を用いて を復号する。 については、秘密鍵を持っていないため、復号することができない。
このプロトコルの安全性は、対応する秘密鍵を得ることなくランダムな公開鍵を取得できる公開鍵暗号の存在を前提としています。
このプロトコルはsemi-honest モデルにおいて安全です。以下、簡単に説明します。
が得る情報は から受信した２つの公開鍵のみであり、秘密鍵 を知らずにどちらの鍵が なのかを より良い確率で予測することはできません。したがって、ランダムに選んだ２つの公開鍵を送信するだけで、 のビューをシミュレートすることができます。
一方、受信者 は二つの暗号文を受信して、そのうちの１つを復号するための秘密鍵を持っています。このとき、 の入力と出力があれば、 のビューを簡単にシミュレートすることができます。シミュレータ は、公開鍵と秘密鍵のペア とランダムな公開鍵 を生成し、シミュレート下で受信する暗号文を、
(1) 公開鍵 で受信した秘密を暗号化したもの
(2) 公開鍵 で適当な数（例えば０）を暗号化したもの
と設定します。実際の実行との違いは(2) の暗号文のみであり、暗号化の安全性が保証されているため、適当な数の暗号文を他の数と区別することはできません。したがって、シミュレーションは成立します。
しかし、このプロトコルはmalicious モデルでは安全ではありません。受信者 は、２つの公開鍵と秘密鍵のペア を生成し、 を に送信することで、２つの暗号文を復号し、 の両方を知ることができます。
また、少数の公開鍵操作で多くのOT を実現する別の方法があります[7][8]。
Oblivious Transfer については、過去にもブログで扱っています。こちらも是非ご覧ください。
MPCプロトコル
ここからは、semi-honestモデルで安全である代表的なプロトコルの仕組みを解説していきます。
Yao's Garbled Circuit
Yao's Garbled Circuit は代表的なMPCプロトコルのひとつです。
その特徴としては次の通りです。
- ２者間でのプロトコル
- 通信回数が回路によらず一定
- 組み合わせ論理回路に対して秘密計算を行う
まず、基本的なアイデアを説明し、Garbled Circuit の生成方法について述べます。その後、安全性について軽く触れ、最後にプロトコルの流れを説明します。
アイデア
Yao's Garbled Circuit は２者間でのプロトコルです。そこで、一人目の参加者を 、二人目の参加者を と書きます。
関数のテーブルによる表現
が を持っており、 が を持っているとき、与えられた関数 を計算することを考えます。
関数 について、全ての入力の組 に対する結果を列挙できるとします。 は 行 列からなるテーブル で表現することができ、とすることができます。すなわち、 を構築することができれば、関数 が表現できたことになります。
テーブルの暗号化
次に、テーブルの各マスを暗号化します。
まず、すべての に対し鍵 、すべての に対し鍵 を対応させます。そして、すべてのマス を で暗号化し、 とします。
このとき、 を知っていれば、 から を復号することができます。
鍵の送信
はテーブル を暗号化したのち、 を に送信します。 は自身の秘密である を知っているので、単に を送信します。一方、 は の秘密 は知らないので、 を1-out-of- OT で送信します。
復号するマスの決定
ここまでで、 は暗号化されたテーブルと を復号する鍵 を取得しているので、あとは復号すべきマスがわかればよいです。
これには、Beaver ら[9] の「point-and-permute」と呼ばれる手法が有効です。point-and-permute では鍵にポインタを付与します。すなわち、鍵 に対応する新しい鍵を としたとき、 です。ただし、 について、 は相異なるようにします。鍵 に対応する新しい鍵 についても同様に生成します。そして、ポインタ が差す場所に を配置します。
以上のようにすることで、 は復号するべきマスの場所がわかるため、 について知ることなく を得ることができます。最後に が にマスを復号して得られた を送れば、秘密計算は完了です。
しかし、この方法では、サイズ のテーブルに対して線形に計算時間が増加するため、非効率です。そこで、組み合わせ論理回路の各ゲートの評価をここまでで紹介したアイデアを用いて行うようにします。このとき、関数を表すテーブルのサイズは４となります。
Garbled Circuit の生成
を表現する組み合わせ論理回路 について、
- の各ワイヤ に対して はワイヤ上の可能な値（）に対応する２つの鍵 とポインタ を割り当てる。これらの組 を「ワイヤラベル」と呼び、平文のワイヤの値 を「ワイヤ値」と呼ぶ。
- 実行中、計算の入力に応じて、各ワイヤはあるワイヤ値をとる。このワイヤ値をアクティブ値、ワイヤラベルをアクティブラベルと呼ぶ。
とします。
次に入力ワイヤ、出力ゲート を持つゲートについて、 は以下の暗号化されたテーブルを構築します。
例えば、 がANDゲートであれば、
となります。
テーブルの各マスには、ゲートで計算された出力に対応するアクティブラベルが暗号化されています。つまり、このテーブルを用いることで２つの入力ワイヤのアクティブラベルから出力ワイヤのアクティブラベルを得ることができます。これを繰り返し行うことで、回路 を評価することができます。
は各テーブル（Garbled tables やGarbled gates とよばれる）のエントリを順列とし、 へ送ります。さらに は、それぞれの入力値に対応するすべてのワイヤのアクティブラベルを に送ります。 が入力を行うワイヤについては、単にワイヤラベルを送信すればよく、 の入力に属するワイヤについては、1-out-of-2 OT によって送信が行われます。
は入力鍵とテーブルたちを受け取り、ワイヤの評価を進めます。前述のとおり、 は暗号化されたゲートの正しい行を復号できなければなりません。これは、前述のpoint-and-permute によって実現されます。
は回路を評価し、最終的に回路の出力ワイヤのアクティブラベルを得ます。これを に送れば、 がこれを復号することができます。なお、 が出力を復号できるように が出力の復号テーブルを送ることで、 が に出力ワイヤのアクティブラベルを送る通信を回避することができます。
安全性
ここでは、Yao's GC の安全性について簡単に説明します。
semi-honestなモデルの場合、 が不正な参加者であったとしても、そのパーティがプロトコルでメッセージを受信しないため、安全といえます。
が不正な参加者であった場合、セキュリティは、評価者 が同じワイヤの両方のラベルを決して見ないという観察に要約されます。これは、明らかに入力ワイヤに当てはまり、帰納的に全ての中間ワイヤに当てはまります（ゲートの各入力ワイヤのラベルが1つしかないため、 はゲートの暗号文を1つしか復号化できません）。 は、プレーンテキスト値とワイヤラベルの対応を認識していないため、ラベルと値の関連付けが によって明示的に提供される出力ワイヤを除いて、ワイヤのプレーンテキスト値に関する情報はありません。
シミュレータ は のビューを次のようにシミュレートします。
- 各ワイヤについてランダムなアクティブラベルを選択し、各ゲートの３つのアクティブでないワイヤラベルをダミー暗号文とする。
- 各ゲートについて、２つの入力ワイヤのアクティブラベルのポインタが出力ラベルのアクティブラベルのポインタを指すようにすればよいので、他のワイヤラベルは関係ない。
- アクティブな出力ワイヤを関数の出力に復号する復号テーブルを生成する。
- 復号テーブルで、出力ワイヤのアクティブラベルが計算結果となるようにする。
このように、シミュレータを構成できるため、プロトコルは安全といえます。
プロトコルの流れ
次にGarbled Circuit の構築手順を示し、その後プロトコルの手順を示します。
図内の は連結、 はビットごとのXOR 、 は集合からの無作為抽出を表します。また、テーブルの暗号化に用いる はランダムオラクルです。
Yao's garbled circuit におけるGarbled Circuit の生成
パラメータ：
関数 を実装する組み合わせ論理回路 、セキュリティパラメータ
Garbled Circuit の生成：
- ワイヤーラベルの生成
の各ワイヤー について、次のようにランダムにワイヤーラベルを選択する。
ただし、 を満たす。
- Garbled Circuit の構築
- を関数 を実現する２入力の論理ゲートとする。 このとき、入力ラベルは とし、出力ラベルは とする。
- のgarbled table を作成する。 の入力値 の 通りの可能な組み合わせのそれぞれについて
の各ゲート に対して、入力ラベルが決定したものから順に次を行う。
とする。
- 出力の復号テーブル
論理回路の各出力ワイヤ （ゲート の出力ワイヤである）について、そのラベルを とする。これらの出力ワイヤについて、可能なワイヤ値 の両方について出力の復号テーブルを次のように作成する。
なので、
のようにして復号することができます。
Yao's garbled circuit のプロトコル
パラメータ：
参加者 とその入力、参加者 とその入力 、関数 を実装する組み合わせ論理回路
プロトコル：
- は図１を実行し、GCを生成する。 は得られたGC を出力の復号テーブルを含めて に送信する。
- は が入力を与える全てのワイヤのアクティブラベルを に送信する。
- が入力を与える各ワイヤ について、 が送信者であり が受信者であるようなOT を実行し、次のようになる：
- はワイヤー値 に対応した２つのワイヤーラベルを与える。 はそのうち入力に対応するワイヤー値() を選択する。
- OTが完了すると はアクティブラベルを受け取る。
- は入力ワイヤのアクティブラベルから順に、 をゲートごとに評価する。
- Garbled Table と（ゲートの）入力のアクティブラベルに対し、 は次のようにして（ゲートの）出力のアクティブラベル を得ることができる：
- は出力の復号テーブルを用いて出力を取得する。
- 出力の復号テーブル と（組み合わせ論理回路の）出力のアクティブラベル （ただし の出力ワイヤである）に対し、 は次のようにして（組み合わせ論理回路の）出力のワイヤ値 を得ることができる：
最後に、 は得られた出力を に送り、両者はそれを出力とする。
Yao's Garbled Circuit については、過去にもブログで扱っています。こちらも是非ご覧ください。
GMWプロトコル
GMWプロトコルでは、秘密分散法によって分散したデータ（これをshare と呼びます）上で計算を行います。
例えば、Yao's GC では、ワイヤの値を「 がワイヤラベルを持ち、 がアクティブラベルを持つ」ことによって、秘密分散していたと捉えることができます。
GMWプロトコル[10][11]ではワイヤ値の秘密分散はより直接的で、参加者はアクティブなワイヤ値の加法的に分散した値を保持します。
GMWプロトコルはYao's GC とは異なり、３つ以上のパーティに拡張できます（Yao's GC も工夫することで３つ以上のパーティに拡張でき、それはBMRプロトコルと呼ばれます）。
GMWプロトコルは組み合わせ論理回路と算術回路のいずれでも動作します。
ここでは、２パーティの論理回路バージョンを紹介し、その後、このプロトコルが３パーティ以上に一般化できることを簡単に説明します。
それぞれについて、まず、秘密分散をどのように行うかを説明したのち、各ゲートの評価方法について説明します。
Yao's GC と同様に、 が入力 を持ち、 が入力 を持ちます。また、 と は関数 を計算する論理回路 について合意しているとします。
秘密分散
まずは、入力を秘密分散します。
は の各ビット に対し、ランダムなビット を生成し、全ての を に送信します。このとき、 についての のshare は であり、 のshare は です。 なので、確かに についてのそれぞれのshare から を復元できます。
の各ビット のshare についても同様に生成します。
ここから、各ゲートの評価を秘密分散したまま進めていきます。
各ゲートの評価
と は回路 をゲートごとに評価します。
ここで、 はNOT・XOR・AND ゲートで構成されるとしても一般性を失いません。したがって、ここではNOT・XOR・AND ゲートをそれぞれどのように評価するのかを考えます。
NOT ゲート
入力を とし、出力を とします。
また、 の持つ のshare を 、 のshare を とし、 の持つ のshare を 、 のshare を とします。
このとき、NOTゲートの評価は が をビット反転すればよいです。
すなわち、 です。
確かに となり、ワイヤ値を反転できています。
XOR ゲート
ゲートの２つの入力ワイヤを とし、出力ワイヤを とします。
また、 は のshare を持ち、 は のshare を持つとします。 の持つ のshare は 、 が持つ のshare を とします。
このとき、XORゲートの評価は各参加者が自分の持つ２つのshare のXORを取ればよいです。
すなわち、 とします。
確かに となり、 のXOR を取れています。
AND ゲート
AND ゲートはローカルな計算で実現できていたNOT やXOR とは異なり、通信をする必要があります。AND ゲートでは1-out-of-4 OT を使用します。
ゲートの２つの入力ワイヤを とし、出力ワイヤを とします。
また、 は のshare を持ち、 は のshare を持つとします。 の持つ のshare は 、 が持つ のshare を とします。
このとき、AND ゲートの評価は、次のように行われます。
- は の４つの可能な入力（ の組み合わせ）に対して の持つべき のshare を計算する。
- 1-out-of-4 OT で は４通りの のshare を送信し、 は自分の入力のshare に対応する出力のshare を受け取る。
すなわち、 として、 次のようにします。
- はランダムなマスクビット を選び、OT のテーブルを次のように用意する。
- 次に、 と は が送信者で が受信者であるような1-out-of-4 OT プロトコルを実行する。 はテーブルのそれぞれの行をOT の秘密入力とし、 は が持っているshare のビットを対応する行を選択するために使用する。
- とする。
このようにすると、 となり、確かにAND を取れています。
回路の評価が終了したら、お互いに出力ワイヤのshare を公開することで回路の出力を得ることができます。
３パーティ以上への一般化
ここでは、これを 人の参加者 が論理回路 を評価するという設定に一般化する方法を簡単に説明します。
秘密分散
2PT のときと同様に、各参加者 は各 について を選び、 を に送信することで入力を秘密分散します。
そして、参加者 は をゲートごとに評価していきます。ゲート の評価は次のように行います。
NOT, XOR ゲート
2PT のときと同様に、ローカルに出力のshare を計算します。すなわち、表記を2PT のときと同じとして、
- NOTゲート：
- XORゲート：
AND ゲート
ANDゲート を考えます。このとき、 番目の参加者のshare を とします。このとき、次が成り立ちます（AND はXOR に対して分配的です）。
したがって、次のようにして のshare を求めることができます。
- 各参加者 はローカルに を計算し、 のshare を得る。
- 全ての参加者のペア について、2PT のときと同様に、 のshare を共同で計算する。
- 最後に各参加者は得たshare のXORをとって、 のshare とする。
すなわち、 番目の参加者の のshare を 、 のshare を 、 のshare を とすると、
となり、確かに
となります。
このようにして、XORゲートとANDゲートの評価が行えます。あとは、2PT のときと同様に、回路を評価し、出力ワイヤのshare を共有することで出力を得ることができます。
BGWプロトコル
Ben-Or, Goldwasser, Wigderson によるBGWプロトコル[12]は秘密計算のための最初のマルチパーティプロトコルのひとつとして知られています。また、Chaum, Crepau, Damgard によって、BGWプロトコルとやや類似したプロトコルがBGWと同時に発表されており[13]、この２つのプロトコルは同等のものと考えられることが多いです。
ここでは、具体性を持たせるため、より単純化された 人の参加者に対するBGWプロトコルを紹介します。
BGWプロトコルを使用すると、「加算・乗算・定数倍」のゲートで構成される体 上の算術回路を評価できます。
GMWプロトコルのときと同様に、まず、秘密分散の方法について説明します。その後、各ゲートの評価方法について説明します。
秘密分散
このプロトコルは、Shamir の秘密分散[14]に基づいており、Shamir の秘密分散が特定の操作に対して準同型であることを利用しています。つまり、個々のshare を適切に操作することで、共有された元の値は秘密にしたまま操作することができます。
について、参加者達が のshare を所有しているとき、参加者のshare を と書きます。 のような演算は参加者 が持つ のshare と のshare の演算を表します。
具体的には、次のようにshare を構成します。
- 秘密情報 を持つ参加者は となるような最大 次元の多項式 をランダムに選択する。
- 各参加者 は値 をshare として持つ。
ここでは、 を共有の閾値と呼び、このとき 個のshare を集めても に関する情報が洩れることはないようになっています（多項式 は一意に定まりません）。
一方、 個のshare を集めると を復元することができます。 は の としたときの に等しいです。
ここで、 を行列を用いて書くと、
となります。ヴァンデルモンド行列式から、
が成り立つので、 が相異なるとき（かつそのときに限り）この行列は正則です。したがって、逆行列を持ち、 は一意に定まります。
また、多項式 はラグランジュ補間と呼ばれる方法で求めることができます。ラグランジュ補間によると、 は次の式で表せます。
ラグランジュ補間について
について、
について、
が成り立つことに注意すれば、
となることがわかります。
したがって、 が成り立ちます。
以上より、 個のshare を集めることで、秘密情報が復元できることがわかりました。
このように秘密分散すると、加算・乗算・定数倍について、次のようにして入力のshare から出力のshare を計算することができます。
入力
参加者 が入力を与える入力ワイヤ に対し、 はワイヤ 上の値 を明確に知っています。
秘密分散の節で述べたように、
- は となるような最大 次元の多項式 をランダムに選択する。
- は各参加者 に を送信する。
- 各参加者 は を のshare とする。
として、 のshare を得ます。
定数倍
入力ワイヤ で出力ワイヤが であるような定数 倍ゲートを考えます。参加者はshare を保有しており、ここで のshare を求めることが目的です。
入力のshare が多項式 に基づいて与えられているとします。このとき、 のshare は です。
それぞれの参加者 のshare を とすると、結果的に各参加者は 上の点を保持していることになります。
このとき、 の最大次数はであり、 なので、 は確かに のshare となっています。
したがって、 です。
はローカルな計算で求められるので、定数倍ゲートでは参加者間の通信は必要ありません。
加算
加算は定数倍と同様に行えます。
入力ワイヤが で出力ワイヤが であるような加算ゲートを考えます。参加者は のshare をいずれも保有しており、ここで のshare を求めることが目的です。
入力のshare がそれぞれ多項式 に基づいて与えられているとします。このとき、 の のshare は、 のshare は です。
それぞれの参加者 が のshare を とすると、結果的に各参加者は 上の点を保持していることになります。
このとき、 の最大次数は であり、 なので、 は確かに のshare となっています。
したがって、 です。
はローカルな計算で求められるので、加算ゲートでは参加者間の通信は必要ありません。
乗算
入力ワイヤ で出力ワイヤ であるような乗算ゲートを考えます。参加者は の両方のshare を持ち、積 のshare を生成することが目的です。
足し算のときと同様に、参加者は のshare と のshare をローカルに乗算することで、各参加者は多項式 上の点を保持することができます。しかし、このとき の次数は最大 となり、次数 以下に削減する必要があります（次数が となることを許容すると、乗算を行うたびに次数が２倍になっていき、大変なことになります）。
この秘密分散の過剰な次数を修正するために、参加者は次数削減を行います。各参加者 は値 を保持しており、 は最大 の次数を持つ多項式です。このとき、目標は の秘密分散を閾値 で得ることです。
主な観察点は が 個のshare の線形関数として書けることです。すなわち、ラグランジュ補間を考えると、
です。したがって、次数削減は次のように行われます。
- 各参加者 は の閾値 のshare を生成し、配布する。このとき、 は を満たす多項式 に基づいてshare を生成する。
- 参加者は をローカルに計算する。この式は、share に対する加算と定数倍を考えると成り立つことがわかる（詳しくはcallout ）。
が成り立つことについて
は 次の多項式であり、 なので、
とすれば、 は 次の多項式であり、
となります。したがって、 のshare を求める問題は、多項式 に基づいたshare を求める問題に帰着されます。
は定数なので、各 のshare があるとき、定数倍と加算によって のshare は、
と計算することができます。
したがって、
は確かに成り立ちます。
値 が閾値 で共有されたので、最終的に共有される も閾値 を持つことになります。
BGWプロトコルの のshare を送信するという部分で通信が必要です。
また、次数 のときに を求めるためには である必要があります。
このことから、BGWプロトコルは のとき、 人の不正な参加者を許容します。
出力
ある出力ワイヤ に対し、 はshare を持つことになります。各参加者がこの値を他の全ての参加者に送信することで、全ての参加者が を知ることができます。
BGWプロトコルについては、過去にもブログで扱っています。こちらも是非ご覧ください。
Multiplication Triples
Multiplication Triples は前処理段階で用意しておいた３つの値を使用することで、効率的に乗算を行えるようにするという技術です。
Multiplication triple はshare の３つ組で、 と は適切な体からランダムに選ばれ、 となります。
前処理段階では、このようなMultiplication triple はランダムな入力に対してBGW乗算サブプロトコルを実行するなど、様々な方法で生成できます[15]。
計算を実行する際には、乗算ゲートごとにひとつのMultiplication triple が消費されます。
ここからは、Multiplication triple を用いて、具体的にどのように乗算を行うかについて説明します。
入力ワイヤ を持つ乗算ゲートを考えます。参加者はshare を持っているとします。また、share、定数 が与えられたとき、ローカルに が計算できるとします。
ここで、Multiplication triple のshare を用いて、次のように と の乗算を行います。
- ローカルに を計算し、 を公開する（全ての参加者が を公開すればよい）。この値は秘密の値 に依存するが、ランダム値 によってマスクされているため、 に関する情報は洩れない。
- 1 と同様に、ローカルに を計算し、 を公開する。
- ここで、次の式が成り立つ。
と は公開されており、参加者は のshare をそれぞれ保持しているため、ローカルな計算のみで、 を次のように計算することができる。
この技術を用いることで、２回の公開操作とローカルな計算のみで乗算を行うことができます。
Multiplication Triples については、過去にもブログで扱っています。こちらも是非ご覧ください。
まとめ
- Semi-honest モデルで安全なプロトコルとして代表的なものに、Yao's Garbled Circuit ・GMWプロトコル・BGWプロトコルがある。
- 乗算を高速化する手法として、Multiplication Triples がある。
参考文献
[1]
David Evans, Vladimir Kolesnikov, and Mike Rosulek. 2018. "A Pragmatic Introduction to Secure Multi-Party Computation".
[2]
Canetti, R., O. Goldreich, and S. Halevi. 1998. “The Random Oracle Methodology, Revisited (Preliminary Version)”. In: 30th Annual ACM Symposium on Theory of Computing. ACM Press. 209–218.
[3]
Mihir Bellare and Phillip Rogaway. 1993. "Random oracles are practical: a paradigm for designing efficient protocols". CCS '93: Proceedings of the 1st ACM conference on Computer and communications security. 62-73.
[4]
岡本 龍明. 2014. 「フォーラム 応用数理の遊歩道(76)暗号における数理モデル」.
[5]
Kilian, J. 1988. “Founding Cryptography on Oblivious Transfer”. In: 20th Annual ACM Symposium on Theory of Computing. ACM Press. 20–31.
[7]
Beaver, D. 1996. “Correlated Pseudorandomness and the Complexity of Private Computations”. In: 28th Annual ACM Symposium on Theory of Computing. ACM Press. 479–488.
[8]
Ishai, Y., J. Kilian, K. Nissim, and E. Petrank. 2003. “Extending Oblivious Transfers Efficiently”. In: Advances in Cryptology – CRYPTO 2003. Ed. by D. Boneh. Vol. 2729. Lecture Notes in Computer Science. Springer, Heidelberg. 145–161.
[9]
Beaver, D., S. Micali, and P. Rogaway. 1990. “The Round Complexity of Secure Protocols (Extended Abstract)”. In: 22nd Annual ACM Symposium on Theory of Computing. ACM Press. 503–513.
[10]
Goldreich, O., S. Micali, and A. Wigderson. 1987. “How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority”. In: 19th Annual ACM Symposium on Theory of Computing. Ed. by A. Aho. ACM Press. 218–229.
[11]
Goldreich, O. 2004. Foundations of Cryptography: Volume 2. Cambridge University Press.
[12]
Ben-Or, M., S. Goldwasser, and A. Wigderson. 1988. “Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract)”. In: 20th Annual ACM Symposium on Theory of Computing. ACM Press. 1–10.
[13]
Chaum, D., C. Crépeau, and I. Damgård. 1988. “Multiparty Unconditionally Secure Protocols (Extended Abstract)”. In: 20th Annual ACM Symposium on Theory of Computing. ACM Press. 11–19.
[14]
Shamir, A. 1979. “How to share a secret”. Communications of the ACM. 22(11): 612–613.
[15]
大原一真. 2019. 「秘密分散法を用いた秘密計算」.