Zenn
キリフダ株式会社Publicationへの投稿
💎

MPCを使ってみる

thanai
に公開
秘密計算
mpc
mpspdz
tech

はじめに

世間ではMCPの話題で持ち切りなので、あえてMPCの記事を書こうと思います。

NOT "Model Context Protocol", BUT "Multi-Party Computation"

MPCとは

MPCは、秘密計算の文脈における概念です。

MPC = Multi-Party Computationを直訳すると多者間計算ですが、これは単純に多数のノードが参加するというだけでなく、互いに秘密値を開示することなく共同で計算を行う仕組みを指します。

文で見ると分かりにくいですが、たとえば有名なものにYao's Millionaires' Problemがあります。

2人の富豪がいて、お互いの財産額を開示することなく、どちらの財産がより多いかを知るにはどうすればよいか？

この問題は、主に以下の2つの技術で解決できます：

  • Oblivious Transfer：
    送信者が2つのメッセージを持ち、受信者はそのうち1つだけを選んで受け取るが、送信者は受信者が何を選んだか知らず、受信者はもう一方のメッセージについて何も知らない通信プロトコル
  • Garbled Circuit:
    入力を与えると結果のみを知ることのできる形式で暗号化した論理回路を構築し、入力データを知ることなく計算を実行できるようにする技術

Yaoの富豪問題が提唱されたのは1980年代ですが、これを拡張していくと、たとえばn人のうちの最大の値を与えたものは誰か？のように、お互いの入札額を開示することなく成立するオークションや、誰が投票したかは明かさないが多数決を取ることが可能な計算などが可能になります。

なぜMPCが流行ってこなかったか

MPCは互いを信頼しなくても成り立たせるための仕組みですが、現実社会では信頼できる第三者を置くことで解決できるケースが多いからです。

たとえば、銀行が「両者が合意すれば、お互いの口座残高は教えませんが相手より高いかどうかだけは教えます」というサービスを提供するだけで事足ります。

これが秘密計算となると、お互いがプロトコルの原理を理解したうえで複雑で高コストな手続きを踏まなければなりません。

しかも銀行からすればそれがビジネスになるため、わざわざトラストレスなプロトコルを整備するインセンティブがあまり生まれません。

ブロックチェーン等の台頭による状況変化

逆に、ブロックチェーンなどのそもそもP2Pが前提となる仕組みの上で利用する場合はMPCも有用な選択肢になりえます。

MPC自体もP2Pの仕組みであり親和性が高いこと、近年のビットコインなどの暗号資産価格の高騰を考えると、高いコストを支払っても成り立つ可能性は高いでしょう。

実際、ZKP（ゼロ知識証明）などを利用したLayer2チェーンなど、これまで社会実装があまりされていなかったようなジャンルの活用も徐々に進んでいます。

また、直近の発展が目覚ましいAIによる開発がさらに進化して、個人で自分用のアプリを作れるような世界観になると、各自が持つ端末同士でのP2P通信が増えてくるかもしれません。

そうした状況ではトラストレスなプロトコルは有用なはずなので、MPCが主流な手段になるという話もそこまで突拍子がないわけではないでしょう。

ちなみに、ブロックチェーン外での既存事例としては、エストニアのCyberneticaが開発したSharemindというMPCプラットフォームがあります。

https://sharemind.cyber.ee/secure-mpc-on-big-data-with-conclave-and-sharemind/
https://sharemind.cyber.ee/sharemind-mpc/multi-party-computation/

MP-SPDZを使ってみる

さて、この記事ではMPCを手軽かつ高効率に利用できるMP-SPDZを利用してみたいと思います。

https://github.com/data61/MP-SPDZ

MP-SPDZは、SPDZというプロトコルをベースにして、その拡張ケースをいくつも含んだライブラリです。任意の拡張ケースを使って、多様な秘密計算を行うことができます。

今回は、その中でも特に高効率で堅牢なプロトコルであるMASCOTで任意のプログラムファイルを分散実行するというケースを試してみましょう。

SPDZとは

実際の利用に入る前にSPDZについて簡単に紹介しておくと、その特徴は大きく2つです。

  1. 悪意のある参加者に対しても耐性があること
  2. 事前計算で乗算・除算を高速化する工夫がされていること

1. 敵対的な参加者に対する耐性が高い

セキュリティモデルの観点から見ると、MPCは2つに大別できます。

  • Honest-but-curious（正直だが好奇心が強い）: 全参加者がプロトコルに忠実に従うが、収集した情報から秘密を推測しようとするモデル
  • Malicious（悪意のある）: 一部の参加者がプロトコルに従わず、積極的に攻撃してくるモデル

SPDZは後者の「悪意のある」参加者モデルに対応しています。これは「プロトコルにすら従わない」参加者が多くいてもそれを検知し、計算を中断できるという耐性を持っています。具体的には、参加者n人のうち、最大で(n-1)人までの不正な参加者がいても安全性を保証できます。

それまでの秘密計算プロトコルではHonest-but-curiousな参加者には耐性があるものの、そもそもプロトコルに従わず環境を破壊しようとする悪意を検知できなかったり、あるいはそれに対応しようとすると計算コストが高すぎて成り立たないものが多かったという背景があります。

2. 事前計算フェーズでの乗算トリプル生成による乗除算の高効率化

MPCにおいて、加減算は比較的簡単ですが、乗除算は非常に複雑になります。

例えば、3人で計算を行う際に秘密の値Xを、

X = x_1 + x_2 + x_3
となるようにランダムに分割して各自に1つずつ断片を配布したとします。

同様にYについても、

Y = y_1 + y_2 + y_3
と分割して配布しましょう。

加算

このとき、足し算は簡単です：

X + Y = (x_1 + x_2 + x_3) + (y_1 + y_2 + y_3)
= (x_1 + y_1) + (x_2 + y_2) + (x_3 + y_3)

つまり、各参加者が自分の持つ値同士を独自に足し合わせ、最後にそれらを合計するだけでよいです。

乗算

しかし、乗算はそうはいきません：

XY = (x_1 + x_2 + x_3)(y_1 + y_2 + y_3)
= x_1 y_1 + x_1 y_2 + x_1 y_3 + x_2 y_1 + x_2 y_2 + x_2 y_3 + x_3 y_1 + x_3 y_2 + x_3 y_3

一気に項が増えました。

それだけではなく、このままでは各参加者が知らない値（例えば参加者1はx_2, x_3, y_2, y_3を知らない）を掛け合わせる必要があり、単独で計算処理を進めることができません。

SPDZはこの問題を乗算トリプルと呼ばれる技術で解決します。これは事前に計算されたa, b, cという3つの値のセット（ここでc = a \cdot b）を用意しておき、実際の計算時にこれを利用することで乗算を効率的に行う手法です。

除算はさらに逆元を求めるような操作になるため、非常に計算工程が多くなります。計算の途中結果から秘密値を復元できてはならず、開示されるべきものだけが開示されるように乗除算を行うには、加減算と比較して指数的にコストが増大するものでした。

MASCOTとは

MASCOTは「Multiplicative Addition and Scalar Oblivious Transfer」の略で、SPDZの事前計算フェーズをさらに高効率かつトラストレスに実現できるようになった仕組みです。

SPDZの最大の課題は、乗算トリプルの生成に信頼できる第三者が必要だったり、高度な暗号技術が必要だったりする点でした。
MASCOTは冒頭で軽く紹介したOblivious Transfer（OT）という暗号プロトコルを拡張・最適化することで、より効率的に乗算トリプルを生成できるようにしています。

具体的には：

  • 通信オーバーヘッドの削減
  • 計算効率の向上
  • セキュリティの強化（Maliciousな敵対者に対する保護）

を実現しています。

MP-SPDZでの実装例

それでは実際にMP-SPDZを使って、簡単な秘密計算の例を実装してみましょう。ここでは、3人の参加者がそれぞれ秘密の数値を持っており、その平均値を計算するという簡単な例を考えます。

1. インストールと環境設定

# MP-SPDZのリポジトリをクローン
git clone https://github.com/data61/MP-SPDZ.git
cd MP-SPDZ

# 必要なパッケージをインストール
make setup

# MASCOTプロトコルに必要なライブラリをコンパイル
make mascot-party.x

Dockerを利用する場合は、

# MP-SPDZのリポジトリをクローン
git clone https://github.com/data61/MP-SPDZ.git
cd MP-SPDZ

# コンテナのビルド（MASCOTの初期化まで完了する）
docker build --target machine .

2. 計算プログラムの作成

以下のプログラムをaverage.mpcという名前で保存します：

# 各参加者は秘密の値を持つ
a = sint.get_input_from(0)
b = sint.get_input_from(1)
c = sint.get_input_from(2)

# 合計を計算
total = a + b + c

# 平均を計算（3で割る）
average = total / 3

# 結果を出力
print_ln('平均値: %s', average.reveal())

3. プログラムのコンパイル

./compile.py average

4. 分散実行

3つの異なるターミナルで以下のコマンドを実行します（それぞれ異なるプレイヤー番号を指定）：

# プレイヤー0（ターミナル1）
./mascot-party.x -N 3 -p 0 -OF . average

# プレイヤー1（ターミナル2）
./mascot-party.x -N 3 -p 1 -OF . average

# プレイヤー2（ターミナル3）
./mascot-party.x -N 3 -p 2 -OF . average

各ターミナルでは、プログラムが入力を求めてきますので、それぞれ秘密にしたい値（例えば10, 20, 30）を入力します。

5. 結果の確認

すべての計算が終了すると、各参加者ターミナルに以下のような結果が表示されます：

平均値: 20

このとき、-OF .を付けないで実行するとParty0にのみ表示されることに注意してください。

この例では各参加者がそれぞれの秘密の値（10, 20, 30）を開示することなく、その平均値（20）を共同で計算することができました。参加者はお互いの値を知ることなく、最終結果だけを得ることができています。

まとめ

MP-SPDZのようなライブラリの登場により、MPCの実装はこれまでに比べて格段に身近なものになりました。利用者は複雑な暗号プロトコルの詳細を深く理解しなくても、実行したい処理をPython風のスクリプトで記述するだけで、堅牢な秘密計算を行うことができます。

特に、MASCOTのような効率的なプロトコルが登場したことで、現実的なパフォーマンスでの秘密計算が可能となり、研究用途に限らず、一部のユースケースにおいては、実運用への応用も現実味を帯びてきていると言えるでしょう。

今回の例ではローカルマシン上の複数プロセスを使って計算を行いましたが、MP-SPDZはこれにとどまらず、ネットワーク越しのノード間通信や、計算途中のデータの永続化など、より本格的なケースにも対応しています。

キリフダ株式会社
キリフダ株式会社Publication

キリフダ株式会社は、web3／ブロックチェーンを事業戦略に取り込みたい事業者を、様々な検討フェーズから漸次推進でサポートする総合コンサルティング会社です。ブロックチェーンやWeb3技術を活用した事業開発支援から、システム設計・開発、運用まで、上流工程から実行・改善までをワンストップでサポートいたします。

Discussion