📝
【MPC技術入門①】Multi-Party Computationの基本と応用
はじめに
この記事は、マルチパーティ計算(multi-party computation:MPC)技術の入門に適した書籍である「A Pragmatic Introduction to Secure Multi-Party Computation [1]」を参考にした、MPC技術解説の１回目の記事となります。今後もMPC技術入門シリーズとして解説していく予定です。
今回は、MPCの基本を説明し、MPCの応用・事例を中心に解説していきます。
MPCの基本
MPCとは、秘密計算（データを暗号化したまま計算を行うことができる技術）を実現するための手法の一つであり、複数の参加者が共同で計算を行います。すなわち次のような計算を行います。
組の参加者がいて、 番目の参加者が秘密の入力 を持っているとします。 組の参加者は、自分の入力を秘匿したまま、共同で を計算します。
MPCによる実際の計算手法にはバリエーションがあり、秘匿化の方法やその他の設定によって差異があります。ここでは、最も簡単かつ一般的な秘匿化手法である加法的秘密分散法をベースとした場合の、加算プロトコルについて紹介します。
組の参加者がおり、 番目の参加者の秘密情報を とします。
ここで、 を計算することを考えます。つまり、全ての組がもつ秘密情報の総和を求める処理に相当します。
この関数 の計算手順は以下です。
- 番目の参加者は、 となる をランダムに生成します。
- に乱数を割り当て、 とします。
- 番目の参加者は、番目の参加者に を送信します。
- 番目の参加者は、 を計算します。
- ここで、 です。
- 全ての参加者に を共有します。
- 各参加者は受け取った全ての値を用いて を実行すると、 であることから、 を自身以外の秘密情報 を知ることなく計算することができました。
このように、MPCでは複数の参加者があるプロトコルにしたがって計算を進めます。この時、入力情報の安全性は、加法的秘密分散などの秘密分散技術やその他の秘匿化技術によって担保されています。
補足情報
上記で紹介したMPCによる方法以外にも、秘密計算を実現する手法として準同型暗号を用いたものがあります。準同型暗号については次の記事で紹介していますので、興味のある方はぜひ一読をおすすめします。
応用可能な分野の例
ここでは、MPCの応用可能な分野について説明します。大枠として、どういった分野でMPCが有効に働くのかについて説明します。
オークション
オークションの方式によっては、プライバシーが重要となります。重要な要素として、「入札額が秘密であること」と「他人の入札に依存した入札ができないこと」があります。
「他人の入札に依存した入札ができないこと」は、例えばある参加者の入札額が 円だったとして、その入札を利用して 円の入札をする、といったことができないということです。
オークションの方式のひとつとして、封印入札オークションがあります。
封印入札オークションとは、「入札者は商品を購入するために相互に知ることができない入札を行い、入札額の最も大きい入札者に商品が販売される」という形式のオークションです。
「入札額が秘密であること」や「他人の入札に依存した入札ができないこと」といった性質が無いと、最初に入札した人はそれより僅かに上回る入札をされるなどして不利になります。
MPCを用いれば、「最高額の入札者」や「最高額」などの結果を、各入札者の入札額について明らかにすることなく求めることができます。
投票
投票においても、オークションと同様に、「投票が秘密であること」や「他人の投票に依存した投票ができないこと」は重要です。また、投票が正しく行われることは重要であるため、これらの性質が法律などによって規定されていることがあります。例えば、日本では「電子投票システムに関する技術的要件及び解説」[3]などで規定されています。
ただし、投票は標準的なMPCのセキュリティの定義ではカバーされていない性質を必要とする可能性があります。特に、「特定の投票行為を強制することができない」という特性はMPCでは標準的ではありません。（この特性を持つMPCの研究にはKüsters ら[4]があります。）
機械学習
機械学習の推論フェーズや学習フェーズにMPCが使用できます。
推論フェーズ
クライアントのテスト入力とサーバの学習済みモデルを利用して、お互いの入力やモデルについて知ることなく、モデルの推論した結果を返すことができます。
すなわち、MPCはクライアントの入力 とサーバの学習済みモデル を秘密の入力として、推論結果 を返します。
例えば、Microsoft が発表したCrypTFlow [2]は、TensorFlow の推論コードをMPCプロトコルに変換するシステムです。このシステムは平文のTensorFlow の推論精度に一致するという結果が得られています。また、現実のニューラルネットワーク（RESNET50 やDENSENET121 など）を用いて、ImageNet データセットに対する推論を現実的な時間で行えるという結果が得られています。
学習フェーズ
MPCを使用して、モデルを学習する際にそのデータを非公開にしたまま学習することができます。
すなわち、MPCは各参加者のデータ を秘密の入力として、学習済みモデル を返します。
データを秘密にしたまま提供できることで、プライバシー保護や秘密情報開示への抵抗といったデータ提供に関する障壁を取り払うことができます。
ただし、ほとんどの機械学習では大規模なデータセットが必要であり、一般的なMPCを用いて秘密のデータセット全体を高速に学習させることは難易度が高いため、特別な工夫が必要になることが多いです。
例えば、MPCと準同型暗号を組み合わせたり[5][6]、算術演算を効率的に実行するカスタムプロトコルを開発するようなハイブリットアプローチが設計されています[7]。
こちらに関連した内容については、以下の記事でも取り扱っておりますので、参考にしていただければと思います。
具体的な事例
こちらではMPCが使用された事例を紹介します。具体的にどういった背景があって、MPCが使用されたのかについて説明します。
デンマークの甜菜オークション[8][9]
デンマークでは数千人の農家が甜菜を生産しています。ほとんどの甜菜農家はデンマーク唯一の甜菜加工会社であるDanisco 社と契約を結び、契約にしたがって甜菜を納めています。ところが、EUが甜菜農家への支援を削減したことなどが原因で、生産能力の高い農家に契約を再分配する必要が出てきました。
甜菜農家は、その経済力や生産性がDanisco 社に推測されると考え、入札を公開したくありません。一方で、契約における数量の管理をDanisco 社が管理しているため、Danisco 社から独立したオークションを行うことはできませんでした。
そこで、Danisco 社・農民組合・研究機関の３者間のMPCで実施することで、甜菜農家の入札を秘匿化したままオークションを実施することができました。
エストニアの学生に関する調査[10][11]
エストニアではIT系学生の卒業率の低さが問題となっていました。これについて、大学在学中の就業が原因だとする仮説が立てられました。この仮説を検証するために、エストニアのICT協会は（文部科学省が保有する）教育記録と（財務省の税務・関税局が保有する）納税記録を調査し、その相関関係を調べようとしました。
しかし、個人情報保護法により文部科学省と財務省の間でデータを共有することが難しく、このままでは検証を実施することはできませんでした。そこで、Cybernetica 社のMPCソフトウェアであるSharemind を用いて、データを秘匿化したまま上記の仮説検証が行われました。
分析の結果、在学中に働くことと期間内に卒業できることの間に、特に相関は見つからなかったということです。このように、データを秘匿化したままの状態で仮説検証を実施することができました。
ボストンの賃金公平性調査[12][13]
ボストン市とBWWCは、ボストン地域内の雇用者における性別・民族による賃金格差についての調査を実施しようとしましたが、プライバシーの問題により直接給与データを得ることができませんでした。
そこで、企業がBWWCやボストン大学に生のデータを預けずに調査を実施できるように、MPCを用いた集計ツールをウェブサービスとして実装しました。これによって、生の給与データを扱うことなく、（アンケートなどではない）実際の給与データに対する調査を実施することができました。
鍵の管理[14]
暗号鍵の管理では、鍵を保管してるサーバへの攻撃が大きな脅威となっています。しかし、サーバへの攻撃を完全に防ぐことは難しく、場合によっては鍵本体を攻撃者によって盗まれてしまうこともあります。
そこで、MPCを用いて鍵サーバの機能を複数のサーバに分割し、鍵を直接生成することなく認証を行います。このようにすると、攻撃者は鍵を盗むために複数のサーバに攻撃をしなければならず、鍵を盗むことが難しくなります。
以上４つのMPCを用いた事例についてご紹介しました。これら以外にも、MPCのユースケースについては過去のAcompanyブログでも解説しています。こちらも是非ご覧ください。
まとめ
- MPCは秘密計算の手法の一つで、複数の参加者が共同で計算を行うものである。
- MPCはオークション・投票・機械学習などに応用できる。
- MPCを用いた事例として、オークション・データ分析・鍵の管理などがある。
MPCは各参加者のデータを秘匿したまま様々な計算を行うことができ、様々な場面でその有用性を発揮します。特に、今までプライバシーなどの問題で扱えなかったデータを活用できるようになるとして、期待されている技術です。
参考文献
[1]
David Evans, Vladimir Kolesnikov, and Mike Rosulek. 2018. "A Pragmatic Introduction to Secure Multi-Party Computation".
[2]
Kumar N. et al. 2020. "CRYPTFLOW: Secure TensorFlow Inference".
[3]
総務省選挙部(2020), 「電子投票システムに関する技術的要件及び解説」
[4]
Küsters, R., T. Truderung, and A. Vogt. 2012. “A game-based definition of coercion resistance and its applications”. Journal of Computer Security. 20(6): 709–764.
[5]
Nikolaenko, V., U. Weinsberg, S. Ioannidis, M. Joye, D. Boneh, and N. Taft. 2013b. “Privacy-Preserving Ridge Regression on Hundreds of Millions of Records”. In: 2013 IEEE Symposium on Security and Privacy. IEEE Computer Society Press. 334–348.
[6]
Gascón, A., P. Schoppmann, B. Balle, M. Raykova, J. Doerner, S. Zahur, and D.
Evans. 2017. “Privacy-Preserving Distributed Linear Regression on HighDimensional Data”. Proceedings on Privacy Enhancing Technologies.
2017(4): 248–267.
[7]
Mohassel, P. and Y. Zhang. 2017. “SecureML: A System for Scalable PrivacyPreserving Machine Learning”. In: 2017 IEEE Symposium on Security
and Privacy. IEEE Computer Society Press. 19–38.
[8]
Tomas Toft. 2012. "The Danish Sugar Beet Auctions".
https://csrc.nist.gov/csrc/media/events/meeting-on-privacy-enhancing-cryptography/documents/toft.pdf
[9]
Bogetoft P. et al. 2009. "Secure Multiparty Computation Goes Live".
[10]
Bogdanov D. et al. 2016. "Students and Taxes: a Privacy-Preserving Study Using Secure Computation".
[11]
sharemind. (2015). "Track Big Data Between Government and Education".
[12]
Lapets A. et al. 2016. "Secure MPC for Analytics as a Web Application".
[13]
BWWC. 2021. "WAGE GAP STUDIES".
[14]
Unbound Tech. 2019. “Control Your Own Keys in the Cloud”.