秘匿マルチパーティ計算

秘匿マルチパーティ計算（ひとくマルチパーティけいさん、英:Secure multi-party computation）とは、多人数の参加者で行う秘匿計算プロトコルの総称であり、複数の参加者がそれぞれ自身の入力値を秘匿したままで多入力関数の値のみを計算することが可能となる暗号学的な手法をいう[1]。単にマルチパーティ計算(MPC)や秘密計算、プライバシー保護計算とも通称される。従来の暗号化手法[注釈 1]とは異なり、このモデルの暗号化は参加者のプライバシーを相互に保護する。

秘匿マルチパーティ計算の基礎は、信頼できる第三者機関(TTP)を必要とせずに遠距離でゲームプレイやコンピュータ演算の業務を模擬試験するメンタルポーカー (mental poker) という暗号作業の研究で1970年代後半に始まった。従来の暗号化とは文章内容の隠蔽に関するものだったが、この新種の計算およびプロトコルは、様々な情報源からのデータで計算しながらもデータに関する部分的な（プライバシー関連の）情報を秘匿して、正確に計算結果を生み出す手法である。

1980年代後半までに、シャフィ・ゴールドワッサーやアヴィ・ヴィグダーソンなどが「セキュア[注釈 2]なチャネル設定で任意の関数を秘匿計算する方法」を提示する論文を発表した[2]。

歴史

特定タスク向けの特殊な目的のプロトコルは、1970年代後半に開発が始まった[3]。その後1982年に、秘匿計算が二者間秘匿計算(2PC)として正式にブール叙述の問題で導入され、1986年には実用的なコンピュータ演算向けの一般化がアンドリュー・ヤオによって導入された[4][5]。この分野は秘匿関数評価(Secure Function Evaluation,SFE)とも呼ばれる。2者間の場合に続いてゴールドライヒ、ミカーリ、ヴィグダーソン[注釈 3]により多数参加者（マルチパーティ）の場合への一般化が行われた。この演算処理は、あらゆる入力の秘密分散と潜在的に悪意あるケースへのゼロ知識証明に基づいており、そこでは大多数の正直な参加者に悪意ある攻撃者が混じっている場合に不正な振る舞いが検知され、不正な人物が排除されたり不正人物による入力が判明しながらも演算は継続する。この仕組みは、秘匿計算にとって本質的に全てのマルチパーティプロトコルが従うべき非常に基本的かつ一般的な手法を示唆するものだった[6]。この研究成果によりGMWパラダイム[7]と通称されるアプローチが導入され、これはsemi-honestことパッシブな攻撃者[注釈 4]に対して秘匿マルチパーティ計算プロトコルを、maliciousことアクティブな攻撃者に対してセキュアな単一プロトコルをコンパイルするのが目的である。

この研究成果に続くのが初となる堅牢な秘匿プロトコルで、これは作業を通じて誰かの出力を明かしたりせず誤った行動を寛大に許容する。この目的のために、しばしば使われる「シェア[注釈 5]の分散という構想」[11]と、参加者の1人がその入力を無条件に隠すことを許すプロトコルが発明された[12]。GMWパラダイムは、その基幹プロトコルを運用する莫大な処理時間のため非効率的だと長年考えられていた。しかし、効率的なプロトコルを実現できることが示され、そのことが実用的な観点からこの一連の研究への関心をより高めている[13]。上の成果は攻撃者が多項式時間のコンピュータ計算に限定された場合のモデルで、あらゆる通信を監視するため、このモデルが「コンピュータ計算モデル(computational model)」と呼ばれている。さらに、これらタスクに対して紛失通信プロトコルが要件を完全に満たすことが示された[14]。上の結果から、過半数の利用者が正直な（プロトコルの指示に忠実で、不正行為を全くしない）場合、秘匿計算が上述のバリエーション下で実現できることが確証された。

次に解決すべき問題は、秘匿通信チャネルで攻撃者にはポイント・ツー・ポイント通信が利用できない場合である。この場合に、参加者の最大1/3が不正行為者かつmaliciousという状況で解決できることが示されており、その解決策とは暗号化ツールを一切適用しない事である（秘匿通信が利用可能なので）[15][16]。ブロードキャストチャネルの追加は、システムに最大1/2までの少数派不正行為者を許容する[17]。とはいえ、通信グラフ上の接続制限が『Perfectly Secure Message Transmission』という書籍で調査された[18]。

歳月を経て、汎用マルチパーティプロトコルの概念は基本的かつ一般的なプロトコルの課題（プロアクティブ秘密分散に見られるような汎用的結合可能性 (Universal Composability) やモバイル攻撃者など）を調査するための潤沢な分野となった[19]。

2000年代後半以降は、汎用プロトコルの分野が実用的アプリケーションを念頭にプロトコルの効率向上に取り組むものへと移行している。MPCにとって効率性の高まるプロトコルが提案されており、今やMPCは民間入札やオークション、署名の分散や復号関数、個人情報検索といった様々な現実的問題に対する実用的解決策だと考えられている[20]。2008年1月に、MPCで初となる大規模かつ実用的なアプリケーションがデンマークで運用された（実際のオークション問題で実演）[21]。当然であるが、理論的概念と調査の両方そして適用される構造が必要である（例えば、MPCを日々の業務の一環に移行するための条件が提唱された）[22]。

2020年、秘匿マルチパーティ計算に取り組んでいる多くの企業が「MPC技術の認識、受け入れ、採用を加速する」ことを目的とするMPCアライアンスを設立した。

定義と概要

MPCにおいて、所定の参加者数p1, p2, ..., pN各々が有する個人データ[注釈 6]をそれぞれd1, d2, ..., dNとする。参加者達は、自分の入力を秘匿したままその個人データで公開関数の値F(d1, d2, ..., dN)を計算したいとする。

例えば、青山、石井、宇野の参加者3名にそれぞれの給与を示す入力 x, y, zがあると想定しよう。彼らは、自分達が各々どのくらい稼ぐのかを互いに明かすことなく、3者のうち最も高い給料を見つけたいとする。数学的にこれは次の計算式に変換される。

F(x, y, z) = max(x, y, z)

信頼できる外部関係者（例えば、秘密を口外しない事で知られる共通の友人トニー）がいれば、彼らはトニーに自分達の給与額を伝えることが可能で、彼が最大値を計算してその数値を彼ら全員に伝えることができる。MPCの目的は、青山と石井と宇野が友人トニーに頼ることなく、つまり誰がいくら稼いでいるかを明 かさずにF(x, y, z)が分かるようなプロトコルを設計することにある。彼らは、不正をしない完全に信頼できるトニーとのやりとりから分かる以上の事を、同プロトコルに携わって知るべきではない。

ここで参加者達が知りうる全ての事は、その出力と自身の入力から知りうる事である。したがって上の例だと、出力がzなら宇野は自分のzが最大値であることを知り、青山と石井は（仮にx, y, zの数値が異なるとすれば）自分の入力が最大値ではなく、誰の給料なのか秘密保持された最大値がzであることを知る。基本的なシナリオとして、参加者達が異なる入力値を持っていて関数が参加者ごとに異なる値を出力する場合に、一般化させることが容易である。

非公式ではあるが、MPCプロトコルが保証する目的となる最も基本的なプロパティは次のとおり。

  • 個人データ入力：参加者の保持する個人データに関する情報は、プロトコル実行中に送信されたメッセージから一切推測できない。個人データに関して推測可能な唯一の情報は、関数の出力だけを見て推測できるものとなる。
  • 正当性：情報を共有したり指示からの逸脱をも厭わない攻撃者のいかなる共謀集団も、プロトコルの実行中に偽りの結果を正直な参加者に出力させることはできない。これには2つの特徴がある。正直な参加者には正しい出力を算出することが保証されており（堅牢なプロトコル）、エラーが見つかった場合は処理中断する（中断ありのMPCプロトコル）。

コイン投げなどの単純タスクから、電子オークションや電子投票やプライバシー保護しつつのデータマイニングといった複雑なものまで、多彩な実用的アプリケーションが存在する。古典的な例として、2人の億万長者が双方とも相手の資産額を知らずに済む方法でどちらがより金持ちなのかを知りたがる、ヤオの億万長者問題 (Yao's Millionaires' problem) がある。この状況に対する解決策は、本質的に比較関数で秘匿的に評価することである。

セキュリティの定義

MPCプロトコルが有効であるにはセキュア[注釈 2]でなくてはならない。現代の暗号学において、プロトコルのセキュリティは安全性証明に関連している。安全性証明とは、プロトコルのセキュリティがその基礎となるプリミティブ型セキュリティの安全性に帰着する数学的証拠を指す。とはいえ、参加者の知識とプロトコルの正確性に基づいて暗号化プロトコル (Cryptographic protocol) の安全性検証を常に公式化できるわけではない。MPCプロトコルの場合、プロトコルの動作する環境には現実世界/理想世界のパラダイムが付きものである[24]。参加者は出力の操作を学ぶ必要があり、出力は入力に依存するため、彼等が何も知りえないとは言えない。しかも、出力の正確性は参加者の入力しだいであって、入力が正しいとの前提が必要な出力の正確性は保証されない（入力を間違えれば計算結果の出力も正確ではなくなる）。

現実世界/理想世界のパラダイムは2つの世界を論じている[8][25]。(i) 理想世界モデルでは、各プロトコル参加者がその入力を送信する、絶対的に信頼できる参加者 T {\displaystyle T} が存在する。この信頼された T {\displaystyle T} が（参加者達から受け取った入力データを使って）自ら関数を計算し、適切な出力を各参加者に送信する。(ii) 対照的に現実世界モデルでは絶対に信頼できる T {\displaystyle T} がおらず、参加者達はプロトコルを用いて相互に通信することにより T {\displaystyle T} の機能を実現することを目指す。現実世界における各参加者の個人データ入力に関して、このプロトコルのために（攻撃者が）理想世界で知りうる以上のことを知りえない場合に、セキュアだとされる。理想世界では参加者間でのメッセージ交換（メールやSNS等の通信やりとり）が一切ないため、現実世界のように交換したメッセージから秘密情報が暴かれることはない。

現実世界/理想世界パラダイムはMPCの複雑さを単純に抽象化し、MPCの中核プロトコルは実際のところ理想的実行に見せかけたアプリケーションの構築を可能にしている。理想的な場合にアプリケーションがセキュアであれば、実際のプロトコルが代わりに実行される場合でもセキュアである。MPCプロトコルのセキュリティ要件は厳重である。とはいえ1987年には、アクティブ(malicious)な攻撃者に対するセキュリティ[6]と前述した初期の仕組みを用いて、任意の関数を秘匿して計算できることが実証された。これらの公開にもかかわらず、当時のMPCは実際に使用されるほど効率的に設計されていなかった。無条件または情報理論上の秘匿MPCは秘密分散の問題（より具体的には検証可能秘密分散法）と密接な関連があり、秘密分散法に基づいて構築されており、多くの秘匿MPCプロトコルがこれをアクティブな攻撃者に対して使っている。

暗号や署名といった従来の暗号化アプリケーションとは異なり、MPCプロトコルの攻撃者はシステムに参加している利用者の 1人だと想定する必要がある。不正な参加者個人や集団は、プロトコルのセキュリティを侵害するために結託する場合がある。 n {\displaystyle n} をプロトコルの参加者数、 t {\displaystyle t} を攻撃者になりうる参加者の数としよう。 t < n / 2 {\displaystyle t<n/2} つまり過半数が正直だと想定される場合のプロトコルおよび解決策 は、そのような想定ではない場合とは異なる。後者の場合、参加者の1人が不正な可能性がある二者計算(two-party computation)の重要なケースと、無制限の参加者達が不正となり正直な参加者を攻撃するため結託する一般的なケースがある。

異なるプロトコルに直面させられる攻撃者達は、彼らがどの程度プロトコルからの逸脱を試みるかに応じて分類できる。基本的に2種類の攻撃者がおり[注釈 4]、それぞれには異なる形のセキュリティが立ち上がる。

  • パッシブ(Semi-Honest)対処セキュリティ:この場合、不正参加者は単にプロトコルから情報を収集するために協力するが、プロトコルの仕様から逸脱しないことが前提となる。これはお人好しな敵モデルで、実際の状況では弱いセキュリティが敷かれる。しかし、このレベルのセキュリティを実現するプロトコルは、参加者間の不注意な情報漏洩を防いでおり、かつこれが唯一の懸念事項である場合に有益である。さらに、Semi-Honestモデルのプロトコルは非常に効率的で、多くの場合さらに高レベルのセキュリティを達成するための重要な第一歩である。
  • アクティブ(Malicious)対処セキュリティ:この場合、攻撃者はチート操作を試みてプロトコルの実行から故意に逸脱する可能性がある。このモデルでのセキュリティを実現するプロトコルは、彼らにパッシブ攻撃者と同等の事しか出来ないよう強制する（それでも従わなければプロトコルから排除、攻撃者の秘密を開示してプロトコルを続行）のが大方針で[26]、非常に高い警備保障を提供する。不正な振る舞いをする参加者が過半数の場合：非正直が過半数の場合に攻撃者が出来る唯一のことは、正直な参加者にチート操作を検知させて「処理中断」させることである。もし正直な参加者が出力を得る場合、それが正確であることは保証されており、彼らのプライバシーは常に保護されている。

アクティブな攻撃者に対するセキュリティは通常、コバートセキュリティ[注釈 7]につながる有効性の低下をもたらす[28]。コバートセキュリティはより現実的な状況を捕捉しており、そこでは捕まらない場合にのみアクティブな攻撃者がチート操作に励んでいる。例えば、彼らの評判が落ちると、他の正直な参加者との将来的な協力が妨害される可能性があったとする。すると、コバートで秘匿なプロトコルは、一部の参加者が指示に従わなかった場合に75%や90%の高確率で通知される事を保証するメカニズムを提供する。ある意味、コバートな攻撃者は外部の暗号以外の懸念材料（ビジネス等）のためパッシブ行動せざるをえなくなったアクティブ攻撃者である。このメカニズムは、実際に有効で十分にセキュアなプロトコルが見つかることを期待して、両モデル間の橋渡しを設定している。

多くの暗号化プロトコルと同様、MPCプロトコルのセキュリティは以下の前提に依存している。

  • それは計算を含んで（つまり因数分解のような幾つかの数学的問題に基づいて）いる場合があり、通信チャネル上でメッセージが物理的に活用できないことに依存している。
  • このモデルは、参加者が「ある瞬間」に送信したメッセージが常に次の「瞬間」に到着する同期ネットワークを使うか、セキュアで信頼性の高いブロードキャストチャネルが存在する、または攻撃者がチャネル内のメッセージを読み取ったり、変更したり、生成できない参加者のあらゆる二者間に秘匿通信チャネルが存在する、ことを前提としている。

計算タスクを実行しうる正直な参加者群は、アクセス構造の概念と関わりがある。攻撃者構造はstatic[29]になることがあり、この場合に攻撃者はMPCの開始前に被害者を選択している。またadaptive[29]にもなることがあり、この場合はMPCの実行中に被害者を選択して（不正者として）操るので防御が困難になる。攻撃者構造は、閾値構造またはより複雑な構造として定義できる。閾値構造では、攻撃者は最大で幾つかの閾値まで参加者数のメモリを破損ないし読み取ることができる。一方、複雑な構造では起こりうる様々な共謀をモデル化しており、攻撃者は参加者の特定の部分集合に悪影響を与える。

プロトコル

二者間計算(2PC) 用とマルチパーティ計算 (MPC)用に提案されたプロトコルには大きな違いがある。また多くの場合、特殊な目的に特化した重要なプロトコルでは、一般的なものから外れたプロトコルを設計する必要がある（投票、オークション、支払い等）。

二者間計算

詳細は「:en:Secure two-party computation」を参照

参加者2名の設定は、マルチパーティの場合には適用されない二者設定に特化した手法を適用できるため、特に関心が高い。実際、秘匿マルチパーティ計算は最初に2者間設定で提示された。最初の研究としてヤオの論文がしばしば挙げられるが[30]、その論文に今でいうヤオのGarbled Circuitプロトコルと通称されるものは実際のところ含まれていない。

ヤオの 基本プロトコルはパッシブ(Semi-Honest)な攻撃者に対してセキュアであり、ラウンド数（これは不変で、評価を行う標的関数と独立している）の観点から非常に有効である。その関数は、固定長バイナリへの入力があるブール回路だと見なされる。ブール回路は、3種類のワイヤ（回路入力ワイヤ、回路出力ワイヤ、中間ワイヤ）を接続した論理ゲートの集まりである。各ゲートが2本の入力ワイヤを受信し、ファンアウト（すなわち次の段階で複数のゲートに渡される）の可能性がある単一の出力ワイヤを有する。この回路の簡易評価は、各ゲートを順番に評価することで行われる。ゲートが位相的に順列されていると仮定する。ゲートは、ビット同士（入力ワイヤのゲートから来るもの）で起こりえる組み合わせそれぞれに表が一意の出力ビットを割り当てるような真理値表として表される。これがゲートの出力ワイヤの値である。評価結果は、回路出力ワイヤで得られたビットである。

ヤオは、送信側と受信側の参加者2名が回路の出力だけを知れるように回路をgarble[注釈 8]処理させる方法を説明した。

より詳細には、garbled circuitは次のように計算される。主な構成は二重鍵の対称暗号方式である。回路のゲートが与えられると、入力ワイヤのとりうる各値(0か1)は乱数で符号化される。入力ビットの採りうる4組の各ゲートの評価から得られた結果の値も、乱数文字列（ラベル）に置き換えられる[33]。ゲートのgarble処理した真理値表は、入力ラベルを鍵として用いる各出力ラベルの暗号で構成されている。真理値表の中にあるこれら暗号4つの位置は乱数化されるため、ゲートの情報は漏洩しない。

garble処理済み の各ゲートを正しく評価するにあたって、暗号化手法には次の2つのプロパティ (プログラミング)がある。第一に、任意の2つの公開鍵の土台となる暗号化関数の範囲は（圧倒的な高確率で）素集合である。2番目のプロパティは、与えられた暗号文が特定の鍵で暗号化されているかどうかを効率的に確認できるものだと言う。これら2つのプロパティを用いて受信側はあらゆる回路入力配線のラベルを取得した後、最初に4 つの暗号文のどれが自分のラベル鍵で暗号化されたのかを見つけ、次に復号して出力配線のラベルを取得することにより各ゲートを評価可能になる。評価中に受信者が知るのはビットのエンコード形式なので、これは気付かれずに実行される。

送信側（回路作成者）の入力ビットは、評価者にエンコード形式としてただ単に送信可能である。一方、彼の入力ビットに対応する受信側（すなわち回路評価者）のエンコード形式は、1-out-of-2OTの紛失通信プロトコルを介して取得される。このOTプロトコルは「送信者が送信した2つの情報のうち、どちらを受信者が受け取ったのかを送信者が知ることができず、受信者はどちらか片方の情報しか知ることができない」という性質の通信方法である[34]。

仮にアクティブ(malicious)な攻撃者を考慮するなら、参加者双方の正しい行動を保証するため追加のメカニズムを構築する必要がある。仮にOTプロトコルがアクティブな攻撃者に対して既にセキュアであるなら、指示から逸脱した場合に受信者がやれることは回路出力ワイヤに到達できないgarbled circuitを評価することだけなので、送信者にセキュリティを示すのは簡単である。その状況は送信者側で大きく異なる。例えば、受信者の入力を明らかにする関数を計算する不適当なgarbled circuitを送信する場合もある。これはプライバシーがもはや保たれないことを意味するが、回路がgarble処理済みなので受信者はこれを検知しえない。ところで、ゼロ知識証明を有効に適用するなら、パッシブ(semi-honest)用プロトコルと比較して小さな処理時間でこのプロトコルをアクティブ(malicious)な攻撃者に対してセキュアにすることが可能である[13]。

マルチパーティプロトコル

大半のMPCプロトコルは、2PCプロトコルとは対照的に、特に私的チャネルの無条件設定下で秘密分散を利用する。秘密分散を根幹とする手法において、参加者達は特別な（ヤオでの創作者と評価者といった）役割を果たさない。代わりに、各ワイヤと関連付けられたデータが参加者間で分散され、各ゲートを評価するのに単一のプロトコルが使用される。この関数は、ヤオで使用される二進回路とは対照的に、有限体上の「回路」として定義されている。こうした回路は文献で算術回路(arithmetic circuit)と呼ばれ[35]、それは操作された値が有限体上に定義される加算と乗算の「ゲート」で構成されている。

秘密分散は、各参加者にシェアを配布することにより、多数の参加者間で1つの秘密配布を可能にしている。一般的にはシャミア秘密分散と加法的秘密分散という2種類の秘密分散法が用いられる。どちらの場合も分散は有限体の乱数要素で、合計するとその体における秘密となる。直感的には、何ら適用要件を満たさない一連のシェアが無作為に配られているように見えるため、セキュリティが実現される。

秘密分散法は合計 n {\displaystyle n} 人の参加者のうち最大 t {\displaystyle t} 人の参加者を統率する攻撃者1人を許容することができ、この場合tはその手法に基づいて変化し、攻撃者はパッシブでもアクティブでも可能で、攻撃者の能力について様々な想定がなされる。シャミア秘密分散法は、パッシブな攻撃者が t < n 2 {\displaystyle t<{\frac {n}{2}}} の場合、そしてアクティブな攻撃者が t < n 3 {\displaystyle t<{\frac {n}{3}}} の場合に対してセキュアでありつつ、情報理論的安全性（仮に攻撃者が無制限の計算能力を持っていたとしても分散の土台となる秘密に関する情報を何ら知りえないことを意味する）をも満たす[36]。

秘密分散において加算と乗算の演算方法を定義するBGWプロトコルが[32][37]、シャミア秘密分散での関数を計算するのにしばしば使用される。加法的秘密分散法は、無制限の計算能力を持つパッシブおよびアクティブな攻撃者に対するセキュリティを維持しつつ、 t < n {\displaystyle t<n} な場合を除く全ての参加者を統率する攻撃者を許容する。一部のプロトコルでは設定段階が必要で、これは計算的に有限の（計算力を持つ）攻撃者に対してのみセキュアな場合がある。

多くのシステムが、秘密分散法を備えたMPCの様々な形を実装している。最も普及しているのが SPDZで[38]、これは加法的秘密分散法のMPCを実装しており、アクティブな攻撃者に対してセキュアである。

その他のプロトコル

2014年に「出力の受信を処理中断(abort)させた攻撃者には事前に相互定義された罰金の支払いを余儀なくさせる秘匿計算の公平性モデル」が、ビットコインネットワークや公正な宝くじ向けに記述された[39]。

実用的なMPCシステム

近年では、2PCおよびMPCのシステムで多くの進展がある。

ヤオに基づくプロトコル

ヤオに基づくプロトコルで作業する際の主な問題の1つは、安全に評価される関数を通常XORゲートとANDゲートで構成する回路として表現する必要がある事である。現実世界のプログラムの大半にはループと複雑なデータ構造が含まれるため、これは非常に重要な作業である。Fairplayシステム[40]が、この問題に取り組むべく設計された最初のツールだった。Fairplayは2つの主要コンポーネントで構成されている。最初のものは、利用者が単純な高水準言語でプログラムを作成し、これらプログラムをブール回路表現で出力可能にするコンパイラである。2番目のコンポーネントは、その後に回路をgarble[注釈 8]処理してプロトコルを実行し、garbled circuitを確実に評価できるようにする。ヤオのプロトコルに基づく二者計算と同じく、Fairplayはマルチパーティプロトコルの実行も可能である。これはBMRプロトコル[40]を用いて行われ、これはヤオのパッシブ向け秘匿プロトコルをアクティブな場合に拡張したものである。

Fairplay導入後の数年で、ヤオの基本プロトコルに対する多くの改善が、アクティブセキュリティのために効率向上と技術面の双方で作成された。これにはXORゲートの評価をかなり単純化できるフリー XOR法や、garble処理した表の大きさを25%削減する garble処理行の削減などが含まれる[41]。

アクティブセキュリティを得る上でこれまで最も有益と思われるアプローチは、garble処理技術と「切り分け選択 (cut-and-choose)[42]の組み合わせから来ている。この組み合わせがより効率的な構造を構築すると考えられている。不正な動作に関して前述の問題を回避するために、同じ回路の様々なgarble処理がコンストラクタから評価者に送られる。次に（運用プロトコル次第だが）それの約半分が一貫性をチェックするために開かれ、もしそうなら未開封のものの大部分は高確率で正しい。出力はあらゆる評価の多数票である（ここで過半数の出力が必要とされることに注意）。出力に不一致がある場合、受信者は送信者が不正操作をしていることを知っているが、そうしないと自分の入力情報が漏洩するため不満は言えない。

このアクティブセキュリティ用のアプローチは、リンデルとピンカスによって開始され[43]、2009年に同技術がピンカスらによって実装された[41]。これにより、非常に複雑（約3万のANDゲートとXORゲートからなる）かつ非自明な関数だと見なされるAdvanced Encryption Standard(AES)回路の最初のアクティブな秘匿二者評価が可能となった。当時はそのコンピュータ計算に約20分かかり、不正行為確率 2 − 40 {\displaystyle 2^{-40}} を得るには160回路が必要だった。

多数の回路が評価されるため、参加者達（受信者を含む）は全てのイテレーションで同じ値が使用されるよう自分の入力をコミット（変更を永続的に確定）する必要がある。ピンカスらの実験では[41]、プロトコルのボトルネックが一貫性チェックの中に存在することが判明した。そのチェックは、AES回路を評価するために約6,553,600のコミットを様々な値でインターネット越しに送信する必要があった。近年の成果では[44]、ヤオに基づくアクティブ対応の秘匿実装プログラムの効率性はさらに向上し、しかも不正行為の確率 2 − 40 {\displaystyle 2^{-40}} を得るのに必要なのは40回路だけで、コミットは大幅に少なくなった。この改善は、送信された回路で切り分け選択を実施するための新しい方法論から生じた。

最近では、メニーコアのCPU上で実行するように設計されたgarbled circuitsに基づく高度な並列処理を行うプロトコル実装が注目されている。クロイターらは[45]、強力なコンピュータ・クラスターの512コアで実行される実装プロトコルについて説明している。これらのリソースを使うと、回路が約60億ゲートからなる4095ビットの編集距離関数を評価できる。これを実現するにあたり、彼らはFairplay以上に最適化された回路コンパイラとパイプライン処理など幾つかの新しい最適化カスタムを開発した。AESの計算時間は、512ノードのクラスター機器を使って、アクティブな場合だと1.4秒/ブロックに短縮、1ノードを使うと115秒になった。シェラトおよびシェンはこれを改良し[46]、汎用ハードウェアを使って0.52秒/ブロックを達成した。

一方、別の研究者グループは一般消費者向けGPUを使用して似たレベルの並列処理を成し遂げる研究をしている[47]。彼らはOT拡張子ほか幾つかの新技術を活用してGPU固有のプロトコルを設計する。このアプローチは、似た数のコアを使用してクラスタコンピュータの実装プログラムと同等の効率を達成すると考えられている（ただし、著者らは約5万ゲートを有するAES回路の実装のみを報告）。ここで必要なハードウェアは、沢山の人のデスクトップコンピュータやゲーム機で同様のデバイスが既に見られるため、入手しやすいものである。著者らは、標準的GPUを備えた標準的なデスクトップ上で2.7秒/AESブロックの時間が出たとしている。仮にセキュリティをコバートセキュリティと似たものに削減できるなら、0.30秒/AESブロックの実行時間だという。パッシブセキュリティの場合、2.5億ゲートを有する回路を7500万ゲート/秒の速度で処理したのとの報告が存在する[48]。

関連項目

脚注

注釈

  1. ^ 暗号化によって通信やストレージの秘匿性と整合性が保証され、参加者のシステム外部に攻撃者（送受信を盗聴する者）がいる場合の暗号手法。
  2. ^ a b 悪意あるシステム侵入等の不正な攻撃に対する備えが出来ている状態[23]。事務所店舗で例えると「いつでも防犯セキュリティが作動する(secure)」警備保障された状態のことで、概念として安全(safety)とは別物。
  3. ^ 後述の"GMW"パラダイムは、この3者の頭文字(Goldreich, Micali, Wigderson)を採ったもの。
  4. ^ a b 攻撃者を2種類に大別すると、半分正直者(semi-honest)のパッシブな攻撃者と、悪意の(malicious)あるアクティブな攻撃者に分類される。前者は「プロトコルには従うものの、計算過程で得られた情報から秘匿された情報を得ようとする」受動的攻撃者で、後者は「不正な参加者をプロトコルから逸脱させて秘匿情報を得るほか、プロトコルを失敗に終わらせたり、データ改ざんも行う」能動的攻撃者を指す[8][9][10]。
  5. ^ 各参加者に渡される、秘匿情報から生成された分割データのこと。個々のシェアを見ても元の秘匿情報を知ることはできず、なおかつ十分な数のシェアを集めれば秘匿情報を復元できるデータ。詳細は秘密分散を参照。
  6. ^ 個人情報と同義だが、関数計算で使用することになる私的な数値データ。年収や貯蓄額、オークションの入札額などが典型例。
  7. ^ コバート(Covert)とは、判別手段を用いてわかるセキュリティのこと。一方、見てわかるセキュリティをオバート(Overt)という[27]。
  8. ^ a b 国内文献も基本的に英単語表記しており定訳不明。MPC文脈上の意味としては、入力値（参加者の個人データ）を秘匿したまま計算結果を出力[31]できるように、回路の論理ゲート構造（の一部）を「目隠し」[32]すること。

出典

  1. ^ 岩本貢、太田和夫、西出隆志「マルチパーティ計算の情報理論的解析」電気通信普及財団研究調査助成報告書 No.31、2016年
  2. ^ Ran Canetti, et al., "Adaptively Secure Multi-party", TOC/CIS groups, LCS, MIT (1996), p. 1.
  3. ^ A. Shamir, R. Rivest, and L. Adleman, "Mental Poker", Technical Report LCS/TR-125, Massachusetts Institute of Technology, April 1979.
  4. ^ Andrew C. Yao, Protocols for secure computations (extended abstract)
  5. ^ Andrew Chi-Chih Yao:How to Generate and Exchange Secrets (Extended Abstract). FOCS 1986: 162-167.
  6. ^ a b Micali, Silvio; Goldreich, Oded; Wigderson, Avi (1987). How to play any mental game. pp. 218-229. doi:10.1145/28395.28420. https://doi.org/10.1145/28395.28420. 
  7. ^ 古典的GMWパラダイムは実用的か?非対話型アクティブセキュア2PCの場合【JST・京大機械翻訳】
  8. ^ a b プライバシーテック研究所「【技術】MPC技術入門② MPCのセキュリティ定義」2021年6月11日
  9. ^ 藤﨑英一郎 2018, p. 9.
  10. ^ 菊池.五十嵐(2018), p. 13.
  11. ^ Zvi Galil, Stuart Haber, Moti Yung: "Cryptographic Computation: Secure Fault-Tolerant Protocols and the Public-Key Model". CRYPTO 1987: 135-155.
  12. ^ David Chaum, Ivan Damgård, Jeroen van de Graaf: "Multiparty Computations Ensuring Privacy of Each Party's Input and Correctness of the Result". 87-119.
  13. ^ a b Abascal, Jackson; Faghihi Sereshgi, Mohammad Hossein; Hazay, Carmit; Ishai, Yuval; Venkitasubramaniam, Muthuramakrishnan (2020-10-30). “Is the Classical GMW Paradigm Practical? The Case of Non-Interactive Actively Secure 2PC”. Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. CCS '20 (Virtual Event, USA: Association for Computing Machinery): 1591-1605. doi:10.1145/3372297.3423366. ISBN 978-1-4503-7089-9. https://doi.org/10.1145/3372297.3423366. 
  14. ^ Joe Kilian: "Founding Cryptography on Oblivious Transfer". STOC 1988: 20-31.
  15. ^ D. Chaum, C. Crepeau & I. Damgård. “Multiparty unconditionally secure protocols”. Stoc 1988. 
  16. ^ Michael Ben-Or, Shafi Goldwasser, Avi Wigderson: Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract). STOC 1988: 1-10
  17. ^ Tal Rabin, "Michael Ben-Or: Verifiable Secret Sharing and Multiparty Protocols with Honest Majority (Extended Abstract)". STOC 1989: 73-85.
  18. ^ Danny Dolev, Cynthia Dwork, Orli Waarts, Moti Yung: "Perfectly Secure Message Transmission". J. ACM 40(1): 17-47 (1993).
  19. ^ Rafail Ostrovsky, Moti Yung: "How to Withstand Mobile Virus Attacks". PODC 1991. pp.51-59.
  20. ^ Claudio Orlandi: Is multiparty computation any good in practice?, ICASSP 2011
  21. ^ Peter Bogetoft, Dan Lund Christensen, Ivan Damgård, Martin Geisler, Thomas Jakobsen, Mikkel Krøigaard, Janus Dam Nielsen, Jesper Buus Nielsen, Kurt Nielse, Jakob Pagter, Michael Schwartzbach and Tomas Toft (2008). “Multiparty Computation Goes Live”. Cryptology ePrint Archive (Report 2008/068). http://eprint.iacr.org/2008/068. 
  22. ^ Moti Yung: From Mental Poker to Core Business: Why and How to Deploy Secure Computation Protocols? ACM Conference on Computer and Communications Security 2015: 1-2 https://dl.acm.org/citation.cfm?doid=2810103.2812701
  23. ^ e-words IT用語辞典「セキュア」の解説より
  24. ^ Michael Backes, Birgit Pfitzmann, and Michael Waidner. "A general composition theorem for secure reactive systems." In Theory of Cryptography Conference, pp. 336-354. Springer, Berlin, Heidelberg, 2004.
  25. ^ 藤﨑英一郎 2018, p. 0-53.
  26. ^ 藤﨑英一郎 2018, p. 61.
  27. ^ 木内正人, 高橋寛行, 大嶋一矢, 佐藤加代子「新時代のセキュリティ・デザイン・コンセプトの研究」『日本デザイン学会研究発表大会概要集』第64巻、日本デザイン学会、2017年、248頁、doi:10.11247/jssd.64.0_248、CRID 1390001205609544704。 
  28. ^ Aumann, Yonatan; Lindell, Yehuda (2007). Security against covert adversaries: Efficient protocols for realistic adversaries. pp. 137-156. doi:10.1007/978-3-540-70936-7_8. https://doi.org/10.1007/978-3-540-70936-7_8. 
  29. ^ a b 藤﨑英一郎 2018, p. 55.
  30. ^ Andrew C. Yao, "How to generate and exchange secrets," SFCS '86 Proceedings of the 27th Annual Symposium on Foundations of Computer Science, pp. 162-167, 1986.
  31. ^ Qiita「【秘密計算】最古のMulti-party Computationプロトコル「Yao's Garbled Circuit」とは」2020年12月11日
  32. ^ a b 安永憲司,2020年,5頁
  33. ^ 菊池.五十嵐(2018), p. 14.
  34. ^ プライバシーテック研究所「【技術】Oblivious Transfer (OT) とは」2020年7月3日
  35. ^ 安永憲司,2020年,3頁
  36. ^ 藤﨑英一郎 2018, p. 10頁.
  37. ^ Ben-Or, Michael; Goldwasser, Shafi; Wigderson, Avi (1988-01-01). Completeness theorems for non-cryptographic fault-tolerant distributed computation. ACM. pp. 1-10. doi:10.1145/62212.62213. ISBN 978-0897912648 
  38. ^ I. Damgard, V. Pastro, N. Smart and S. Zakarias, "Multiparty computation from somewhat homomorphic encryption," Crypto 2012, vol. Springer LNCS 7417, pp. 643-662, 2012.
  39. ^ Iddo Bentov, Ranjit Kumaresan (2014). “How to Use Bitcoin to Design Fair Protocols”. Cryptology e Print (129): 1-38. https://eprint.iacr.org/2014/129.pdf 2014年10月9日閲覧。. 
  40. ^ a b A. Ben-David, N. Nisan and B. Pinkas, "FairplayMP: a system for secure multi-party computation," ACM CCS 2008, pp. 257-266, 2008.
  41. ^ a b c B. Pinkas, T. Schneider, N. Smart and S. Williams, "Secure two-party computation is practical," Asiacrypt 2009, vol. Springer LNCS 5912, pp. 250-267, 2009.
  42. ^ 安永憲司,2020年,4頁
  43. ^ Y. Lindell and B. Pinkas, "An efficient protocol for secure two-party computation in the presence of malicious adversaries," Eurocrypt 2007, vol. Springer LNCS 4515, pp. 52-78, 2007.
  44. ^ Y. Lindell, "Fast cut-and-choose based protocols for malicious and covert adversaries," Crypto 2013 vol. Springer LNCS 8043, pp. 1-17, 2013.
  45. ^ B. Kreuter, a. shalet and C.-H. Shen, "Billion gate secure computation with malicious adversaries," USENIX Security Symposium 2012, pp. 285-300, 2012.
  46. ^ A. Shelat and C.-H. Shen, "Fast two-party secure computation with minimal assumptions," ACM CCS 2013, pp. 523-534, 2013.
  47. ^ T. Frederiksen and J. Nielsen, "Fast and maliciously secure two-party computation using the GPU, "ACNS 2013, vol. Springer LNCS 7954, pp. 339-356, 2013.
  48. ^ Y. Huang, J. Katz and D. Evans, "Efficient secure two-party computation using symmetric cut-and-choose.," CRYPTO, vol. Springer LNCS 8043, pp. 18-35, 2013.

参考文献

  • 藤﨑英一郎「マルチパーティ計算の理論」（PDF）、北陸先端科学技術大学院大学、2018年6月29日。 
  • 安永憲司「秘匿計算2」大阪大学、2020年6月15日、1-5頁。脚注にて、安永はGarbled Circuitのことを「目隠し回路」と訳している。
  • 菊池亮, 五十嵐大「秘密計算の発展」『電子情報通信学会 基礎・境界ソサイエティ Fundamentals Review』第12巻第1号、電子情報通信学会、2018年、12-20頁、doi:10.1587/essfr.12.1_12。 

外部リンク

  • 【技術】MPC技術入門①、同②、③、④ - プライバシーテック研究所、数式を含めた技術的解説（日本語）
  • The Fairplay Project - ヤオのプロトコルに基づくFairplayシステム
  • Secure Multiparty Computation Language - MPCのプログラミング言語および関連する暗号化ランタイム
  • SCALE-MAMBA MPC: Secure Computation Algorithms from LEuven - SPDZ系のMPCプロトコル