秘匿マルチパーティ計算
特定タスク向けの特殊な目的のプロトコルは、1970年代後半に開発が始まった。その後1982年に、秘匿計算が二者間秘匿計算(2PC)として正式にブール叙述の問題で導入され、1986年には実用的なコンピュータ演算向けの一般化がアンドリュー・ヤオによって導入された。この分野は秘匿関数評価(Secure Function Evaluation,SFE)とも呼ばれる。2者間の場合に続いてゴールドライヒ、ミカーリ、ヴィグダーソンにより多数参加者(マルチパーティ)の場合への一般化が行われた。この演算処理は、あらゆる入力の秘密分散と潜在的に悪意あるケースへのゼロ知識証明に基づいており、そこでは大多数の正直な参加者に悪意ある攻撃者が混じっている場合に不正な振る舞いが検知され、不正な人物が排除されたり不正人物による入力が判明しながらも演算は継続する。この仕組みは、秘匿計算にとって本質的に全てのマルチパーティプロトコルが従うべき非常に基本的かつ一般的な手法を示唆するものだった。この研究成果によりGMWパラダイムと通称されるアプローチが導入され、これはsemi-honestことパッシブな攻撃者に対して秘匿マルチパーティ計算プロトコルを、maliciousことアクティブな攻撃者に対してセキュアな単一プロトコルをコンパイルするのが目的である。
現実世界における各参加者の個人データ入力に関して、このプロトコルのために(攻撃者が)理想世界で知りうる以上のことを知りえない場合に、セキュアだとされる。理想世界では参加者間でのメッセージ交換(メールやSNS等の通信やりとり)が一切ないため、現実世界のように交換したメッセージから秘密情報が暴かれることはない。
現実世界/理想世界パラダイムはMPCの複雑さを単純に抽象化し、MPCの中核プロトコルは実際のところ理想的実行に見せかけたアプリケーションの構築を可能にしている。理想的な場合にアプリケーションがセキュアであれば、実際のプロトコルが代わりに実行される場合でもセキュアである。MPCプロトコルのセキュリティ要件は厳重である。とはいえ1987年には、アクティブ(malicious)な攻撃者に対するセキュリティと前述した初期の仕組みを用いて、任意の関数を秘匿して計算できることが実証された。これらの公開にもかかわらず、当時のMPCは実際に使用されるほど効率的に設計されていなかった。無条件または情報理論上の秘匿MPCは秘密分散の問題(より具体的には検証可能秘密分散法)と密接な関連があり、秘密分散法に基づいて構築されており、多くの秘匿MPCプロトコルがこれをアクティブな攻撃者に対して使っている。
暗号や署名といった従来の暗号化アプリケーションとは異なり、MPCプロトコルの攻撃者はシステムに参加している利用者の 1人だと想定する必要がある。
大半のMPCプロトコルは、2PCプロトコルとは対照的に、特に私的チャネルの無条件設定下で秘密分散を利用する。秘密分散を根幹とする手法において、参加者達は特別な(ヤオでの創作者と評価者といった)役割を果たさない。代わりに、各ワイヤと関連付けられたデータが参加者間で分散され、各ゲートを評価するのに単一のプロトコルが使用される。この関数は、ヤオで使用される二進回路とは対照的に、有限体上の「回路」として定義されている。こうした回路は文献で算術回路(arithmetic circuit)と呼ばれ、それは操作された値が有限体上に定義される加算と乗算の「ゲート」で構成されている。
秘密分散は、各参加者にシェアを配布することにより、多数の参加者間で1つの秘密配布を可能にしている。一般的にはシャミア秘密分散と加法的秘密分散という2種類の秘密分散法が用いられる。どちらの場合も分散は有限体の乱数要素で、合計するとその体における秘密となる。直感的には、何ら適用要件を満たさない一連のシェアが無作為に配られているように見えるため、セキュリティが実現される。
秘密分散法は合計 n {\displaystyle n} 人の参加者のうち最大 t {\displaystyle t} 人の参加者を統率する攻撃者1人を許容することができ、この場合tはその手法に基づいて変化し、攻撃者はパッシブでもアクティブでも可能で、攻撃者の能力について様々な想定がなされる。
参加者2名の設定は、マルチパーティの場合には適用されない二者設定に特化した手法を適用できるため、特に関心が高い。実際、秘匿マルチパーティ計算は最初に2者間設定で提示された。最初の研究としてヤオの論文がしばしば挙げられるが、その論文に今でいうヤオのGarbled Circuitプロトコルと通称されるものは実際のところ含まれていない。
ヤオの 基本プロトコルはパッシブ(Semi-Honest)な攻撃者に対してセキュアであり、ラウンド数(これは不変で、評価を行う標的関数と独立している)の観点から非常に有効である。その関数は、固定長バイナリへの入力があるブール回路だと見なされる。ブール回路は、3種類のワイヤ(回路入力ワイヤ、回路出力ワイヤ、中間ワイヤ)を接続した論理ゲートの集まりである。各ゲートが2本の入力ワイヤを受信し、ファンアウト(すなわち次の段階で複数のゲートに渡される)の可能性がある単一の出力ワイヤを有する。この回路の簡易評価は、各ゲートを順番に評価することで行われる。ゲートが位相的に順列されていると仮定する。ゲートは、ビット同士(入力ワイヤのゲートから来るもの)で起こりえる組み合わせそれぞれに表が一意の出力ビットを割り当てるような真理値表として表される。これがゲートの出力ワイヤの値である。評価結果は、回路出力ワイヤで得られたビットである。
ヤオは、送信側と受信側の参加者2名が回路の出力だけを知れるように回路をgarble処理させる方法を説明した。
これを実現するにあたり、彼らはFairplay以上に最適化された回路コンパイラとパイプライン処理など幾つかの新しい最適化カスタムを開発した。AESの計算時間は、512ノードのクラスター機器を使って、アクティブな場合だと1.4秒/ブロックに短縮、1ノードを使うと115秒になった。シェラトおよびシェンはこれを改良し、汎用ハードウェアを使って0.52秒/ブロックを達成した。
一方、別の研究者グループは一般消費者向けGPUを使用して似たレベルの並列処理を成し遂げる研究をしている。彼らはOT拡張子ほか幾つかの新技術を活用してGPU固有のプロトコルを設計する。このアプローチは、似た数のコアを使用してクラスタコンピュータの実装プログラムと同等の効率を達成すると考えられている(ただし、著者らは約5万ゲートを有するAES回路の実装のみを報告)。ここで必要なハードウェアは、沢山の人のデスクトップコンピュータやゲーム機で同様のデバイスが既に見られるため、入手しやすいものである。著者らは、標準的GPUを備えた標準的なデスクトップ上で2.7秒/AESブロックの時間が出たとしている。仮にセキュリティをコバートセキュリティと似たものに削減できるなら、0.30秒/AESブロックの実行時間だという。パッシブセキュリティの場合、2.5億ゲートを有する回路を7500万ゲート/秒の速度で処理したのとの報告が存在する。
2014年に「出力の受信を処理中断(abort)させた攻撃者には事前に相互定義された罰金の支払いを余儀なくさせる秘匿計算の公平性モデル」が、ビットコインネットワークや公正な宝くじ向けに記述された。