安全な二者間計算

セキュア2者間計算（2PC）またはセキュア関数評価は、セキュアマルチパーティ計算（MPC）のサブ問題であり、多くの暗号化タスクと密接な関係にあることから、研究者から特別な注目を集めています。^{[1] [2]} 2PCの目標は、2つのパーティが、入力の値を相手方と共有することなく、入力に対して任意の関数を共同で計算できる汎用プロトコルを作成することです。^[3] 2PCの最もよく知られた例の1つは、ヤオの億万長者問題で、アリスとボブという2人のパーティが億万長者であり、自分の富を明かさずにどちらがより裕福であるかを判断したいと考えています。^[4]正式には、アリスは富を持ち、ボブは富を持ち、またはの値を明かさずに計算したいと考えています。 ${\displaystyle a}$${\displaystyle b}$${\displaystyle a\geq b}$${\displaystyle a}$${\displaystyle b}$

2者間計算のためのYaoのガーブル回路プロトコルは、受動的な敵対者に対してのみセキュリティを提供しました。 ^[5]能動的な敵対者に対するセキュリティを実現するための最初の一般的なソリューションの1つは、Goldreich、Micali、Wigderson ^[6]によって、ゼロ知識証明を適用して半正直な動作を強制することによって導入されました。^[7]このアプローチは、計算量のオーバーヘッドが大きいため、長年非実用的であることが知られていました。ただし、この方法を2PCに適用することに向けて大幅な改善が行われ、Abascal、Faghihi Sereshgi、Hazay、Yuval Ishai、Venkitasubramaniamがこのアプローチに基づく最初の効率的なプロトコルを提供しました。^[8]能動的な敵対者に対して安全な別のタイプの2PCプロトコルは、Yehuda LindellとBenny Pinkas、^[9] Ishai、Manoj PrabhakaranとAmit Sahai ^[10]、Jesper Buus NielsenとClaudio Orlandiによって提案されました。^[11]この問題に対する別の解決策として、コミットされた入力を明示的に処理する解決策がスタニスワフ・ヤレツキとヴィタリー・シュマティコフによって提案された。^[12]

2者間計算プロトコルのセキュリティは、通常、定義上安全である理想的なシナリオとの比較を通じて定義されます。^[13]理想的なシナリオでは、信頼できる当事者が、安全なチャネルを介して2つの当事者（主にクライアントとサーバー）の入力を収集し、どちらの当事者も中止を選択しなかった場合に結果を返します。^[14]暗号の2者間計算プロトコルは、この理想的なプロトコルよりも悪くなく、追加の信頼の仮定がない場合、安全です。これは通常、シミュレータを使用してモデル化されます。シミュレータの役割は、理想的なプロトコルのラッパーとして動作し、暗号プロトコルのように見えるようにすることです。シミュレータの出力が暗号プロトコルの出力に統計的に近い、または計算上区別がつかない場合、情報理論的または計算的に制限された敵対者に対するシミュレーションは成功します。2者間計算プロトコルは、すべての敵対者に対して成功するシミュレータが存在する場合に安全です。

• 2PC における重要なプリミティブは、忘却転送です。
• 普遍的な構成可能性