はじめに
こちらの内容と流れを参考にいくつかの記事に分割してまとめていきたいと思います。項目は追加していく予定です。
- Multi-Party Computation (MPC)とは <- 本記事の内容
- 基本的なMPCプロトコル1（Oblivious Transfer, Garbled Circuits）
- 基本的なMPCプロトコル2（GMWプロトコル）
- 基本的なMPCプロトコル3（BGWプロトコル）
- 基本的なMPCプロトコル4（BMRプロトコル）
概要
Secure Multi-Party Computation（MPC）は、複数の当事者がそれぞれの秘密の入力値を公開することなく、共同で合意した関数の出力を計算する技術です。計算の途中経過や個別の入力を互いに明かすことなく、最終結果のみを共有することでプライバシー保護を実現します。医療・金融・統計分析など、データの秘匿性が重要な領域で特に必要な技術です。
具体例
簡素化して考えると以下のように足し算が構成できます。秘密の値XとYがあります。それぞれを足し算で分割して、1つ目の値をAさんに、2つ目の値をBさんに渡します。AさんBさんはそれぞれローカルで計算して、結果だけを値を検証する人に渡します。そうすると、AさんとBさん、そして結果をまとめる人は元の値XとYを知らない状態でX+Yの計算結果を得ることができます。
歴史
-
MPCの理論的な基盤は、1970〜80年代に“mental poker”などの特定問題で始まり、Yaoによる2者間計算（two-party computation）、そしてBen-Or, Goldwasser, Wigdersonなどによる汎用MPC（任意の関数の計算が秘密保持下で可能なモデル）へと発展しました。
-
そこから2000年代まではあくまで理論的なものでしたが、アルゴリズムの改善やコンピューティングコストの低下により実用可能なレベルに達しました。Fairplayが最初の汎用のセキュアコンピューティングの実装です。高級言語で秘匿計算をプログラムできましたが、こちらもまだパフォーマンスの観点で用途が制限されていました。そこからさらに研究は進み、MPCは5桁ほど計算効率が上がり、色々な用途への応用がなされています。
Outsourced Computation
MPCと似た構造を持つアイデアとして、Outsourced Computationがあります。第二者が暗号化されたデータを暗号化された状態で計算し、そのデータの保有者に返した後にデータ保有者が複合化することで計算結果を得られるというものです。準同型暗号がこれに使われていますが、MPCに比べて計算コストが高いです。一方でMPCは通信コストがかかるという点で、準同型暗号の計算コストが下がれば通信コストのとの総合でMPCとの競合になる可能性があります。そもそもMPCに準同型暗号を使うというアイデアもありますので完全に別物というわけではないようです。
アプリケーション
以下MPCが活用されている例です。
Yao's Millionairs Problem
2人のお金持ちが自分の資産を公開せずにどちらの資産額が大きいかを比較したいという状況で、秘匿した資産額それぞれ$x_1$, &x_2&を入力として、$x_1 < x_2$の結果をBooleanで出力します。
いわゆるGarbled Circuitと言われるものですが、次の記事でまた出てきますので詳細は割愛します。
プライバシー保護されたデータ分析
複数の機関が入力データを秘匿したまま共同で統計や解析を行う用途。医療データ、金融データ、マーケットリサーチ等で使われます。 札と価格を決定する際に不正を防ぐことが可能です。
機械学習におけるMPC
異なるデータ所有者がそれぞれのデータを明かさずに共同で学習（トレーニング）や予測（推論）を行う。モデルと入力双方の秘匿性を維持する応用があります。
鍵管理・デジタル署名
暗号通貨ウォレットなどで、秘密鍵を複数のパーティーに分割（シェア）して保管し、署名時に複数のシェアを用いて署名を行う方式。単一の秘密鍵が丸ごと露出するリスクを低減します。
Web3／ブロックチェーンにおけるMPCウォレット
Web3ウォレットで、トランザクション署名を複数のCustodian（管理者）で共同で行うなど、マルチシグとは違う形で秘密鍵管理を行う実装が広まっています。 Fireblocksとかが有名ですね。