セキュアマルチパーティ計算（MPC）を理解する - 理論と実践
セキュアマルチパーティ計算（MPC）は、暗号技術における最も重要なブレークスルーの一つであり、各当事者が自らの秘密の入力に対して関数を共同で計算しながら、結果以外の情報を一切明かさないことを可能にします。本ガイドでは、MPCの理論的基盤、セキュリティの定義、そして実用的な応用について包括的に解説します。
セキュアマルチパーティ計算を理解する
理論から実践へ — MPCの理論的基盤、セキュリティの定義、そして実用的な応用に関する包括的なガイド
はじめに
分散コンピューティング環境では、複数の当事者が機微なデータを含む計算で協力する必要が生じることがよくあります。従来のアプローチでは、当事者は中央の管理者を信頼するか、自らの秘密情報を明かすかのいずれかを迫られます。セキュアマルチパーティ計算は、各当事者が結合された入力に対して関数を計算しながら、それらの入力を秘密に保つことを可能にすることで、この根本的なジレンマを解決します。
中核となるセキュリティ要件
MPCプロトコルは、いくつかの重要な特性を満たさなければなりません。
プライバシー
いずれの当事者も、定められた出力を超える情報を一切知ることはありません。他の当事者の入力について明らかになる唯一の情報は、出力そのものから導き出せるものに限られます。
正当性
各当事者は正しい出力を受け取ることが保証されます。いかなる悪意ある当事者も、指定された関数から逸脱するように結果に影響を与えることはできません。
入力の独立性
不正な当事者は、正直な当事者の入力とは独立して自らの入力を選ばなければならず、他者の値の知識に基づく攻撃を防ぎます。
配信の保証
不正な当事者は、サービス拒否攻撃によって正直な当事者が出力を受け取るのを妨げることができてはなりません。
公平性
不正な当事者が出力を受け取るのは、正直な当事者も自らの出力を受け取る場合に限られ、選択的な結果の拒否を防ぎます。
理想／現実パラダイム
MPCの標準的なセキュリティの定義は、理想／現実シミュレーションパラダイムと呼ばれる洗練されたアプローチに従います。
理想世界
計算を支援する、腐敗し得ない信頼された第三者が存在する世界を想像してみてください。
入力を送信
関数を計算
出力を返す
この理想的な実行においては、セキュリティは自動的に成立します。
| 特性 | 理想世界で成立する理由 |
|---|---|
| プライバシー | 各当事者は自らの出力しか見ず、それ以外は何も明かされません |
| 正当性 | 信頼された第三者は常に正しく計算します |
| 入力の独立性 | 入力は、いかなる出力を受け取る前に送信されます |
| 公平性 | 信頼された第三者はすべての出力を同時に配信します |
現実世界
現実には、そのような信頼された第三者は存在しません。その代わりに、当事者は互いの間でプロトコルを実行し、その一部が不正を働き、結託する可能性があります。あるプロトコルがセキュアであるとみなされるのは、敵対者が現実のプロトコル実行で行い得ることが、信頼された第三者が存在する理想的な実行でも同様に行い得る場合です。
敵対者モデル
敵対者の能力と挙動は、プロトコルの設計とセキュリティ保証に大きな影響を与えます。
敵対者の挙動
| モデル | 挙動 | ユースケース |
|---|---|---|
| セミオネスト（受動的） | 不正な当事者はプロトコルに従うが、実行の観測結果から追加情報を得ようとする | 意図しないデータ漏洩をモデル化する。能動的な攻撃ではない |
| 悪意ある（能動的） | 不正な当事者はプロトコルから任意に逸脱し得る | 最も強力かつ現実的な脅威モデル。あらゆる攻撃に対するセキュリティを保証する |
| カバート | 敵対者は悪意ある挙動をとり得るが、指定された確率で検出される | 検出が現実的な罰則を伴うシナリオをモデル化し、説明責任を通じて攻撃を抑止する |
不正化戦略
| 戦略 | 説明 | モデル化の対象 |
|---|---|---|
| 静的な不正化 | 不正な当事者の集合はプロトコル実行の開始前に固定される | 事前に定められた内部脅威 |
| 適応的な不正化 | 敵対者は、観測したトランスクリプトに基づき実行中に当事者を不正化し得る | システムに侵入する外部のハッカー、または実行途中で挙動を変える当事者 |
| プロアクティブセキュリティ | 当事者は不正化され、その後回復（再び正直になる）し得る | 侵害が発見されシステムがクリーンアップされる状況。限られた期間だけマシンを制御する敵対者に対してセキュリティが保証される |
基本的な実現可能性の結果
| 閾値 | 特性 | 要件 |
|---|---|---|
| 正直者多数（t < n/3） | 完全な公平性と出力配信の保証。計算量的または情報理論的なセキュリティ。 | 認証済みチャネルのみ（情報理論的な場合はプライバシーも） |
| 正直者多数（t < n/2） | 公平性と配信の保証。計算量的および情報理論的の両方の変種。 | 1対1のチャネルに加えてブロードキャストチャネル |
| 正直者多数なし（t >= n/2） | 「アボート付き」のセキュリティ。敵対者は出力を知りつつ、正直な当事者にはそれを拒否し得る。 | 一部の関数に固有の制約（例：公平なコイン投げは2者間では不可能） |
中核的な手法
Shamir秘密分散
多項式補間を用いた正直者多数MPCの基本的な構成要素です。
セットアップ
復元
セキュリティ
正直者多数MPCプロトコル
秘密分散を用いることで、当事者は算術回路をセキュアに評価できます。
各当事者は、(t+1)-out-of-n のShamir分散を用いて自らの入力を分散します。このフェーズの後、当事者はすべての入力ワイヤ値のシェアを保持します。
加算ゲート： 各当事者はローカルに自らのシェアを加算します。シェアが多項式a(x)とb(x)を表す場合、当事者iは c(i) = a(i) + b(i) を計算します。これは c(0) = a(0) + b(0) を満たす c(x) = a(x) + b(x) を定義します。通信は不要です！
乗算ゲート： 次数の増加のため、より複雑になります。当事者iは c(i) = a(i) x b(i) を計算し、次数2tの多項式（次数tではない）が得られます。0における値を保ちつつ次数を下げるため、追加のランダム分散と通信を用いた次数削減ステップが必要です。
当事者は出力ワイヤのシェアを指定された受信者に送信します。受信者は多項式補間によって出力を復元します。
プライベート集合積（PSI）
PSIは、集合XとYを持つ2者が、他の要素を明かすことなく X ∩ Y を計算したいという、特殊なMPC問題です。
鍵生成
Oblivious PRF
交換
照合
閾値暗号
閾値暗号は、いずれか単一の当事者が完全な秘密鍵を保持することなく、暗号演算（署名、復号）を可能にします。
モジュラー合成
セキュアMPCの重要な特性の一つがモジュラー合成です。セキュアであることが証明されたプロトコルは、より大規模なシステムにおいてサブルーチンとして安全に利用できます。
| 種類 | 条件 | 保証 |
|---|---|---|
| 逐次合成 | MPCプロトコルは他のプロトコルからの並行メッセージなしに実行される | より大規模なシステムでもセキュリティが保たれる。モジュラーな設計を可能にする。MPCは信頼された第三者の抽象として扱われる。 |
| 並行合成（UC） | 複数のプロトコルインスタンスが同時に実行される | ユニバーサル合成可能性（UC）は最も強力な保証を提供する。UCセキュアなプロトコルは、並行実行に関わらずセキュアであり続ける。ゴールドスタンダードだが、効率面のコストを伴う。 |
実用上の考慮事項
効率の進展
過去10年で、MPCは理論的な珍しいものから実用的なツールへと変貌を遂げました。
アルゴリズムの改善
優れたプロトコル設計により、暗号のオーバーヘッドを桁違いに削減する
ハードウェアの最適化
AES-NIやその他の専用命令を活用し、暗号演算を高速化する
専用コンパイラ
高水準のコードを最適化された回路に変換する。コストの高いANDゲートを最小化しつつ、コストの低いXORゲートを許容する
通信の最適化
帯域幅の要件を削減し、前処理技術を用いて計算をオフラインに移す
実世界での導入
ボストン賃金格差調査
114社にまたがる166,705人の従業員を分析。個々の給与を明かすことなく、男女間の賃金統計を計算。社会貢献のためのMPC。
Google広告コンバージョン
広告を表示された人々と実際の購入者との積集合を計算。正確なコンバージョン指標を可能にしつつ、ユーザーのプライバシーを保護する。
暗号鍵の保護
エンタープライズ向け鍵管理のための閾値暗号。単一障害点なしに署名鍵を保護する。暗号資産カストディやPKIで利用される。
エストニア政府
税務記録と教育記録を組み合わせ、学生の就労への影響を分析。プライバシーと規制遵守を維持した。
プライバシー保護機械学習
暗号化されたデータに対する機械学習。金融機関横断のマネーロンダリング対策。データを共有しないリスク評価。
重要な注意点
パフォーマンスのトレードオフ
| 要因 | 影響 |
|---|---|
| レイテンシ | 平文計算に比べてしばしば10〜1000倍遅い |
| 帯域幅 | 暗号プロトコルは相当量の通信を必要とする |
| メモリ | 一部のプロトコルは中間値のために大きなストレージを必要とする |
MPCの未来
MPCは、研究における「長期戦」を体現しています。純粋な理論から実用的な導入へと、30年以上をかけて歩んできました。
近年の進展
数桁に及ぶパフォーマンスの改善。成熟した実装とツール。産業界での採用拡大と標準化の取り組み。
残された課題
非専門家にとってMPCを利用しやすくすること。非常に大規模なデータセットを効率的に扱うこと。複雑な計算を経済的にサポートすること。
有望な方向性
MPCと他の技術を組み合わせるハイブリッドなアプローチ。ハードウェアアクセラレーションと専用チップ。より優れたコンパイルと最適化のツール。
結論
セキュアマルチパーティ計算は、理論的な可能性から実用的な現実へと進化しました。理想／現実パラダイムによって形式化されたその強力なセキュリティ保証は、あたかも腐敗し得ない信頼された第三者が計算を実行しているかのようにプロトコルが振る舞うことを保証します。効率性と使いやすさの継続的な進歩により、MPCはますますデータ駆動型となる世界において、プライバシーを保護する計算のための不可欠なツールとなりつつあります。
参考文献
本記事は、Yehuda Lindell著「Secure Multiparty Computation」（初出：Communications of the ACM、2021年1月、Vol. 64, No. 1、86〜96ページ）に基づいています。