📝
【技術】Multi Party Computationとは
はじめに
本記事では、秘匿計算(秘密計算)プロトコルの総称である、Multi-Party Computation（以下MPC）について解説していきます。
MPCは秘匿計算の一種で、プライバシー保護計算を実現するために1980年代に発表されました。
秘匿計算とは、データを暗号化したまま計算できる計算手法で、計算結果以外の情報が他者に漏れません。詳しくは別の記事で説明しているので、合わせてお読みください。
MPCとは
MPCとは、複数のサーバが協力して行う秘匿計算技術です。
ある秘密情報から任意の計算 を適用した結果を求めたい時、ある一つのサーバで計算を行う場合、計算中にその一ヶ所に秘密情報が集約してしまうため攻撃の対象になりやすく、秘密情報の漏洩リスクが高くなってしまいます。
そこで秘密情報を暗号化して計算サーバに送り、以降は暗号化された状態のまま計算を行うことで、計算中に何らかの要因で情報が漏洩しても秘密情報の漏洩を防ぐことができます。
この暗号化の仕組みに「秘密分散」という手法を用いて複数のサーバが協力し合って計算を行う仕組みが、MPCです。
以下、MPCを用いた加算の実現例を元に原理を解説していきます。
前提として、 人の参加者 がいる場合に、参加者は自身の秘密情報 を持っているとします。この時、参加者が秘密情報 を明かさずに実行したい計算 の計算結果を得ることが目標です。
参加者は任意の秘密分散法(今回はシャミアの秘密分散法を用いることとします)で、 をシェア に分けます。
そして、各シェアと法 を全ての参加者に秘密裏に分配し、全員の秘密情報のシェアを全員が共有した状態にします。
その後、参加者は自身の持つ全てのシェア に対して以下のように加法を適用します。
そして、最後に全ての参加者が計算した を集めて、計算結果を復号することで、各参加者が他社の秘密情報を知らずに計算結果のみを受け取ることができます。
このように、MPCでは複数のデータ所有者が計算に使用したい秘密情報の断片(シェア)を共有し合い、各々がそのシェアを使って計算を実行し、実行結果を一箇所に集めて本来の計算結果を得ることでセキュアな秘匿計算を実現しています。
しかしながら、複数のサーバが大量に計算し、データのやりとりをする必要があったため、理論が確立された当初は実用的ではありませんでした。しかし、近年効率の良いアルゴリズムや、プロトコルが研究され、実用化されるようになりました。
以下で実用化されるまでに至った歴史を振り返ります。
MPCの歴史
MPCの研究は、1979年1月にAdi Shamir, Ronald L. Rivest, Leonard M. Adlemanによって発表されたMental Pokerを行うためのプロトコルから始まりました。
Mental Pokerとは、信頼できる第三者のいない状況で物理的に監視の目が届かない程離れた参加者同士が公正にゲームを行うために提起される一連の暗号問題で、言い換えると、信頼できる第三者の存在なしに許可された参加者のみが特定の情報にアクセスするためにどうすべきかという問題です。
彼らが提案したこの問題に対するプロトコルこそが、暗号化を使用して2-party間で安全な計算を行うために考案された最初のプロトコルでした。
ちなみに、前述した秘密分散法の一つであるシャミア秘密分散法は、Shamir によってMental Poker と同じ年の1979年11月に発表され、今なお様々な分野において重要な役割を果たしています。
Mental Pokerについての最初の発表があった後、オリジナルのプロトコルでは意味のある部分情報が漏洩してしまうことが発見されたため、1982年にShafi GoldwasserとSilvio Micaliによって改良が加えられ、Semantic securityと呼ばれる暗号文から平文に関する部分情報が解読困難である意味論的安全なプロトコルが実現されました。
同じ年の1982年に、Andrew Yaoがm 人の参加者で秘匿計算f(x_1, x_2, …,x_m) を行う方法を提案し、その後1986年に、現在多くの効率的なMPCプロトコルの基礎となっている、Yao's Garbled Circuit Protocol が考えられました。
そこから、一般的に知られる計算に対応したSecure Two-Party Computation(2PC) として議論されるようになり、1980年代後半にはm-party に一般化されたGoldreich-Micali-Wigderson(GMW) やBen-Goldwasser-Wigderson(BGW) などが発表され、今日のMPCとして研究が進められていきました。
1987年の時点で、すでにパーティー間に攻撃者が存在した場合を想定した場合にも有効であることが実証され、情報理論的安全性が担保されました。
この時期に、理論から実用に向けてパラダイムシフトが起き始めました。
今まで考案されてきた手法は、計算コストや通信コストの面であまり効率的とは言えない設計となっていたため、以降で実用化を目指した研究がされていきました。
そして、遂に2004年にXOR ゲートとAND ゲートで構成された回路を実装した、Fairplayというシステムが登場しました。
このシステムにより、データ数10のソートされた数列2つの中央値を計算するというタスクが達成され、ここからさらなる改良が進み、様々な実用的なタスクが達成されていきました。
研究分野では、2010年にはネットワークの監視、2015年にはゲノミクスの分野、2017年には広告のコンバージョン、メールのスパムフィルタ、機械学習などに適用されました。
実世界では、オークション、プライバシーに関わる内容のアンケート、秘密鍵の管理などにMPCが適用されました。
デンマークで行われた甜菜(ビート)のオークションでは、農家連合、加工会社、研究機関の3者間でのMPCによって、農家は加工会社に入札額を知られないことで生産能力を秘匿しながら、加工会社は重要な契約に関わる情報をセキュアにしたままオークションを行うことが可能になりました。
MPCによる秘密鍵の管理では、秘密鍵をシェアに分けて複数のサーバにおき、本来の鍵の所有者とサーバー群の間でMPCを通して行うことによって鍵自体の復号なしに鍵認証を実現しました。
まとめ
暗号化したままデータ分析が可能な技術である秘匿計算技術は、近年実社会での実用化例の増加に伴い注目されており、中でもMPCはすでに高いレベルで実用化されています。
今後、MPCを用いた秘匿計算技術の社会実装をさらに加速していくことで、今までプライバシーの観点から扱うことのできなかった価値のある膨大なデータをあらゆる分野で有効活用することが可能になると期待されています。