秘匿マルチパーティ計算

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

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

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

歴史

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

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

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

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

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

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

定義と概要

MPCにおいて、所定の参加者数p₁, p₂, ..., p_N各々が有する個人データをそれぞれd₁, d₂, ..., d_Nとする。参加者達は、自分の入力を秘匿したままその個人データで公開関数の値F(d₁, d₂, ..., d_N)を計算したいとする。

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

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

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

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

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

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

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

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

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

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

プロトコル

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

二者間計算

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

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

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

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

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

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

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

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

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

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

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

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

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

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

その他のプロトコル

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

実用的なMPCシステム

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

ヤオに基づくプロトコル

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

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

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

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

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

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

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

関連項目

• デジタル通貨
• 準同型暗号
• メンタルポーカー (mental poker) 
• 紛失通信プロトコル
• ヤオの億万長者問題 (Yao's Millionaires' problem) 

脚注

参考文献

• 藤﨑英一郎「マルチパーティ計算の理論」（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プロトコル