秘匿マルチパーティ計算のソースを表示

{{翻訳直後|1=[[:en:Secure multi-party computation]]09:44, 9 August 2022|date=2022年8月}}
'''秘匿マルチパーティ計算'''（ひとくマルチパーティけいさん、英:Secure multi-party computation）とは、多人数の参加者で行う[[秘匿共通集合計算プロトコル|秘匿計算プロトコル]]の総称であり、複数の参加者がそれぞれ自身の入力値を秘匿したままで多入力関数の値のみを計算することが可能となる[[暗号学]]的な手法をいう<ref name=UEC>岩本貢、太田和夫、西出隆志「[https://www.taf.or.jp/files/items/572/File/036.pdf マルチパーティ計算の情報理論的解析]」[[電気通信普及財団]]研究調査助成報告書 No.31、2016年</ref>。単に'''マルチパーティ計算(MPC)'''や'''秘密計算'''、[[プライバシー]]保護計算とも通称される。従来の暗号化手法{{Refnest|group="注釈"|暗号化によって通信やストレージの秘匿性と整合性が保証され、参加者のシステム外部に攻撃者（送受信を盗聴する者）がいる場合の暗号手法。}}とは異なり、このモデルの暗号化は参加者のプライバシーを相互に保護する。

秘匿マルチパーティ計算の基礎は、信頼できる第三者機関([[TTP]])を必要とせずに遠距離でゲームプレイやコンピュータ演算の業務を模擬試験する[[メンタルポーカー]]{{enlink|mental poker}}という暗号作業の研究で1970年代後半に始まった。従来の暗号化とは文章内容の隠蔽に関するものだったが、この新種の計算およびプロトコルは、様々な情報源からのデータで計算しながらもデータに関する部分的な（プライバシー関連の）情報を秘匿して、正確に計算結果を生み出す手法である。

1980年代後半までに、<!--Michael Ben-Or、-->[[シャフィ・ゴールドワッサー]]や[[アヴィ・ヴィグダーソン]]<!--、そして個別にDavid Chaum、Claude Crépeau、 Ivan Damgård -->などが「セキュア{{Refnest|group="注釈"|name=scur}}なチャネル設定で任意の関数を秘匿計算する方法」を提示する論文を発表した<ref>Ran Canetti, et al., "[http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-682.pdf Adaptively Secure Multi-party]", TOC/CIS groups, LCS, MIT (1996), p. 1.</ref>。

== 歴史 ==
特定タスク向けの特殊な目的のプロトコルは、1970年代後半に開発が始まった<ref>A. Shamir, R. Rivest, and L. Adleman, "Mental Poker", Technical Report LCS/TR-125, Massachusetts Institute of Technology, April 1979.</ref>。その後1982年に、秘匿計算が[[#二者間計算|二者間秘匿計算]](2PC)として正式に[[ブール論理|ブール叙述]]の問題で<!--（いわゆる[[ヤオの億万長者問題]]のために）-->導入され、1986年には実用的なコンピュータ演算向けの一般化が[[アンドリュー・ヤオ]]によって導入された<ref name="Yao">Andrew C. Yao, [http://www.cs.wisc.edu/areas/sec/yao1982-ocr.pdf Protocols for secure computations] (extended abstract)</ref><ref>Andrew Chi-Chih Yao:[https://ieeexplore.ieee.org/document/4568207 How to Generate and Exchange Secrets (Extended Abstract)]. FOCS 1986: 162-167.</ref>。この分野は秘匿関数評価(Secure Function Evaluation,SFE)とも呼ばれる。2者間の場合に続いてゴールドライヒ、ミカーリ、ヴィグダーソン{{Refnest|group="注釈"|後述の"GMW"パラダイムは、この3者の頭文字(Goldreich, Micali, Wigderson)を採ったもの。}}により多数参加者（マルチパーティ）の場合への一般化が行われた。この演算処理は、あらゆる入力の[[秘密分散]]と潜在的に悪意あるケースへの[[ゼロ知識証明]]に基づいており、そこでは大多数の正直な参加者に悪意ある攻撃者が混じっている場合に不正な振る舞いが検知され、不正な人物が排除されたり不正人物による入力が判明しながらも演算は継続する。この仕組みは、秘匿計算にとって本質的に全ての<!--（未来の）-->マルチパーティプロトコルが従うべき非常に基本的かつ一般的な手法を示唆するものだった<ref name="goldreich_87">{{Cite journal |author=Micali, Silvio; Goldreich, Oded; Wigderson, Avi |year=1987 |title=How to play any mental game |book=Proceedings of the Nineteenth ACM Symp. on Theory of Computing, STOC |pages=218-229 |organization=ACM New York, NY, USA |doi=10.1145/28395.28420 |url=https://doi.org/10.1145/28395.28420}}</ref>。この研究成果によりGMWパラダイム<ref>[https://jglobal.jst.go.jp/detail?JGLOBAL_ID=202002244246774003 古典的GMWパラダイムは実用的か?非対話型アクティブセキュア2PCの場合【JST・京大機械翻訳】]</ref>と通称されるアプローチが導入され、これはsemi-honestことパッシブな攻撃者{{Refnest|group="注釈"|name=adv|攻撃者を2種類に大別すると、半分正直者(semi-honest)のパッシブな攻撃者と、悪意の(malicious)あるアクティブな攻撃者に分類される。前者は「プロトコルには従うものの、計算過程で得られた情報から秘匿された情報を得ようとする」受動的攻撃者で、後者は「不正な参加者をプロトコルから逸脱させて秘匿情報を得るほか、プロトコルを失敗に終わらせたり、データ改ざんも行う」能動的攻撃者を指す<ref name="名前なし-20230316131020">プライバシーテック研究所「[https://acompany.tech/privacytechlab/mpc-multi-party-computation-2/ 【技術】MPC技術入門② MPCのセキュリティ定義]」2021年6月11日</ref>{{sfn|藤﨑英一郎|2018|p=9}}{{sfn|菊池.五十嵐(2018)|p=13}}。}}に対して秘匿マルチパーティ計算プロトコルを、maliciousことアクティブな攻撃者に対してセキュアな単一プロトコルをコンパイルするのが目的である。

この研究成果に続くのが初となる[[堅牢性|堅牢]]な秘匿プロトコルで、これは作業を通じて誰かの出力を明かしたりせず誤った行動を寛大に許容する。この目的のために、しばしば使われる「シェア{{Refnest|group="注釈"|各参加者に渡される、秘匿情報から生成された分割データのこと。個々のシェアを見ても元の秘匿情報を知ることはできず、なおかつ十分な数のシェアを集めれば秘匿情報を復元できるデータ。詳細は[[秘密分散]]を参照。}}の分散という構想」<ref>[[Zvi Galil]], Stuart Haber, Moti Yung: "[https://link.springer.com/chapter/10.1007%2F3-540-48184-2_10 Cryptographic Computation: Secure Fault-Tolerant Protocols and the Public-Key Model]". CRYPTO 1987: 135-155.</ref>と、参加者の1人がその入力を無条件に隠すことを許すプロトコルが発明された<ref>David Chaum, Ivan Damgård, Jeroen van de Graaf: "[https://link.springer.com/chapter/10.1007%2F3-540-48184-2_7 Multiparty Computations Ensuring Privacy of Each Party's Input and Correctness of the Result]". 87-119.</ref>。GMWパラダイムは、その基幹プロトコルを運用する莫大な処理時間<!--（オーバーヘッド）-->のため非効率的だと長年考えられていた。しかし、効率的なプロトコルを実現できることが示され、そのことが実用的な観点からこの一連の研究への関心をより高めている<ref name=":0">{{Cite journal|last=Abascal|first=Jackson|last2=Faghihi Sereshgi|first2=Mohammad Hossein|last3=Hazay|first3=Carmit|last4=Ishai|first4=Yuval|last5=Venkitasubramaniam|first5=Muthuramakrishnan|date=2020-10-30|title=Is the Classical GMW Paradigm Practical? The Case of Non-Interactive Actively Secure 2PC|url=https://doi.org/10.1145/3372297.3423366|journal=Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security|series=CCS '20|location=Virtual Event, USA|publisher=Association for Computing Machinery|pages=1591-1605|doi=10.1145/3372297.3423366|isbn=978-1-4503-7089-9}}</ref>。上の成果は攻撃者が[[多項式時間]]のコンピュータ計算に限定された場合のモデルで、あらゆる通信を監視するため、このモデルが「コンピュータ計算モデル(computational model)」と呼ばれている。さらに、これらタスクに対して[[紛失通信プロトコル]]が要件を完全に満たすことが示された<ref>Joe Kilian: "[http://dl.acm.org/citation.cfm?doid=62212.62215 Founding Cryptography on Oblivious Transfer]". STOC 1988: 20-31.</ref>。上の結果から、過半数の利用者が正直な（プロトコルの指示に忠実で、不正行為を全くしない）場合、秘匿計算が上述のバリエーション下で実現できることが確証された。

次に解決すべき問題は、秘匿通信チャネルで攻撃者には[[ポイント・ツー・ポイント]]通信が利用できない場合である。この場合に、参加者の最大1/3が不正行為者かつmaliciousという状況で解決できることが示されており、その解決策とは暗号化ツールを一切適用しない事である（秘匿通信が利用可能なので）<ref name="CCD">{{cite journal|author1=D. Chaum, C. Crepeau |author2=I. Damgård |name-list-style=amp |title=Multiparty unconditionally secure protocols|journal=Stoc 1988}}</ref><ref>Michael Ben-Or, Shafi Goldwasser, Avi Wigderson:
Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract). STOC 1988: 1-10</ref>。[[ブロードキャスト]]チャネルの追加は、システムに最大1/2までの少数派不正行為者を許容する<ref>Tal Rabin, "[http://dl.acm.org/citation.cfm?doid=73007.73014  Michael Ben-Or: Verifiable Secret Sharing and Multiparty Protocols with Honest Majority (Extended Abstract)]". STOC 1989: 73-85.</ref>。とはいえ、通信グラフ上の接続制限が『Perfectly Secure Message Transmission』という書籍で調査された<ref>Danny Dolev, Cynthia Dwork, Orli Waarts, Moti Yung: "[http://dl.acm.org/citation.cfm?doid=138027.138036 Perfectly Secure Message Transmission]". J. ACM 40(1): 17-47 (1993).</ref>。

歳月を経て、汎用マルチパーティプロトコルの概念は基本的かつ一般的なプロトコルの課題（[[秘密分散#プロアクティブ秘密分散|プロアクティブ秘密分散]]に見られるような汎用的結合可能性{{enlink|Universal Composability}}やモバイル攻撃者など）を調査するための潤沢な分野となった<ref>Rafail Ostrovsky, Moti Yung: "[http://dl.acm.org/citation.cfm?doid=112600.112605 How to Withstand Mobile Virus Attacks]". PODC 1991. pp.51-59.</ref>。

2000年代後半以降<!--および確実に2010年以降-->は、汎用プロトコルの分野が実用的アプリケーションを念頭にプロトコルの効率向上に取り組むものへと移行している。MPCにとって効率性の高まるプロトコルが提案されており、今やMPCは<!-- distributed votingや-->民間入札やオークション、署名の分散や復号関数、個人情報検索といった様々な現実的問題<!--（特に線形秘密分散を必要とし、当事者間のやりとりが多くないシェア上で主にローカル操作だけを必要とするもの）-->に対する実用的解決策だと考えられている<ref>Claudio Orlandi: [http://u.cs.biu.ac.il/~orlandi/icassp-draft.pdf Is multiparty computation any good in practice?], ICASSP 2011</ref>。2008年1月に、MPCで初となる大規模かつ実用的なアプリケーションが[[デンマーク]]で運用された（実際のオークション問題で実演）<ref>{{cite journal|url=http://eprint.iacr.org/2008/068|author= Peter Bogetoft, Dan Lund Christensen, Ivan Damgård, Martin Geisler, Thomas Jakobsen, Mikkel Krøigaard, Janus Dam Nielsen, Jesper Buus Nielsen, Kurt Nielse, Jakob Pagter, Michael Schwartzbach and Tomas Toft|title= Multiparty Computation Goes Live|journal= Cryptology ePrint Archive|issue= Report 2008/068|year=2008}}</ref>。当然であるが、理論的概念と調査の両方そして適用される構造が必要である（例えば、MPCを日々の業務の一環に移行するための条件が提唱された）<ref>Moti Yung: From Mental Poker to Core Business: Why and How to Deploy Secure Computation Protocols? ACM Conference on Computer and Communications Security 2015: 1-2
https://dl.acm.org/citation.cfm?doid=2810103.2812701</ref>。

2020年、秘匿マルチパーティ計算に取り組んでいる多くの企業が「MPC技術の認識、受け入れ、採用を加速する」ことを目的とする[https://www.mpcalliance.org/ MPCアライアンス]を設立した。

== 定義と概要 ==
MPCにおいて、所定の参加者数p<sub>1</sub>, p<sub>2</sub>, ..., p<sub>N</sub>各々が有する個人データ{{Refnest|group="注釈"|[[個人情報]]と同義だが、関数計算で使用することになる私的な数値データ。[[年収]]や[[貯蓄]]額、オークションの入札額などが典型例。<!--[[三十六進法]]を活用すればアルファベットのA-Zにも対応可能。-->}}をそれぞれd<sub>1</sub>, d<sub>2</sub>, ..., d<sub>N</sub>とする。参加者達は、自分の入力を秘匿したままその個人データで公開関数の値F(d<sub>1</sub>, d<sub>2</sub>, ..., d<sub>N</sub>)を計算したいとする。

例えば、青山、石井、宇野の参加者3名にそれぞれの給与を示す入力 x, y, zがあると想定しよう。彼らは、自分達が各々どのくらい稼ぐのかを互いに明かすことなく、3者のうち最も高い給料を見つけたいとする。数学的にこれは次の計算式に変換される。
: {{math|F(x, y, z) {{=}} max(x, y, z)}}

信頼できる外部関係者（例えば、秘密を口外しない事で知られる共通の友人トニー）がいれば、彼らはトニーに自分達の給与額を伝えることが可能で、彼が最大値を計算してその数値を彼ら全員に伝えることができる。MPCの目的は、青山と石井と宇野が友人トニーに頼ることなく、つまり誰がいくら稼いでいるかを明
かさずに{{math|F(x, y, z)}}が分かるようなプロトコルを設計することにある。彼らは、不正をしない完全に信頼できるトニーとのやりとりから分かる以上の事を、同プロトコルに携わって知るべきではない。

ここで参加者達が知りうる全ての事は、その出力と自身の入力から知りうる事である。したがって上の例だと、出力がzなら宇野は自分のzが最大値であることを知り、青山と石井は（仮にx, y, zの数値が異なるとすれば）自分の入力が最大値ではなく、誰の給料なのか秘密保持された最大値がzであることを知る。基本的なシナリオとして、参加者達が異なる入力値を持っていて関数が参加者ごとに異なる値を出力する場合に、一般化させることが容易である。

非公式ではあるが、MPCプロトコルが保証する目的となる最も基本的な[[プロパティ]]は次のとおり。
*個人データ入力：参加者の保持する個人データに関する情報は、プロトコル実行中に送信されたメッセージから一切推測できない。個人データに関して推測可能な唯一の情報は、関数の出力だけを見て推測できるものとなる。
* [[正当性 (計算機科学)|正当性]]：情報を共有したり指示からの逸脱をも厭わない攻撃者のいかなる共謀集団<!--（数学的には真部分集合）-->も、プロトコルの実行中に偽りの結果を正直な参加者に出力させることはできない。これには2つの特徴がある。正直な参加者には正しい出力を算出することが保証されており（堅牢なプロトコル）、エラーが見つかった場合は処理中断する（中断ありのMPCプロトコル）。

コイン投げなどの単純タスクから、電子オークション<!--(市場清算価格の計算)-->や電子投票やプライバシー保護しつつのデータマイニングといった複雑なものまで、多彩な実用的アプリケーションが存在する。古典的な例として、2人の億万長者が双方とも相手の資産額を知らずに済む方法でどちらがより金持ちなのかを知りたがる、[[ヤオの億万長者問題]]{{enlink|Yao's Millionaires' problem}}がある。この状況に対する解決策は、本質的に比較関数で秘匿的に評価することである。

== セキュリティの定義 ==
MPCプロトコルが有効であるにはセキュア{{Refnest|group="注釈"|name=scur|悪意あるシステム侵入等の不正な攻撃に対する備えが出来ている状態<ref>e-words IT用語辞典「[https://e-words.jp/w/%E3%82%BB%E3%82%AD%E3%83%A5%E3%82%A2.html セキュア]」の解説より</ref>。事務所店舗で例えると「いつでも防犯セキュリティが作動する(secure)」警備保障された状態のことで、概念として安全(safety)とは別物。}}でなくてはならない。現代の暗号学において、プロトコルのセキュリティは安全性証明に関連している。安全性証明とは、プロトコルのセキュリティがその基礎となる[[プリミティブ型]]セキュリティの安全性に帰着する数学的証拠を指す。とはいえ、参加者の知識とプロトコルの正確性に基づいて暗号化プロトコル{{enlink|Cryptographic protocol}}の安全性検証を常に公式化できるわけではない。MPCプロトコルの場合、プロトコルの動作する環境には現実世界/理想世界のパラダイムが付きものである<ref name="BPW">Michael Backes, Birgit Pfitzmann, and Michael Waidner. "[https://link.springer.com/chapter/10.1007/978-3-540-24638-1_19 A general composition theorem for secure reactive systems]." In Theory of Cryptography Conference, pp. 336-354. Springer, Berlin, Heidelberg, 2004.</ref>。参加者は出力の操作を学ぶ必要があり、出力は入力に依存するため、彼等が何も知りえないとは言えない。しかも、出力の正確性は参加者の入力しだいであって、入力が正しいとの前提が必要な出力の正確性は保証されない（入力を間違えれば計算結果の出力も正確ではなくなる）。

現実世界/理想世界のパラダイムは2つの世界を論じている<ref name="名前なし-20230316131020"/>{{sfn|藤﨑英一郎|2018|p=0-53}}。(i) 理想世界モデルでは、各プロトコル参加者がその入力を送信する、絶対的に信頼できる参加者<math>T</math>が存在する。この信頼された<math>T</math>が（参加者達から受け取った入力データを使って）自ら関数を計算し、適切な出力を各参加者に送信する。(ii) 対照的に現実世界モデルでは絶対に信頼できる<math>T</math>がおらず、参加者達はプロトコルを用いて相互に通信することにより<math>T</math>の機能を実現することを目指す。現実世界における各参加者の個人データ入力に関して、このプロトコルのために（攻撃者が）理想世界で知りうる以上のことを知りえない場合に、セキュアだとされる。理想世界では参加者間でのメッセージ交換（[[メール]]や[[ソーシャル・ネットワーキング・サービス|SNS]]等の通信やりとり）が一切ないため、現実世界のように交換したメッセージから秘密情報が暴かれることはない。

現実世界/理想世界パラダイムはMPCの複雑さを単純に抽象化し、MPCの中核プロトコルは実際のところ理想的実行に見せかけたアプリケーションの構築を可能にしている。理想的な場合にアプリケーションがセキュアであれば、実際のプロトコルが代わりに実行される場合でもセキュアである。MPCプロトコルのセキュリティ要件は厳重である。とはいえ1987年には、アクティブ(malicious)な攻撃者に対するセキュリティ<ref name="goldreich_87" />と前述した初期の仕組みを用いて、任意の関数を秘匿して計算できることが実証された。これらの公開にもかかわらず、当時のMPCは実際に使用されるほど効率的に設計されていなかった。無条件または情報理論上の秘匿MPCは[[秘密分散]]の問題（より具体的には[[検証可能秘密分散法]]）と密接な関連があり、秘密分散法に基づいて構築されており、多くの秘匿MPCプロトコルがこれをアクティブな攻撃者に対して使っている。

暗号や署名といった従来の暗号化アプリケーションとは異なり、MPCプロトコルの攻撃者はシステムに参加している利用者の 1人<!-- (または統制されている内部の当事者) -->だと想定する必要がある。不正<!--(corrupted)-->な参加者個人や集団は、プロトコルのセキュリティを侵害するために結託する場合がある。<math> n</math>をプロトコルの参加者数、<math> t </math>を攻撃者になりうる参加者の数としよう。<math>t < n/2</math>つまり過半数が正直だと想定される場合のプロトコルおよび解決策 は、そのような想定ではない場合とは異なる。後者の場合、参加者の1人が不正な可能性がある二者計算(two-party computation)の重要なケースと、無制限の参加者達が不正となり正直な参加者を攻撃するため結託する一般的なケースがある。

異なるプロトコルに直面させられる攻撃者達は、彼らがどの程度プロトコルからの逸脱を試みるかに応じて分類できる。基本的に2種類の攻撃者がおり{{Refnest|group="注釈"|name=adv}}、それぞれには異なる形のセキュリティが立ち上がる<!--（それぞれ異なる現実世界シナリオに適合する）-->。
*パッシブ(Semi-Honest)対処セキュリティ:この場合、不正参加者は単にプロトコルから情報を収集するために協力するが、プロトコルの仕様から逸脱しないことが前提となる。これはお人好しな敵モデルで、実際の状況では弱いセキュリティが敷かれる。しかし、このレベルのセキュリティを実現するプロトコルは、<!--(それ以外に協力する)-->参加者間の不注意な情報漏洩を防いでおり、かつこれが唯一の懸念事項である場合に有益である。さらに、Semi-Honestモデルのプロトコルは非常に効率的で、多くの場合さらに高レベルのセキュリティを達成するための重要な第一歩である。
*アクティブ(Malicious)対処セキュリティ:この場合、攻撃者は[[チート]]操作を試みてプロトコルの実行から故意に逸脱する可能性がある。このモデルでのセキュリティを実現するプロトコルは、彼らにパッシブ攻撃者と同等の事しか出来ないよう強制する（それでも従わなければプロトコルから排除、攻撃者の秘密を開示してプロトコルを続行）のが大方針で{{sfn|藤﨑英一郎|2018|p=61}}、非常に高い警備保障を提供する。不正な振る舞いをする参加者が過半数の場合：非正直が過半数の場合に攻撃者が出来る唯一のことは、正直な参加者にチート操作を検知させて「処理中断」させることである。もし正直な参加者が出力を得る場合、それが正確であることは保証されており、彼らのプライバシーは常に保護されている。

アクティブな攻撃者に対するセキュリティは通常、コバートセキュリティ{{Refnest|group="注釈"|コバート(Covert)とは、判別手段を用いてわかるセキュリティのこと。一方、見てわかるセキュリティをオバート(Overt)という<ref>{{Cite journal|和書|author=木内正人, 高橋寛行, 大嶋一矢, 佐藤加代子 |date=2017 |url=https://doi.org/10.11247/jssd.64.0_248 |title=新時代のセキュリティ・デザイン・コンセプトの研究 |journal=日本デザイン学会研究発表大会概要集 |publisher=日本デザイン学会 |volume=64 |page=248 |doi=10.11247/jssd.64.0_248 |id={{CRID|1390001205609544704}}}}</ref>。}}につながる有効性の低下をもたらす<ref>{{Cite journal |author=Aumann, Yonatan; Lindell, Yehuda |year=2007 |title=Security against covert adversaries: Efficient protocols for realistic adversaries |issue=Theory of Cryptography: 4th Theory of Cryptography Conference, TCC 2007, Amsterdam, The Netherlands, February 21-24, 2007. Proceedings 4 |pages=137-156 |organization=Springer |doi=10.1007/978-3-540-70936-7_8 |url=https://doi.org/10.1007/978-3-540-70936-7_8}}</ref>。コバートセキュリティはより現実的な状況を捕捉しており、そこでは捕まらない場合にのみアクティブな攻撃者がチート操作に励んでいる。例えば、彼らの評判が落ちると、他の正直な参加者との将来的な協力が妨害される可能性があったとする。すると、コバートで秘匿なプロトコルは、一部の参加者が指示に従わなかった場合に75%や90%の高確率で通知される事を保証するメカニズムを提供する。ある意味、コバートな攻撃者は外部の暗号以外の懸念材料（ビジネス等）のためパッシブ行動せざるをえなくなったアクティブ攻撃者である。このメカニズムは、実際に有効で十分にセキュアなプロトコルが見つかることを期待して、両モデル間の橋渡しを設定している。

多くの暗号化プロトコルと同様、MPCプロトコルのセキュリティは以下の前提に依存している。
*それは計算を含んで（つまり因数分解のような幾つかの数学的問題に基づいて）いる場合があり、通信チャネル上でメッセージが物理的に活用できないことに依存している<!--(usually with some probability of error which can be made arbitrarily small)-->。
*このモデルは、参加者が「ある瞬間」に送信したメッセージが常に次の「瞬間」に到着する[[同期ネットワーク]]を使うか、セキュアで信頼性の高い[[ブロードキャスト]]チャネルが存在する、または攻撃者がチャネル内のメッセージを読み取ったり、変更したり、生成できない参加者のあらゆる二者間に秘匿通信チャネルが存在する、ことを前提としている。

計算タスクを実行しうる正直な参加者群は、[[アクセス構造]]の概念と関わりがある。攻撃者構造はstatic{{sfn|藤﨑英一郎|2018|p=55}}になることがあり、この場合に攻撃者はMPCの開始前に被害者を選択している。またadaptive{{sfn|藤﨑英一郎|2018|p=55}}にもなることがあり、この場合はMPCの実行中に被害者を選択して（不正者として）操るので防御が困難になる。攻撃者構造は、閾値構造またはより複雑な構造として定義できる。閾値構造では、攻撃者は最大で幾つかの閾値まで参加者数のメモリを破損ないし読み取ることができる。一方、複雑な構造では起こりうる様々な共謀をモデル化しており、攻撃者は参加者の<!--事前定義された-->特定の部分集合に悪影響を与える。

== プロトコル ==
二者間計算(2PC) 用とマルチパーティ計算 (MPC)用に提案されたプロトコルには大きな違いがある。また多くの場合、特殊な目的に特化した重要なプロトコルでは、一般的なものから外れたプロトコルを設計する必要がある（投票、オークション、支払い等）。

=== 二者間計算 ===
{{Main|:en:Secure two-party computation}}
参加者2名の設定は、マルチパーティの場合には適用されない二者設定に特化した手法を適用できるため、<!--アプリケーションの観点からだけでなく-->特に関心が高い。実際、秘匿マルチパーティ計算<!--（実際に秘匿関数評価の制限されたケースで、この場合は単一の関数のみが評価される）-->は最初に2者間設定で提示された。最初の研究としてヤオの論文<!--2つのうち1つ-->がしばしば挙げられるが<ref name="Yao86">Andrew C. Yao, "How to generate and exchange secrets," SFCS '86 Proceedings of the 27th Annual Symposium on Foundations of Computer Science, pp. 162-167, 1986.</ref>、その論文に今でいうヤオの[[Garbled Circuit]]プロトコルと通称されるものは実際のところ含まれていない。

ヤオの 基本プロトコルはパッシブ(Semi-Honest)な攻撃者に対してセキュアであり、ラウンド数（これは不変で、評価を行う標的関数と独立している）の観点から非常に有効である。その関数は、固定長バイナリへの入力があるブール回路だと見なされる。ブール回路は、3種類のワイヤ（回路入力ワイヤ、回路出力ワイヤ、中間ワイヤ）を接続した[[論理回路|論理ゲート]]の集まりである。各ゲートが2本の入力ワイヤを受信し、ファンアウト（すなわち次の段階で複数のゲートに渡される）の可能性がある単一の出力ワイヤを有する。この回路の簡易評価は、各ゲートを順番に評価することで行われる。ゲートが位相的に順列されていると仮定する。ゲートは、[[ビット]]同士（入力ワイヤのゲートから来るもの）で起こりえる組み合わせそれぞれに表が一意の出力ビットを割り当てるような[[真理値表]]として表される。これがゲートの出力ワイヤの値である。評価結果は、回路出力ワイヤで得られたビットである。

ヤオは、送信側と受信側の参加者2名が回路の出力だけを知れるように回路をgarble{{Refnest|group="注釈"|name=gabl|国内文献も基本的に英単語表記しており定訳不明<!--（一般には「[[文字化け]]等で解読不能にする」という意味）-->。MPC文脈上の意味としては、入力値（参加者の個人データ）を秘匿したまま計算結果を出力<ref>Qiita「[https://qiita.com/tktktktk/items/c7498456fcbb22814526 【秘密計算】最古のMulti-party Computationプロトコル「Yao's Garbled Circuit」とは]」2020年12月11日</ref>できるように、回路の論理ゲート構造（の一部）を「目隠し」<ref name="名前なし-20230316131020-2">安永憲司,2020年,5頁</ref>すること。}}処理させる方法を説明した。<!--高レベル箇所は当方の知識不足により翻訳断念。以下原文。At a high level, the sender prepares the garbled circuit and sends it to the receiver, who obliviously evaluates the circuit, learning the encodings corresponding to both his and the sender's output. He then just sends back the sender's encodings, allowing the sender to compute his part of the output. The sender sends the mapping from the receivers output encodings to bits to the receiver, allowing the receiver to obtain their output.-->

より詳細には、garbled circuitは次のように計算される。主な構成は[[共通鍵暗号|二重鍵の対称暗号]]方式である。回路のゲートが与えられると、入力ワイヤのとりうる各値(0か1)は乱数で符号化される。入力ビットの採りうる4組の各ゲートの評価から得られた結果の値も、乱数文字列（ラベル）に置き換えられる{{sfn|菊池.五十嵐(2018)|p=14}}。ゲートのgarble処理した真理値表は、入力ラベルを鍵として用いる各出力ラベルの暗号で構成されている。真理値表の中にあるこれら暗号4つの位置は乱数化されるため、ゲートの情報は漏洩しない。

garble処理済み の各ゲートを正しく評価するにあたって、暗号化手法には次の2つの[[プロパティ (プログラミング)]]がある。第一に、任意の2つの公開鍵の土台となる暗号化関数の範囲は（圧倒的な高確率で）[[素集合]]である。2番目のプロパティは、与えられた暗号文が特定の鍵で暗号化されているかどうかを効率的に確認できるものだと言う。これら2つのプロパティを用いて受信側はあらゆる回路入力配線のラベルを取得した後、最初に4 つの暗号文のどれが自分のラベル鍵で暗号化されたのかを見つけ、次に復号して出力配線のラベルを取得することにより各ゲートを評価可能になる。評価中に受信者が知るのはビットのエンコード形式なので、これは気付かれずに実行される。

送信側（回路作成者）の入力ビットは、評価者にエンコード形式としてただ単に送信可能である。一方、彼の入力ビットに対応する受信側（すなわち回路評価者）のエンコード形式は、1-out-of-2OTの[[紛失通信プロトコル]]を介して取得される。このOTプロトコルは「送信者が送信した2つの情報のうち、どちらを受信者が受け取ったのかを送信者が知ることができず、受信者はどちらか片方の情報しか知ることができない」という性質の通信方法である<ref>プライバシーテック研究所「[https://acompany.tech/privacytechlab/oblivious-transfer-ot-mpc/ 【技術】Oblivious Transfer (OT) とは]」2020年7月3日</ref>。

仮にアクティブ(malicious)な攻撃者を考慮するなら、参加者双方の正しい行動を保証するため追加のメカニズムを構築する必要がある。仮にOTプロトコルがアクティブな攻撃者に対して既にセキュアであるなら、指示から逸脱した場合に受信者がやれることは回路出力ワイヤに到達できないgarbled circuitを評価することだけなので、送信者にセキュリティを示すのは簡単である。その状況は送信者側で大きく異なる。例えば、受信者の入力を明らかにする関数を計算する不適当なgarbled circuitを送信する場合もある。これはプライバシーがもはや保たれないことを意味するが、回路がgarble処理済みなので受信者はこれを検知しえない。ところで、[[ゼロ知識証明]]を有効に適用するなら、パッシブ(semi-honest)用プロトコルと比較して小さな処理時間でこのプロトコルをアクティブ(malicious)な攻撃者に対してセキュアにすることが可能である<ref name=":0" />。

=== マルチパーティプロトコル ===
大半のMPCプロトコルは、2PCプロトコルとは対照的に、特に私的チャネルの無条件設定下で秘密分散を利用する。秘密分散を根幹とする手法において、参加者達は特別な（ヤオでの創作者と評価者といった）役割を果たさない。代わりに、各ワイヤと関連付けられたデータが参加者間で分散され、各ゲートを評価するのに単一のプロトコルが使用される。この関数は、ヤオで使用される二進回路とは対照的に、[[有限体]]上の「回路」として定義されている。こうした回路は文献で算術回路(arithmetic circuit)と呼ばれ<ref>安永憲司,2020年,3頁</ref>、それは操作された値が有限体上に定義される[[加算]]と[[乗算]]の「ゲート」で構成されている。

秘密分散は、各参加者にシェアを配布することにより、多数の参加者間で1つの秘密配布を可能にしている。一般的には[[秘密分散#効率的な秘密分散法|シャミア秘密分散]]と[https://acompany.tech/privacytechlab/mpc-multi-party-computation-1/ 加法的秘密分散]という2種類の秘密分散法が用いられる。どちらの場合も分散は有限体の乱数要素で、合計するとその体における秘密となる。直感的には、何ら適用要件を満たさない一連のシェアが無作為に配られているように見えるため、セキュリティが実現される。

秘密分散法は合計<math>n</math>人の参加者のうち最大<math>t</math>人の参加者を統率する攻撃者1人を許容することができ、この場合tはその手法に基づいて変化し、攻撃者はパッシブでもアクティブでも可能で、攻撃者の能力について様々な想定がなされる。シャミア秘密分散法は、パッシブな攻撃者が<math>t < \frac{n}{2}</math>の場合、そしてアクティブな攻撃者が<math>t < \frac{n}{3}</math>の場合に対してセキュアでありつつ、[[情報理論的安全性]]（仮に攻撃者が無制限の計算能力を持っていたとしても分散の土台となる秘密に関する情報を何ら知りえないことを意味する）をも満たす{{sfn|藤﨑英一郎|2018|p=10頁}}。

秘密分散において加算と乗算の演算方法を定義するBGWプロトコルが<ref name="名前なし-20230316131020-2"/><ref>{{Cite book|last1=Ben-Or|first1=Michael|last2=Goldwasser|first2=Shafi|last3=Wigderson|first3=Avi|date=1988-01-01|title=Completeness theorems for non-cryptographic fault-tolerant distributed computation|publisher=ACM|pages=1-10|doi=10.1145/62212.62213|isbn=978-0897912648|s2cid=207554159}}</ref>、シャミア秘密分散での関数を計算するのにしばしば使用される。加法的秘密分散法は、無制限の計算能力を持つパッシブおよびアクティブな攻撃者に対するセキュリティを維持しつつ、<math>t < n</math>な場合を除く全ての参加者を統率する攻撃者を許容する。一部のプロトコルでは設定段階が必要で、これは計算的に有限の（計算力を持つ）攻撃者に対してのみセキュアな場合がある。

多くのシステムが、秘密分散法を備えたMPCの様々な形を実装している。最も普及しているのが SPDZで<ref name="SPDZ">I. Damgard, V. Pastro, N. Smart and S. Zakarias, "Multiparty computation from somewhat homomorphic encryption," Crypto 2012, vol. Springer LNCS 7417, pp. 643-662, 2012.</ref>、これは加法的秘密分散法のMPCを実装しており、アクティブな攻撃者に対してセキュアである。

=== その他のプロトコル ===
2014年に「出力の受信を処理中断(abort)させた攻撃者には事前に相互定義された罰金の支払いを余儀なくさせる秘匿計算の公平性モデル」が、[[ビットコイン]]ネットワークや公正な宝くじ向けに記述された<ref>{{cite journal|author1=Iddo Bentov, Ranjit Kumaresan|title=How to Use Bitcoin to Design Fair Protocols|journal=Cryptology e Print|date=2014|issue=129|pages=1-38|url=https://eprint.iacr.org/2014/129.pdf|access-date=9 October 2014}}</ref>。
== 実用的なMPCシステム ==
近年では、2PCおよびMPCのシステムで多くの進展がある。

=== ヤオに基づくプロトコル ===
ヤオに基づくプロトコルで作業する際の主な問題の1つは、安全に評価される関数<!--（任意のプログラムもありうる）-->を通常[[XORゲート]]と[[ANDゲート]]で構成する回路として表現する必要がある事である。現実世界のプログラムの大半にはループと複雑なデータ構造が含まれるため、これは非常に重要な作業である。Fairplayシステム<ref name="Fairplay">A. Ben-David, N. Nisan and B. Pinkas, "FairplayMP: a system for secure multi-party computation," ACM CCS 2008, pp. 257-266, 2008.</ref>が、この問題に取り組むべく設計された最初のツールだった。Fairplayは2つの主要コンポーネントで構成されている。最初のものは、利用者が単純な高水準言語でプログラムを作成し、これらプログラムをブール回路表現で出力可能にするコンパイラである。2番目のコンポーネントは、その後に回路をgarble{{Refnest|group="注釈"|name=gabl}}処理してプロトコルを実行し、garbled circuitを確実に評価できるようにする。ヤオのプロトコルに基づく二者計算と同じく、Fairplayはマルチパーティプロトコルの実行も可能である。これはBMRプロトコル<ref name="Fairplay" />を用いて行われ、これはヤオのパッシブ向け秘匿プロトコルをアクティブな場合に拡張したものである。

Fairplay導入後の数年で、ヤオの基本プロトコルに対する多くの改善が、アクティブセキュリティのために効率向上と技術面の双方で作成された。これにはXORゲートの評価をかなり単純化できるフリー XOR法や、garble処理した表の大きさを25%削減する garble処理行の削減などが含まれる<ref name="PSSW">B. Pinkas, T. Schneider, N. Smart and S. Williams, "Secure two-party computation is practical," Asiacrypt 2009, vol. Springer LNCS 5912, pp. 250-267, 2009.</ref>。

アクティブセキュリティを得る上でこれまで最も有益と思われるアプローチは、garble処理技術と「切り分け選択 (cut-and-choose)<ref>安永憲司,2020年,4頁</ref>の組み合わせから来ている。この組み合わせがより効率的な構造を構築すると考えられている。不正な動作に関して前述の問題を回避するために、同じ回路の様々なgarble処理が[[コンストラクタ]]から評価者に送られる。次に（運用プロトコル次第だが）それの約半分が一貫性をチェックするために開かれ、もしそうなら未開封のものの大部分は高確率で正しい。出力はあらゆる評価の多数票である（ここで過半数の出力が必要とされることに注意）。出力に不一致がある場合、受信者は送信者が不正操作をしていることを知っているが、そうしないと自分の入力情報が漏洩するため不満は言えない。

このアクティブセキュリティ用のアプローチは、リンデルとピンカスによって開始され<ref>Y. Lindell and B. Pinkas, "An efficient protocol for secure two-party computation in the presence of malicious adversaries," Eurocrypt 2007, vol. Springer LNCS 4515, pp. 52-78, 2007.</ref>、2009年に同技術がピンカスらによって実装された<ref name="PSSW" />。これにより、非常に複雑（約3万のANDゲートとXORゲートからなる）かつ[[自明性 (数学)|非自明]]な<!--（複数のアプリケーションを用いる）-->関数だと見なされる[[Advanced Encryption Standard]](AES)回路の最初のアクティブな秘匿二者評価が可能となった。当時はそのコンピュータ計算に約20分かかり、不正行為確率<math>2^{-40}</math>を得るには160回路が必要だった。

多数の回路が評価されるため、参加者達（受信者を含む）は全ての[[イテレータ|イテレーション]]で同じ値が使用されるよう自分の入力を[[コミット]]（変更を永続的に確定）する必要がある。ピンカスらの実験では<ref name="PSSW" />、プロトコルの[[ボトルネック]]が一貫性チェックの中に存在することが判明した。そのチェックは、AES回路を評価するために約6,553,600のコミットを様々な値でインターネット越しに送信する必要があった。近年の成果では<ref>Y. Lindell, "Fast cut-and-choose based protocols for malicious and covert adversaries," Crypto 2013 vol. Springer LNCS 8043, pp. 1-17, 2013.</ref>、ヤオに基づくアクティブ対応の秘匿実装プログラムの効率性はさらに向上し、しかも不正行為の確率<math>2^{-40}</math>を得るのに必要なのは40回路だけで、コミットは大幅に少なくなった。この改善は、送信された回路で切り分け選択を実施するための新しい方法論から生じた。

最近では、[[メニーコア]]のCPU上で実行するように設計されたgarbled circuitsに基づく高度な並列処理を行うプロトコル実装<!--（implementation）-->が注目されている。クロイターらは<ref>B. Kreuter, a. shalet and C.-H. Shen, "Billion gate secure computation with malicious adversaries," USENIX Security Symposium 2012, pp. 285-300, 2012.</ref>、強力な[[コンピュータ・クラスター]]の512コアで実行される実装プロトコルについて説明している。これらのリソースを使うと、回路が約60億ゲートからなる4095ビットの[[レーベンシュタイン距離|編集距離]]関数を評価できる。これを実現するにあたり、彼らはFairplay以上に最適化された回路コンパイラと[[パイプライン処理]]など幾つかの新しい最適化カスタムを開発した。<!--これによって回路の残り部分がまだ生成されている間に、garbled circuitsをネットワーク越しに送信し始める。-->AESの計算時間は、512[[ノード (ネットワーク)|ノード]]のクラスター機器を使って、アクティブな場合だと1.4秒/ブロックに短縮、1ノードを使うと115秒になった。シェラトおよびシェンはこれを改良し<ref>A. Shelat and C.-H. Shen, "Fast two-party secure computation with minimal assumptions," ACM CCS 2013, pp. 523-534, 2013.</ref>、汎用ハードウェアを使って0.52秒/ブロックを達成した。<!--同報告書は毎秒21ブロックの[[スループット]]を報告しているが、1ブロックあたり48秒の[[レイテンシー]]がある。-->

一方、別の研究者グループは一般消費者向け[[Graphics Processing Unit|GPU]]を使用して似たレベルの並列処理を成し遂げる研究をしている<ref name="FN">T. Frederiksen and J. Nielsen, "Fast and maliciously secure two-party computation using the GPU, "ACNS 2013, vol. Springer LNCS 7954, pp. 339-356, 2013.</ref>。彼らはOT拡張子ほか幾つかの新技術を活用してGPU固有のプロトコルを設計する。このアプローチは、似た数のコアを使用してクラスタコンピュータの実装プログラムと同等の効率を達成すると考えられている（ただし、著者らは約5万ゲートを有するAES回路の実装のみを報告）。ここで必要なハードウェアは、沢山の人のデスクトップコンピュータやゲーム機で同様のデバイスが既に見られるため、入手しやすいものである。著者らは、標準的GPUを備えた標準的なデスクトップ上で2.7秒/AESブロックの時間が出たとしている。仮にセキュリティをコバートセキュリティと似たものに削減できるなら、0.30秒/AESブロックの実行時間だという。パッシブセキュリティの場合、2.5億ゲートを有する回路を7500万ゲート/秒の速度で処理したのとの報告が存在する<ref>Y. Huang, J. Katz and D. Evans, "Efficient secure two-party computation using symmetric cut-and-choose.," CRYPTO, vol. Springer LNCS 8043, pp. 18-35, 2013.</ref>。

== 関連項目 ==
* [[デジタル通貨]]
* [[準同型暗号]]
* [[メンタルポーカー]]{{enlink|mental poker}}
* [[紛失通信プロトコル]]
* [[ヤオの億万長者問題]]{{enlink|Yao's Millionaires' problem}}

== 脚注 ==
=== 注釈===
{{Reflist|group="注釈"}}
=== 出典 ===
{{Reflist|30em}}
=== 参考文献 ===
<!--出典で「著者,年,頁」表記をした文献に限定。-->
* {{Cite journal|和書|author=藤﨑英一郎 |url=https://www.jaist.ac.jp/~fujisaki/2018/lec-mpc-kanazawa-20180629.pdf |format=PDF |title=マルチパーティ計算の理論 |publisher=北陸先端科学技術大学院大学 |date=2018-06-29 |pages=1-99 |ref=harv}}
* 安永憲司「[http://www-infosec.ist.osaka-u.ac.jp/~yasunaga/contsec/lec_mpc2.pdf 秘匿計算2]」[[大阪大学]]、2020年6月15日、1-5頁。脚注にて、安永は[[Garbled Circuit]]のことを「目隠し回路」と訳している。
* {{Cite journal|和書|publisher=電子情報通信学会 |title=秘密計算の発展 |author=菊池亮, 五十嵐大 |journal=電子情報通信学会 基礎・境界ソサイエティ Fundamentals Review |volume=12 |issue=1 |pages=12-20 |year=2018 |doi=10.1587/essfr.12.1_12 |url=https://doi.org/10.1587/essfr.12.1_12 |ref={{harvid|菊池.五十嵐(2018)}}}}

== 外部リンク ==
<!--英語版は羅列過剰なため、解説を主としたサイトを厳選（アーカイブサイトやGithubサイトは除外）。-->
* [https://acompany.tech/privacytechlab/mpc-multi-party-computation-1/ 【技術】MPC技術入門①]、[https://acompany.tech/privacytechlab/mpc-multi-party-computation-2/ 同②]、[https://acompany.tech/privacytechlab/mpc-multi-party-computation-3/ ③]、[https://acompany.tech/privacytechlab/mpc-multi-party-computation-4/ ④] - プライバシーテック研究所、数式を含めた技術的解説（日本語）
* [http://www.cs.huji.ac.il/project/Fairplay/ The Fairplay Project] - ヤオのプロトコルに基づくFairplayシステム
* [http://www.brics.dk/SMCL/ Secure Multiparty Computation Language] - MPCのプログラミング言語および関連する暗号化ランタイム
* [https://homes.esat.kuleuven.be/~nsmart/SCALE/ SCALE-MAMBA MPC: Secure Computation Algorithms from LEuven] - SPDZ系のMPCプロトコル

{{DEFAULTSORT:ひとくまるちはあていけいさん}}
[[Category:暗号理論]]
[[Category:暗号技術]]