（翻訳）安全な多者間計算からのゼロ知識証明

Yuval Ishai¹, Eyal Kushilevitz², Rafail Ostrovsky³, Amit Sahai⁴

この論文の予稿版は STOC 2007 で発表されました⁵。研究の一部は著者が IPAM を訪問中に行われたものです。

概要

ゼロ知識証明は、証明者が検証者に対し、ある主張が真実であるという事実以外の情報を一切明かすことなく、その主張を納得させることを可能にします。安全な多者間計算は、$n$人の相互に不信感を抱くプレイヤーが、破損した$t$人のプレイヤーに自身の入力に関する追加情報を一切明かすことなく、各自のローカルな入力に関する関数を共同で計算することを可能にします。

我々は、これら二つの基本的な概念の間に存在する新しい一般的な関連性を提示します。具体的には、NP 関係$R(x, w)$に対するゼロ知識証明の一般的な構成法を提案します。この構成法は、関連する多者間機能$f$に対する任意の安全なプロトコルをブラックボックスとして利用するのみです。後者のプロトコルは、少数の「正直だが好奇心旺盛な」プレイヤーに対して安全であることが要求されるだけです。また、多数の悪意あるプレイヤーに対する安全性を活用して効率を向上させることができる、基本構成の変種も提示します。

応用として、安全な多者間計算に関する過去の結果をゼロ知識の領域に変換し、効率的なゼロ知識証明に関する以前の構成を改善することができます。特に、長さ$m$の証拠に対する$R$の検証がサイズ$s$の回路$C$によって行える場合、一方向性関数の存在を仮定すると、以下のタイプのゼロ知識証明プロトコルが得られます：

• 証拠長への接近: $C$が$\wedge, \vee, \oplus, \neg$ゲート（ファンイン無制限）上で定数深さを持つ場合、通信複雑性が$m \cdot \text{poly}(k) \cdot \text{polylog}(s)$であるゼロ知識証明プロトコルが得られます。ここで$k$はセキュリティパラメータです。

• 「定数レート」ゼロ知識: サイズ$s$でファンインが限定された任意の回路$C$に対して、通信複雑性が$O(s) + \text{poly}(k, \log s)$であるゼロ知識プロトコルが得られます。したがって、大規模な回路では、通信複雑性と回路サイズの比率は定数に近づきます。これは、以前の最良のプロトコルが持つ$O(ks)$の複雑性を改善するものです。

キーワード: 暗号理論、ゼロ知識、安全な計算、ブラックボックスリダクション

1. はじめに

本研究では、暗号理論における最も基本的な二つのタスク、すなわちゼロ知識証明と安全な多者間計算との間に、新しい一般的な関連性を確立します。この関連性を説明し、その動機を述べる前に、文脈を理解するための関連背景を説明します。

ゼロ知識証明プロトコル⁶は、証明者が検証者に対し、ある言明の正当性を、その言明が真であるという事実以外の情報を一切明かすことなく納得させることを可能にします。より一般的な問題として、安全な多者間計算（MPC）^{7 8 9 10}があります。MPC プロトコルは、$n$人のプレイヤーが各自の入力のプライバシーを保ち、出力の正当性を維持しながら、入力に関する関数（「$n$者間機能」とも呼ばれる）を計算することを可能にします。より正確には、プロトコルは、最大$t$人のプレイヤーを汚染する可能性のある敵対者が、関数が外部の信頼できる第三者によって計算される理想的なプロトコルを攻撃することで達成できた以上のことを達成するのを防ぐべきです。特に、汚染されたプレイヤーは、関数の出力以外の残りの入力に関する追加情報を知るべきではありません。ゼロ知識プロトコルは、証明者が持つ証拠の正当性を検証する関数を持つ、安全な二者間計算の特殊なケースと見なすことができます。

正直者多数 vs. 不正直者多数: MPC プロトコルは二つのカテゴリに分類できます。一つは正直者多数の存在に依存するもの（すなわち、$t < n/2$と仮定する）^{9 10 11}であり、もう一つは正直者多数が存在しない場合でもセキュリティを提供できるもの^{7 8 12}です。正直者多数の場合、無条件に成立する「情報理論的」セキュリティを得ることが可能ですが、正直者多数でない場合は、暗号学的仮定の下で成立する計算量的セキュリティで妥協する必要があります。一方で、正直者多数の仮定はしばしば強すぎ、重要な二者間の場合には意味をなさないのです。

これら二つのタイプのプロトコルの構成は、用いる技術の種類が大きく異なります。第二のカテゴリのプロトコル（特にゼロ知識プロトコル）が第一のカテゴリのプロトコルの設計に有用であることが時折証明されてきましたが、その逆方向の応用は我々の知る限り存在しません。本研究は、正直者多数を持つ MPC の効率性と単純さ（および関連する膨大な研究）を、正直者多数が存在しない場合の効率的なプロトコル、特に効率的なゼロ知識プロトコルの設計に活用したいという希望に一部動機付けられています。

半正直 vs. 悪意のあるプレイヤー: もう一つの主要な区別は、プロトコルの指示に従うが、見たものから追加情報を得ようとするかもしれない半正直（「正直だが好奇心旺盛」とも）プレイヤーに対するセキュリティを提供する MPC プロトコルと、入力のプライバシーや出力の正当性を侵害するためにプロトコルの指示から任意に逸脱する可能性のある悪意のあるプレイヤーに対するセキュリティを提供するプロトコルとの間にあるものです。これら二つのタイプのプロトコルを、それぞれ半正直モデルで安全、悪意のあるモデルで安全と呼びます。半正直モデルでのセキュリティは、通常、悪意のあるモデルでのセキュリティよりもはるかに実現が容易です。注目すべきことに、Goldreich、Micali、Wigderson ^{13 8}の有名な結果は、半正直モデルで関数$f$を安全に計算する任意の MPC プロトコル$\Pi$を、悪意のあるモデルで$f$を安全に計算するプロトコル$\Pi'$にコンパイルする方法を示しています。「GMW パラダイム」として知られるこの高度な技術は、プレイヤーが送信するすべてのメッセージについて、そのメッセージがプロトコル$\Pi$の仕様と一致していることをゼロ知識証明で検証することを要求します。ゼロ知識証明を実装するために、コンパイラは$\Pi$をブラックボックスとして使用するのではなく、そのコード¹⁴を調べる必要があり、結果として得られるプロトコル$\Pi'$は、$\Pi$を実装する回路のすべてのゲートに対して複数の暗号操作を実行する必要があります。したがって、GMW パラダイムを適用すると、かなりの効率オーバーヘッドが発生する可能性があり、これは$\Pi$の計算複雑性が増すにつれて悪化します。本研究の第二の動機は、半正直モデルのセキュリティを悪意のあるモデルのセキュリティに向上させるための、代替的な「ブラックボックス」アプローチを見つけることです。

1.1 我々の貢献

我々は、NP 関係$R(x, w)$に対するゼロ知識証明システム$\Pi$の一般的な構成法を提案します。この構成法は、関連する多者間機能$f$に対する MPC プロトコル$\Pi_f$、およびビットコミットメントプロトコルをブラックボックス¹⁵として利用します。機能$f$は、$R$へのブラックボックス（オラクル）アクセスのみを用いて効率的に定義できます。

MPC プロトコル$\Pi_f$は、任意の数のプレイヤー$n$を関与させることができ、2 人の半正直プレイヤーに対して安全である必要があるだけです。特に、MPC プロトコルは正直者多数の存在下で安全である必要があるだけです。（我々の主要な構成では、$\Pi_f$が各プレイヤーペア間に理想的な Oblivious Transfer (OT) ^{16 17}チャネルを使用することを許容します。$\Pi_f$が OT チャネルを必要としない場合のために、$\Pi_f$が 1 人の半正直プレイヤーに対してのみ安全である必要がある構成の変種を提示します。）

我々の構成の基本的な変種は次のように進行します。$f(x, w_1, w_2, ..., w_n) = R(x, w_1 \oplus w_2 \oplus ... \oplus w_n)$と定義します。関数$f$は$n$者間機能と見なされ、$x$（NP 言明）は全$n$プレイヤーに知られており、$w_i$（証拠の$i$番目のシェア）はプレイヤー$i$の秘密入力です。$x$は$R$へのオラクルを用いて効率的に定義されることに注意してください。ゼロ知識プロトコル$\Pi_R$は、証明者が（自身のプライベートな作業テープ上で）証拠$w$を$n$個の加法的シェアに秘密分散することから始まります。$w = w_1 \oplus ... \oplus w_n$となるように、ランダムな$w_1, ..., w_n$を選びます。次に証明者は、$n$者間プロトコル$\Pi_f$を「頭の中で実行」し、言明$x$とシェア$w_1, ..., w_n$を$n$人のプレイヤーの入力として使用します。この実行が完了した後、証明者は検証者との対話を開始します。証明者は$n$人のプレイヤーそれぞれのビューにコミットし、検証者はランダムな異なるプレイヤーのペア$i, j$を選び、これらのプレイヤーのコミットされたビューを開くよう証明者に要求します。最後に、検証者は、開かれたビューが互いに（$\Pi_f$に関して）矛盾しておらず、これらのビューの出力が 1 である場合に受理します。（$\Pi_f$が OT チャネルを使用する場合、この一貫性チェックは各 OT チャネルの入力と出力にも適用されます。）

プロトコルのゼロ知識性は、$\Pi_f$が 2 人の半正直プレイヤーに対して安全であることから従います。$\Pi_f$が完全に正しいと仮定すると、健全性を侵害するには、不正な証明者が少なくとも 1 つの矛盾したビューのペアを生成する必要があり、これは少なくとも$1 / \binom{n}{2}$の確率で検出されます。$O(kn^2)$回の繰り返しを用いることで、健全性エラーを$2^{-k}$に減少させることができます。

我々の変換のブラックボックス性により、効率が大幅に向上する可能性が示唆されます。特に、結果として得られるゼロ知識プロトコルの通信複雑性は、それらが由来する MPC プロトコルの計算複雑性よりも小さくなり得ます。これは、通信複雑性が通常、関係$R$の計算複雑性よりもはるかに大きい、従来のゼロ知識証明（固定された NP 完全問題への Karp リダクションを介して得られる）とは対照的です。

繰り返しによる健全性増幅のコストを回避する、より効率的な構成の変種を得るために、我々はより多くの破損を許容し、検証者が一度に多くのビューを開くことを可能にする MPC プロトコルを採用します。この場合、半正直プレイヤーに対する$\Pi_f$のセキュリティでは不十分であり、$t$人の悪意のあるプレイヤーに対してある種の頑健性を持つ MPC プロトコルに依存する必要があります（ここで通常、$t$は健全性パラメータ$k$の定数倍、$n$は$t$の定数倍となります）。

この修正の背後にある直感は、検証者がプロトコルの単一の実行から、単なる 2 つのビューではなく、$t$個のビューを得られるようにすることです。$t$人の悪意のあるプレイヤーに対するセキュリティは、MPC プロトコル$\Pi_f$の正当性（またはゼロ知識プロトコルの健全性）を侵害するためには、ビュー間の不整合が「うまく分散」している必要があり、$t$個のランダムなビューを開くことで圧倒的な確率で不整合が明らかになることを保証します。$t$人の半正直プレイヤーに対するセキュリティではここでは不十分であることに注意してください。実際、この場合、単一の悪意のあるプレイヤーが他のすべてのプレイヤーに誤った出力を持たせることができます。もしこの特定のプレイヤーが検証者によって選ばれなければ、不整合は明らかにされず、それでも出力は誤っている可能性があります。一方、悪意のあるプレイヤーに対する完全なセキュリティは必要ありません。プロトコルが悪意のあるプレイヤーの存在下で正当であることが十分であり、そのプライバシーは以前と同様に半正直プレイヤーに対してのみ保持されればよいのです。

我々の応用に必要な基本構成のもう一つの拡張は、$\Pi_f$が無視できる確率で誤った出力を生成する可能性がある「統計的」なケースです。このケースは、単純な基本構成でさえ失敗させます。なぜなら、敵対者がビューを生成するために使用されるランダム性を偏らせることによって（しかし、それ以外はプロトコルに従って振る舞う）、不正を行うことを可能にするからです。我々は、標準的な暗号技術を用いてこの障害を克服する方法を示しますが、我々の構成の効率的なバージョンでは、これにはいくつかの追加の複雑さが伴います。

応用: 我々の一般的なアプローチの有用性を実証するために、MPC の効率に関する以前の結果をゼロ知識の領域に変換し、効率的なゼロ知識証明に関するいくつかの以前の構成を改善します。特に、長さ$m$の証拠$w$に対する$R(x, \cdot)$の検証がサイズ$s$の回路$C$によって行える場合、以下のタイプのゼロ知識証明プロトコルが得られます。

• シンプルなゼロ知識証明: 半正直モデル用の標準的な MPC プロトコル、例えば 2-private 3-player GMW プロトコル^{8 12}（OT チャネルに依存）や 1-private 3-player BGW プロトコル⁹を組み込むことで、複雑性$O(ks)$のシンプルなゼロ知識プロトコルが得られます。（ここで、また以下で$k$はセキュリティパラメータを示し、健全性エラーは最大$2^{-k}$です。）これらのプロトコルは、3-Colorability や Hamiltonicity に基づく古典的なゼロ知識プロトコルよりも効率的な代替手段を提供します。なぜなら、それらは回路表現に直接適用され、これらの NP 完全問題への Karp リダクションを必要としないからです。古典的なプロトコルとは対照的に、BGW プロトコルから派生したゼロ知識プロトコルは、算術計算をブール演算でエミュレートする必要なく、算術回路で定義された関係を証明するために効率的に拡張できます。

• 証拠長への接近: $C$が$\wedge, \vee, \oplus, \neg$ゲート（ファンイン無制限）上で定数深さを持つ場合、通信量が$m \cdot \text{poly}(k) \cdot \text{polylog}(s)$ビットのゼロ知識証明プロトコルが得られます。このプロトコルは一方向性関数を用いて実装できます⁹。あるいは、我々の技術は、前処理を伴う非対話モデルでゼロ知識証明システムを生成します。我々のプロトコルの複雑性は、Kalai と Raz ¹⁸による以前のプロトコルのそれと同等です。しかし、後者はゼロ知識論証システムのみを生成し、より強い仮定に依存しますが、セットアップの実装に必要な通信量は少ないです。上記で説明した我々のゼロ知識プロトコルは、¹⁴の MPC プロトコルに依存しており、その基本バージョンは BGW プロトコル⁹と^{19 20}の多項式表現技術を組み合わせたものです。我々が得るプロトコルは、基礎となる仮定（一方向性関数）と通信複雑性の両方の観点から、期待できるほぼ最良のものであることに注意してください。実際、非自明なゼロ知識証明の存在は、「非一様」一方向性関数の存在を意味し²¹、ゼロ知識証明（論証²²とは対照的に）のより低い通信複雑性は、SAT に対する驚くほど効率的な確率的アルゴリズムを意味するでしょう²³。

• 「定数レート」ゼロ知識: 一方向性関数が存在すると仮定すると、サイズ$s$でファンインが限定された任意の回路$C$に対して、通信複雑性が$O(s) + \text{poly}(k, \log s)$であるゼロ知識証明が得られます。したがって、大規模な回路では、通信複雑性と回路サイズの比率は定数に近づきます。これは、以前の最良のプロトコル（例：²⁴）が持つ$O(ks)$の複雑性を改善します。我々のゼロ知識プロトコルは、²⁵の MPC プロトコルに依存しており、代数幾何符号²⁶に基づく秘密分散を用いて定数サイズの体上で動作するように最適化されています。

展望: 我々の構成は、上記で議論した二つの動機付けとなる目標に直接関連しています。第一に、ゼロ知識と MPC の間に新しい一般的な関連性を確立し、これにより特に、正直者多数を持つ MPC に関する膨大な研究をゼロ知識証明の設計に活用できます。後者は、ひいては、一般的な安全な二者間プロトコルや正直者多数のいない MPC の設計に使用できます。この新しい関連性はまた、ゼロ知識証明の効率に関するいくつかの未解決問題と、MPC の分野における同様の未解決問題との間の関連性も確立します。例えば、すべての回路が入力サイズの（例えば）2 乗に依存する通信複雑性で安全に評価できるならば、すべての NP 関係は、証拠サイズのほぼ 2 乗の通信複雑性を持つゼロ知識証明を持つことになります。

第二に、我々の構成は、半正直モデルでのセキュリティをブラックボックス的に悪意のあるモデルでのセキュリティに向上させることができる有用な応用クラスを示します。一般に、半正直モデルで関数$F$を安全に計算するプロトコル$\Pi$をブラックボックス的に使用して、悪意のあるモデルで関数$R$を安全に計算するプロトコル$\Pi'$を直接構成することは不可能であることに注意するのは有益です。例えば、$R$がゼロ知識機能である場合、半正直モデルでは、証明者が単に検証者に入力$(x, w)$に対する$R$の出力を送信する自明なプロトコル$\Pi$を考えることができます。明らかに、$\Pi$は一般に$\Pi'$の構成には役に立ちません。$R$を関連する多者間機能$f$に変更することで、この不可能性を回避します²⁷。

1.2 関連研究

ブラックボックスリダクション: Impagliazzo と Rudich ²⁸の独創的な論文に始まり、暗号理論におけるブラックボックスリダクションの可能性と不可能性の境界線を描こうとする豊富な研究があります。特に、様々な暗号プリミティブからの MPC プロトコルのブラックボックス構成が以前に提案されています^{29 30 31 32 33 34}。我々の研究は、基礎となる暗号プリミティブをブラックボックスとして扱うだけでなく、実現されるべき機能もブラックボックスとして扱う点で、これらすべての研究とは異なります。対照的に、以前の構成は、固定された機能のケースを扱うか、あるいは機能の非ブラックボックス的な使用を行うかのいずれかでした。

ゼロ知識の効率: 対話的および非対話的ゼロ知識証明の効率を改善するための膨大な研究があります。例えば、^{35 24 36 37 38 39 40 18}およびその中の参考文献を参照してください。この文脈で注意すべき重要な点は、計算量的健全性で妥協することにより、多項式対数的な通信複雑性を持つ、漸近的に非常に効率的なゼロ知識論証システムを得ることができるということです。これらの論証システムは、対話的で衝突困難なハッシュ関数に基づくもの²²か、ランダムオラクルモデルで非対話的なもの⁴¹のいずれかです。我々が論証ではなく証明に焦点を当てるのは、理論的および実践的な観点の両方から動機付けられています。理論的な観点からは、より弱い仮定の下でより強い健全性の概念を得ます。より実践的な観点からは、^{22 41}のような PCP ベースの論証の構成は、まだ実際には効率的であるとは言い難いです。最後に、我々の結果は、半正直プレイヤーに対するセキュリティをブラックボックス的に悪意のあるプレイヤーに対するセキュリティに向上させるという一般的な目標によって独立に動機付けられています。この動機は、証明と論証の両方に当てはまります。

構成: 第 2 節では、いくつかの準備を述べます。半正直モデルにおける MPC からのゼロ知識プロトコルの基本構成は第 3 節で説明され、通信複雑性が証拠長に近いゼロ知識プロトコルへの応用（第 3.2 節）も含まれます。第 4 節では、悪意のあるモデルにおける MPC からのゼロ知識プロトコルの構成を提示します。これらは、第 4.4 節で提示される定数レートのゼロ知識への応用によって動機付けられています。第 5 節でいくつかの最終的な所見をもって締めくくります。

2. 準備

このセクションでは、ゼロ知識証明と MPC プロトコルの概念を定義します。

区別不能性: 関数$\epsilon(\cdot)$は、任意の多項式の逆数よりも漸近的に小さい場合、無視できる（negligible）といいます。つまり、すべての定数$c > 0$と十分に大きいすべての$n$に対して、$\epsilon(n) < 1/n^c$が成り立ちます。$1 - \epsilon$が無視できる場合、$\epsilon(\cdot)$は圧倒的（overwhelming）であるといいます。$X \subseteq \{0,1\}^*$を無限の文字列集合とします。二つの分布アンサンブル$\{A_x\}_{x \in X}$と$\{B_x\}_{x \in X}$は、すべての効率的な非一様識別器$D$に対して、すべての$x \in X$に対して$| \Pr[D(A_x) = 1] - \Pr[D(B_x) = 1] | \le \epsilon(|x|)$となるような無視できる関数$\epsilon(\cdot)$が存在する場合、計算量的に区別不能であると言われます。

2.1 ゼロ知識（ZK）

我々は、文献^{6 13 42}からのゼロ知識証明の標準的な概念を使用し、正直な証明者が効率的であるべき場合に適合させます。

NP 関係$R(x, w)$は、効率的に決定可能な二項関係であり、多項式的に有界です。つまり、$R(x, w)$が満たされるならば$|w| < p(|x|)$となるような多項式$p(\cdot)$が存在します。我々は自然に$R$を 0 または 1 を出力するブール関数と見なします。任意の NP 関係$R$は NP 言語$L = \{x: \exists w, R(x,w) = 1\}$を定義することに注意してください。

NP 関係$R(x, w)$に対するゼロ知識証明プロトコルは、二つの PPT 対話アルゴリズム、証明者$P$と検証者$V$によって定義されます。最初に、証明者は NP 言明$x$と対応する証拠$w$を与えられ、検証者は言明$x$のみを与えられます。証明者と検証者は、それぞれのアルゴリズムによって定義された次メッセージ関数を使用して対話します。この関数は、入力、これまでに受信したメッセージ、および対応するパーティのコイントスに基づいて、次に送信するメッセージを決定します。

定義 2.1（ゼロ知識証明） プロトコル$(P,V)$は、以下の要件を満たす場合、関係$R$に対するゼロ知識証明プロトコルです：

• 完全性: $R(x, w) = 1$であり、両プレイヤーが正直である（すなわち、プロトコルに従って送信するメッセージを計算する）場合、検証者は常に受理します。

• 健全性: すべての悪意のある計算量的に無制限な証明者$P^*$に対して、x が偽の言明である（すなわち、すべての$w$に対して$R(x,w) = 0$である）場合、$P^*$と$V$の入力$x$に関する対話は、最大で$\epsilon(|x|)$の確率を除いて$V$を拒否させるような、無視できる関数$\epsilon(\cdot)$が存在します。

• ゼロ知識: 任意の悪意のある PPT 検証者$V^*$に対して、PPT シミュレータ$M^*$が存在し、$R(x,w) = 1$となる入力$(x,w)$で$P$と対話するときの$V^*$のビューは、$M^*(x)$の出力分布と計算量的に区別不能です。すなわち、無視できる関数$\delta(\cdot)$が存在し、すべての効率的な非一様識別器$D$と、$(x,w) \in R$となるすべての$x, w$に対して、

  $$| \Pr[D(\text{View}_{V^*}(x, w)) = 1] - \Pr[D(M^*(x)) = 1]| < \delta(|x|)$$

  が成り立ちます。ここで$\text{View}_{V^*}$は、$V^*$のビューを表し、その入力$x$、コイントス、および受信メッセージから構成されます。

我々は時々、完全性の要件を緩和し、無視できるエラー確率を許容します。最後に、無視できない（通常は定数）健全性エラー$e$を持つゼロ知識プロトコルも考慮します。そのような場合、健全性エラーが指定されます。

簡単のため、我々はゼロ知識プロトコルのより強い知識の証明特性（[16]参照）を考慮しません。しかし、我々の一般的な構成は、この特性も満たすことが示せます。

明示的なセキュリティパラメータの使用: 上記のゼロ知識証明の標準的な定義は、言明$x$の長さを暗黙的にセキュリティパラメータとして扱い、不正直なパーティ（証明者または検証者）の有利さが$|x|$において無視できることを要求することに注意してください。これは実現可能性の結果を確立するには便利ですが、暗号プロトコルの具体的な効率を研究する際には、すべてのアルゴリズムに追加の入力として与えられる別のセキュリティパラメータ$k$を導入すると便利です。そのような場合、定義 2.1 の健全性とゼロ知識の要件を、$\epsilon(|x|)$と$\delta(|x|)$をそれぞれ$\epsilon(k)$と$\delta(k)$に置き換えることで修正します。さらに、ゼロ知識の要件では、$V^*$と$D$の実行時間を$k$の多項式に制限します。後者の定義を満たすゼロ知識プロトコルは、$k = |x|^c$（$c > 0$は任意に小さい定数でよい）とすることで、元の定義を満たすゼロ知識プロトコルに変換できます³⁵。したがって、$k$は入力長よりも漸近的にずっと小さいと考えることができます。

2.2 理想化されたプリミティブ

我々のゼロ知識プロトコルを記述する際、ビットコミットメントやコイントスのようなプリミティブの理想化されたバージョンが利用可能なハイブリッドモデルで、それらを最初に記述し分析すると便利です。その後、理想プリミティブの呼び出しを（一方向性関数のブラックボックス使用のみで）インスタンス化して、プレーンモデルでプロトコルを得る方法を明示的に記述します。このようなモジュラー設計アプローチは、MPC の分野では一般的です（^{43 12}参照）。しかし、我々は計算量的に健全な論証ではなく、無条件に健全な証明を扱っているため、最終的なプロトコルのセキュリティを推論するために既製の合成定理を適用することはできず、各ケースを個別に論じる必要があります。

ゼロ知識証明のモジュラー設計のための一般的なツールが不足しているにもかかわらず、理想プリミティブをインスタンス化して得られるゼロ知識プロトコルの分析は、ハイブリッドモデルにおける我々のプロトコルの分析と、文献からの以前のゼロ知識プロトコルの分析を、かなり直接的な方法で組み合わせていることに注意してください。したがって、本研究の主な貢献は、ハイブリッドモデル内で最もよく見なされるかもしれません。

2.3 安全な多者間計算（MPC）

我々は、文献^{43 42}からの MPC の標準的な定義を使用します。我々の基本モデルは、安全なポイントツーポイントチャネルを介した同期通信を仮定します。（一部のプロトコルは、OT チャネル、ブロードキャストプリミティブ、または理想的なコイントスのような他の理想プリミティブにも依存します。これらは使用されるときに説明されます。）

$n$をプレイヤーの数とし、$P_1, ..., P_n$で表します。すべてのプレイヤーは公開入力$x$を共有し、各プレイヤー$P_i$はローカルな秘密入力$w_i$を持ちます。我々は、$n$者間機能$f$を安全に実現するプロトコルを考えます。ここで$f$は、入力$(x, w_1, ..., w_n)$を$n$個の出力のタプルにマッピングします。（単一の出力のみが指定されている場合、この出力はすべてのプレイヤーに与えられると仮定されます。）

プロトコル$\Pi$は、その次メッセージ関数を介して指定されます。すなわち、$\Pi(i, x, w_i, r_i, (m_1, ..., m_{\tau}))$は、公開入力$x$、ローカル入力$w_i$、ランダム入力$r_i$、および最初の$\tau$ラウンドで受信したメッセージ$m_1, ..., m_{\tau}$が与えられた場合に、ラウンド$\tau+1$で$P_i$によって送信される$n$個のメッセージ（および、場合によってはブロードキャストメッセージ）のセットを返します。統計的または計算量的セキュリティの場合、$\Pi$は追加の入力としてセキュリティパラメータ$k$を受け取ります。$\Pi$の出力は、プロトコルが終了すべきであることを示すこともあり、その場合、$\Pi$は$P_i$のローカルな出力を返します。$P_i$のビューは$V_i$で示され、$w_i$、$r_i$、および$\Pi$の実行中に$P_i$が受信したメッセージを含みます。汚染されていないプレイヤー$P_i$によって送信されたメッセージおよびそのローカルな出力は、$V_i$と$x$から$\Pi$を呼び出すことによって推測できることに注意してください。ビュー間の一貫性に関する以下の自然な概念を定義すると便利です。

定義 2.2（一貫性のあるビュー） ビューのペア$V_i, V_j$は、（プロトコル$\Pi$といくつかの公開入力$x$に関して）$V_i, x$に暗黙的に含まれる送信メッセージが$V_j$で報告された受信メッセージと同一であり、その逆も同様である場合、一貫性があると言われます。

以下の単純な補題は、$n$個のビューのタプルが、すべてのビューのペアが一貫している場合に限り、$\Pi$のある正直な実行に対応することを主張します。

補題 2.3（ローカル vs. グローバルな一貫性） $\Pi$を上記の$n$者間プロトコル、$x$を公開入力とします。$V_1, ..., V_n$を$n$個の（おそらく不正確な）ビューのタプルとします。そのとき、すべてのビューのペア$V_i, V_j$が$\Pi$と$x$に関して一貫しているのは、公開入力$x$（および秘密入力$w_i$とランダム入力$r_i$のいくつかの選択）を持つ$\Pi$の正直な実行が存在し、その中で$V_i$がすべての$1 \le i \le n$に対して$P_i$のビューである場合に限ります。

証明: 「if」方向は定義から直接従います。「only if」方向については、$V_1, ..., V_n$をペアワイズで一貫性のあるビューとし、$w_i, r_i$をビュー$V_i$で報告された入力とランダム入力とします。ビューのペアワイズの一貫性は、ラウンド数$d$に関する帰納法により、$\Pi$が$(x, (w_1, r_1), ..., (w_n, r_n))$で呼び出されたときの$d$ラウンド後のすべてのプレイヤー$P_i$の実際のビューが、$V_i$で報告された最初の$d$ラウンドの$P_i$のビューと同じであることを意味します。したがって、$n$個のビュー$V_1, ..., V_n$は、要求通り、$\Pi$の完全な実行と一貫しています。□

我々は、「半正直」モデルと「悪意のある」モデルの両方でプロトコルのセキュリティを考えます。半正直モデルでは、セキュリティ要件を以下の正当性とプライバシーの要件に分解することができます。

定義 2.4（正当性） $\Pi$が決定論的な$n$者間機能$f(x, w_1, ..., w_n)$を完全な（または、統計的な）正当性で実現するとは、すべての入力$x, w_1, ..., w_n$に対して、あるプレイヤーの出力が$f$の出力と異なる確率が$0$（または、$k$において無視できる）である場合を言います。ここで確率は、ランダム入力$r_1, ..., r_n$の独立した選択にわたります。

定義 2.5（$t$-プライバシー） $1 \le t < n$とします。$\Pi$が完全な$t$-プライバシーで$f$を実現するとは、PPT シミュレータ SIM が存在し、任意の入力$x, w_1, ..., w_n$と、$|T| \le t$となる汚染されたプレイヤーの任意の集合$T \subseteq \{1, ..., n\}$に対して、$T$のプレイヤーの共同ビュー$\text{View}_T(x, w_1, ..., w_n)$が$\text{SIM}(T, x, (w_i)_{i \in T}, f_T(x, w_1, ..., w_n))$と同一に分布する場合を言います。統計的または計算量的プライバシーへの緩和は自然な方法で定義されます。すなわち、統計的（または、計算量的）な場合、すべての識別器$D$（または、回路サイズが$\text{poly}(k)$の$D$）に対して、無視できる関数$\delta(\cdot)$が存在し、

$$| \Pr[D(\text{View}_T(k, x, w_1, ..., w_n)) = 1] - \Pr[D(\text{SIM}(k, T, x, (w_i)_{i \in T}, f_T(x, w_1, ..., w_n))) = 1]| < \delta(k)$$

が成り立つことを要求します。

悪意のあるモデルでは、汚染されたプレイヤーが任意に振る舞う可能性があるため、セキュリティを上記のように正当性とプライバシーに一般的に分解することはできません。しかし、我々の目的のためには、プロトコルが標準的な一般定義によって暗示される、悪意のあるモデルにおけるより弱いセキュリティ概念を満たすだけで十分です。具体的には、$\Pi$が上記で定義されたように$t$-private であり、さらに悪意のあるモデルにおける以下の正当性の概念を満たすことが十分です。

定義 2.6（$t$-頑健性） $\Pi$が完全な（または、統計的な）$t$-頑健性で$f$を実現するとは、定義2.4のように半正直な敵対者の存在下で完全（または、統計的）に正当であり、さらに、最大$t$人のプレイヤーの集合$T$を汚染する任意の計算量的に無制限な悪意のある敵対者に対して、および任意の入力$(x, w_1, ..., w_n)$に対して、以下の頑健性特性が成り立つ場合を言います。$f(x, w'\_1, ..., w'\_n) = \perp$となるような$(w'\_1, ..., w'\_n)$が存在しない場合、正直なプレイヤーの入力が$(x, w_1, ..., w_n)$と一致する$\Pi$の実行において、汚染されていないプレイヤーが1を出力する確率は$0$（または、$k$において無視できる）です。

最後に、我々は適応的な敵対者に対する頑健性も考慮します。この敵対者は、これまでに見たプレイヤーのビューに基づいて、汚染されたプレイヤーの集合$T$を動的に選択することが許されます（ただし、汚染されたプレイヤーの総数が$t$を超えない限り）。定義 2.6 は、適応的な敵対者の場合に自然に拡張できます。（そのような定義のインスタンスは後で正式に定義されます。）デフォルトでは、我々は上記で定義された非適応的な頑健性の概念を考えます。

3. 半正直モデルにおける MPC からのゼロ知識証明

このセクションでは、半正直モデルにおける MPC プロトコルに依存する、我々の基本的なゼロ知識プロトコルの構成を提示します。

$L$を NP の言語とし、$R(x, w)$を対応する NP 関係とします。$f$を、$R$に対応する以下の$(n+1)$引数関数（$n \ge 3$）とします： $f(x, w_1, ..., w_n) = R(x, w_1 \oplus ... \oplus w_n)$ ここで$\oplus$は文字列のビットごとの排他的論理和（すべて同じ長さ）を表します。我々は$f$を$n$者間機能と見なし、最初の引数$x$は全$n$プレイヤーに知られている公開入力、$w_i$はプレイヤー$P_i$の秘密入力、出力は全プレイヤーが受け取ります。我々は時々、公開入力$x$を無視し、$f$を$x$によって指定される$n$引数関数と見なします。

$\Pi_f$を、完全な正当性と、完全、統計的、または計算量的な 2-プライバシー（半正直モデルで）で$f$を実現する$n$者間プロトコルとします。我々は今、NP 関係$R$に対するゼロ知識プロトコル$\Pi_R$を記述します。証明者と検証者は両方とも入力$x$（$L$のインスタンス）を与えられます。証明者は証拠$w$も与えられ、両者は MPC プロトコル$\Pi_f$へのブラックボックスアクセスを持ちます。ゼロ知識プロトコルは、統計的に拘束力のあるコミットメントプロトコル Com ⁴⁴も利用します。これは、任意の一方向性関数^{45 42}に基づいて構築できます。

我々は、Com の理想化された実装を用いて$\Pi_R$を記述し分析することから始めます。この実装では、文字列は信頼できる第三者に秘密裏に送信することでコミットでき、後でコミッターが信頼できる第三者にコミットされた文字列を明かすよう指示することで開く（または「デコミットする」）ことができます。（コミッターがコミットメントを開くことを拒否できるが、その事実はコミットされた文字列の指定された受信者に知られることに注意してください。）あるいは、コミットされた文字列がロックされた箱で送られ、デコミットが箱を開けるための鍵を送ることで行われる直接的な物理的実装を考えることもできます。このような理想的なコミットメントプリミティブを使用するプロトコルを、コミットメントハイブリッドモデルのプロトコルと呼びます。

コミットメントハイブリッドモデルにおける$\Pi_R$の実装は、我々の主な貢献と見なすことができます。後で、理想的なコミットメントプリミティブを実際の暗号コミットメントプロトコルでインスタンス化する際に必要となる分析の（標準的な）修正について説明します。プロトコルを図 1 に示します。

図 1: コミットメントハイブリッドモデルにおける ZK プロトコル$\Pi_R$

1. 証明者は、排他的論理和が証拠$w$に等しくなるような$w_1, ..., w_n \in \{0,1\}^l$をランダムに選びます。彼女は入力$(x, w_1, ..., w_n)$に対する$\Pi_f$の実行を「頭の中で」エミュレートします（これには$n$人のプレイヤーのランダム性を選択し、プロトコルを実行することが含まれます）。この実行に基づき、証明者は$n$人のプレイヤーのビュー$V_1, ..., V_n$を準備し、これらの$n$個のビューそれぞれに個別にコミットします。
2. 検証者は、ランダムに異なるプレイヤーインデックス$i, j \in [n]$を選び、それらを証明者に送信します。
3. 証明者は、2 つのビュー$V_i, V_j$に対応するコミットメントを「開きます」。
4. 検証者は、以下の場合に限り受理します： (a) 証明者が要求された 2 つのビューを実際に正常に開いた。 (b) $P_i$と$P_j$の両方の出力（それらのビューによって決定される）が 1 である。 (c) 開かれた 2 つのビューが互いに一貫している（$x$と$\Pi_f$に関して、定義 2.2 参照）。

定理 3.1 $n \ge 3$とし、$R, f$を上記のとおりとします。$\Pi_f$が$n$者間機能$f$を完全な正当性と、完全、統計的、または計算量的な 2-プライバシー（半正直モデルで）で実現すると仮定します。そのとき、図 1 で説明された$\Pi_R$は、コミットメントハイブリッドモデルにおける NP 関係$R$に対するゼロ知識証明プロトコルであり、健全性エラー$\epsilon < 1 - 1 / \binom{n}{2}$です。

証明: 完全性、健全性、ゼロ知識を個別に論じます。

• 完全性: $(x, w) \in R$であり、証明者が正直である場合、$w_1 \oplus ... \oplus w_n = w$であり、$\Pi_f$は完全に正しいため、ビュー$V_1, ..., V_n$は常に出力 1 を持ちます。これらのビューはプロトコルの正直な実行によって生成されるため、常に互いに一貫しています。

• 健全性: すべての$w$に対して$R(x,w) = 0$であると仮定します。したがって、$\Pi_f$の完全な正当性により、$w_1, ..., w_n$のすべての選択と、ランダム入力$r_1, ..., r_n$のすべての選択に対して、プロトコルの正直な実行における全$n$プレイヤーの出力は 0 でなければなりません。したがって、ステップ 1 で証明者によってコミットされた$n$個のビューを考えると、すべてのビューで出力が 0 であるか、または補題 2.3 により、$x$と$\Pi_f$に関して矛盾する 2 つのビューが存在します。前者の場合、検証者は常に拒否し、後者の場合、彼は少なくとも$1 / \binom{n}{2}$の確率で拒否します。これは、彼が矛盾するペア$i, j$を選択する確率です。

• ゼロ知識: $V^*$を悪意のある検証者とします。$V^*$と MPC シミュレータ SIM の両方をブラックボックスとして呼び出す、$V^*$のビューのためのシミュレータ$M^*$を記述します。$\Pi_f$が完全に 2-private である場合から始めます。シミュレータ$M^*$は入力$x$に対して次のように動作します：

  1. 入力$x$で$V^*$を実行します。$i, j$を$\Pi_R$のステップ 2 で$V^*$によって送信されたインデックスのペアとします。
  2. $M^*$は、$\Pi_R$のステップ 3 で（正直な）証明者から受信した 2 つのビュー$V_i, V_j$を、ランダムな$w_i, w_j$を選び、$\text{SIM}(T = \{i,j\}, x, (w_i, w_j), 1)$を実行することでシミュレートします。

  （コミットメントハイブリッドモデルでは、ステップ 1 の証明者のコミットメントは自明にシミュレートできることに注意してください。）上記のシミュレーションが完全であることを論じます。$R(x,w) = 1$となる任意の$(x, w)$を固定します。シミュレータによって選ばれた$V^*$のランダム性は、$\Pi_R$の実際の実行における$V^*$のランダム性と同一に分布しています。したがって、そのようなランダム性$r_{V^*}$のすべての選択に対して条件付けられた場合にシミュレーションが完全であることを証明すれば十分です。$r_{V^*}$によって決定される検証者の選択を$i, j$とします。$(x, w)$に対する$\Pi_R$の実際の実行では、$\Pi_f$への入力$w_1, ..., w_n$（正直な証明者によって選ばれる）は、$w_i$と$w_j$が均一で独立であるようになっています。したがって、$r_{V^*}$に条件付けられると、$M^*$による$w_i, w_j$の選択は、$(x, w)$に対する$\Pi_f$の実行における証明者による$w_i, w_j$の選択と同一に分布しています。残るは、$r_{V^*}, w_i, w_j$の各可能な選択に条件付けられた場合に、$\Pi_R$のステップ 3 で証明者から受信したビュー$(V_i, V_j)$の分布が、$\text{SIM}(\{i,j\}, x, (w_i, w_j), 1)$の分布と同一であることを示すことです。実際、SIM が$\Pi_f$の完全な 2-private シミュレータであるという事実は、$w_i, w_j, w$と一致する$w_1, ..., w_n$のすべての可能な選択にさらに条件付けられた場合でも、後者が成り立つことを保証します。

  最後に、$\Pi_f$が統計的または計算量的にのみ 2-private である場合、シミュレーションの質もそれに応じて変化します。（これらの場合、シミュレータは追加の入力としてセキュリティパラメータ$k$を受け取り、それを$V^*$と SIM に渡します。）前の証明からの唯一の変更は最終ステップにあります：$w_i, w_j, w$と一致する$w_1, ..., w_n$のすべての選択にさらに条件付けられた場合、$\Pi_R$における$(V_i, V_j)$の分布は、今や$\text{SIM}(k, \{i,j\}, x, (w_i, w_j), 1)$の出力に統計的または計算量的に近いだけです。標準的な平均化の議論により、これは$M^*$の最終的な出力が$V^*$のビューに統計的または計算量的に近いことを意味します。□

上記のプロトコルにおける理想的なコミットメントプリミティブは、任意の統計的に拘束力のあるコミットメントプロトコルでインスタンス化できます。正式な定義については⁴²を参照してください。そのようなコミットメントプロトコルは、任意の一方向性関数^{45 44}に（ブラックボックス的に）基づくことができます。

Com を（完全に拘束力があり、計算量的に秘匿性のある）コミットメントプロトコルとし、$\Pi_{R,Com}$を、理想的なコミットメント（またはデコミットメント）の各呼び出しを、セキュリティパラメータ$k$を持つ Com の対応する呼び出しを用いて自然な方法で実装することによって$\Pi_R$から得られるプロトコルとします。そのとき、以下が成り立ちます：

定理 3.2 $n \ge 3$とし、$R, f$を定理 3.1 のとおりとします。$\Pi_f$が$n$者間機能$f$を完全な正当性と、完全、統計的、または計算量的な 2-プライバシー（半正直モデルで）で実現すると仮定します。Com を任意の統計的に拘束力のあるコミットメントプロトコルとします。そのとき、上記で説明された$\Pi_{R,Com}$は、NP 関係$R$に対するゼロ知識証明プロトコルであり、健全性エラー$\epsilon(k) < 1 - 1 / \binom{n}{2} + \delta(k)$です。ここで$\delta(\cdot)$はいくつかの無視できる関数です。さらに、$\Pi_{R,Com}$の$kn^2$回の逐次的な繰り返しから得られるプロトコルは、健全性エラー$2^{-k(k)}$を持つゼロ知識証明です。

Com が一方向性関数へのブラックボックスリダクションを用いて実装される場合、$\Pi_{R,Com}$の実装（およびそのセキュリティリダクション）は、$\Pi_f$と一方向性関数のブラックボックス使用のみを行うことに注意してください。

証明: $\Pi\_{R,Com}$の分析は、3-Colorability に対する古典的な GMW ゼロ知識証明¹³の分析を密接に模倣します。自己完結性のためにここで詳細を提供します。

$\Pi_{R,Com}$の完全性は、$\Pi_R$の完全性と、正直な証明者によるデコミットメントが正直な検証者によって常に受理されるという事実から従います。

健全性: Com の統計的拘束特性は、Com の各呼び出しがコミットされた文字列を定義し、検証者のコインに関する無視できる確率を除いて、この文字列のみが後でデコミットできることを保証します。したがって、$\Pi_{R,Com}$の健全性エラーは、$\Pi_R$のそれよりも最大で無視できる量（すなわち、証明者がいずれかのコミットメントの拘束性を破る確率）だけ大きくなります。

ゼロ知識: GMW プロトコルと同様に、$\Pi_{R,Com}$のゼロ知識特性の証明に重要な特徴は、検証者がプロトコルで行える選択が多項式個しかないことです。そのため、シミュレータ$M^*$は次のように動作します：

1. シミュレータは、成功するまで以下の$l = n^2k$回の「試行」を行います。シミュレータがすべての試行で失敗した場合、中止します。
2. シミュレータはまず、異なるパーティのペア$\{i, j\}$と入力$w_i, w_j$をランダムに選び、MPC シミュレータ$\text{SIM}(k, \{i,j\}, x, (w_i, w_j), 1)$を呼び出して、これらのパーティのシミュレートされたビュー$V_i$と$V_j$を取得します。すべての$h \notin \{i,j\}$に対して、シミュレータはランダムなビュー$V_h$を準備します。
3. 各ビュー$V_h$に対して、シミュレータは検証者アルゴリズムでコミットメントプロトコルを実行します。
4. 検証者がチャレンジ$\{i,j\}$で応答した場合、「試行」は成功したと言い、そうでなければ試行は失敗し、やり直します。試行が成功した場合、シミュレータは$V_i$と$V_j$を検証者に開き、成功した対話から得られる検証者のビューを出力します。

明らかに、各シミュレーション試行は少なくとも$1/n^2$の独立した確率で成功します。したがって、シミュレータは少なくとも$1 - 2^{-k(k)}$の確率で少なくとも一度は成功します。

シミュレーションの計算量的区別不能性は、以下の標準的なハイブリッド論法から従います（このハイブリッド論法のより詳細な説明については、3-Colorability に対する GMW ゼロ知識プロトコルの文脈で^{13 42}を参照してください）。

• ハイブリッド $A_1, ..., A_l$: シミュレータが証拠を与えられる一連のハイブリッド実験を考えます。実験$A_i$では、最初の$i$回の「試行」で、MPC シミュレータを適用する代わりに、正直な証明者が行うように振る舞い、MPC プロトコルの正直な実行に従ってすべてのビュー$\{V_j\}$を準備します。しかし、その後、パーティのペア$\{i,j\}$をランダムに選び、$h \notin \{i,j\}$であるすべての$V_h$をランダムなビューに置き換え、最後のステップでシミュレータが行うように続けます。（残りの$l - i$回の試行は上記のシミュレータに従います。）ハイブリッド$A_1$とシミュレータの出力を区別できる攻撃者は、直ちに MPC シミュレータの識別器をもたらします。同様に、各$A_i$は同じ理由で$A_{i+1}$と区別不能です。

• ハイブリッド B: ここで、ハイブリッド B を考えます。これはハイブリッド$A_l$と同一ですが、今やすべてのビュー$\{V_j\}$は（正直な証明者が行うように）MPC プロトコルの正直な実行から生成されたままであるとします。ハイブリッド$A_l$では、これらのビューの一部（コミットされたが決して開かれないもの）はランダムなビューであったことを思い出してください。コミットメントの区別不能性により、ハイブリッド$A_l$はハイブリッド B と区別不能です。

ハイブリッド B と、$\Pi_{R,Com}$における証明者と検証者の実世界の対話との唯一の違いは、ハイブリッド B が（何度も独立して）検証者の$i$と$j$の選択を事前に推測しようとすることです。独立性により、ハイブリッド B は$1 - 2^{-\Omega(k)}$の確率で成功します。したがって、ハイブリッド B は、証明者と検証者の間の実生活の対話から統計的距離$2^{-\Omega(k)}$以内にあり、これでゼロ知識特性の証明は完了します。

上記のシミュレータは悪意のある検証者をブラックボックス的に使用するため、定理の第二部は一般的な逐次合成定理（¹²参照）によって暗示されます。□

追加の注記:

1. $\Pi_f$が完全に正しくない場合、不正な証明者は$\Pi_R$の健全性を侵害する可能性があります：$x \notin L$に対して、彼女はプロトコルが誤って 1 を出力するような$w_1, ..., w_n$と$r_1, ..., r_n$を選び、それによって検証者を誤って受理させる（彼がどのインデックス$i, j$を選んでも）。不完全な正当性の問題については、以下の 3.1 節で扱います。
2. 上記のプロトコルは証明者に最大 2 つのビューを開くことしか要求しないため、証拠$w$を$n$人全員ではなく、$n$人のうち 3 人のプレイヤー間で共有すれば十分です。
3. 後でゼロ知識プロトコルの通信量を最小化することに関心があります。この基本構成の通信複雑性を（簡単に）分析することは有益です。$\Pi_R$における通信は、主に$\Pi_f$におけるビューへのコミットメントから構成されます。長さ$l$の文字列$m$への統計的に拘束力のあるコミットメントを実装するには、$l + \text{poly}(k)$ビットの通信コストがかかります。ここで$k$はセキュリティパラメータです。これは、まず擬似乱数生成器$G$へのランダムなシード$s \in \{0,1\}^k$にコミットし、次に$m \oplus G(s)$を送信することで実現できます。$\Pi_R$におけるビューの全長は、$O(|w|)$に$\Pi_f$の通信およびランダム性複雑性を加えたものに等しいことに注意してください。
4. $\Pi_R$の記述と分析は、より強力な通信チャネルを使用するプロトコル$\Pi_f$に対応するように容易に拡張できます。例えば、各プレイヤーペアが任意の 2 者間機能へのオラクルアクセスを持つと仮定できます。この機能では、両プレイヤーが入力と出力を送受信します。一貫性のあるビューの概念は、この場合に自然に拡張できます。すなわち、検証者は、オラクルからの報告された出力がその入力と一貫していることを確認できます。（2-プライバシー要件のため、そのようなオラクルが$\Pi_f$の設計を自明にしないことに注意してください。）特に、各プレイヤーペアが OT チャネル^{16 17}を介して接続されていると仮定できます。このチャネルでは、送信者は 2 つの入力$s_0, s_1$を持ち、受信者は選択ビット$b$を持ち、受信者は$s_b$を得ます。$\Pi_R$を、$\Pi_f$がブロードキャストチャネルを使用する場合に拡張することも容易です。単に証明者が検証者にすべてのブロードキャストメッセージを送信させるだけでよいのです³⁹。
5. このプロトコル、および以下のほとんどのプロトコルは、実際にはアーサー・マーリンプロトコルです（すなわち、検証者が証明者に公開ランダムコインを送信することのみを要求します）。

1-private MPC に基づくゼロ知識: ここで、任意の 1-private（2-private ではなく）MPC プロトコル$\Pi_f$を使用できる、基本ゼロ知識プロトコル$\Pi_R$の修正版を記述します。$n$個のビュー$V_i$にコミットすることに加えて、証明者は$\binom{n}{2}$個の通信チャネルそれぞれで通信されたメッセージにコミットします。検証者は今、ランダムなプレイヤー$P_i$のビュー$V_i$を、$P_i$に付随する$n-1$個のチャネルすべてと共に開くよう証明者に要求します。ゼロ知識特性は、検証者に明かされる情報が単一のプレイヤー$P_i$のビューによって暗示されるという事実から従います。健全性エラーは最大$1 - 1/n$です：補題 2.3 と同様に、プロトコルの無効な実行は、ローカルビューと付随するチャネルとの間に少なくとも 1 つの不整合を含まなければならないことを示すことができます。この健全性エラーは、基本構成の$1 - 1 / \binom{n}{2}$エラーよりも優れており、現在の変種を効率の観点からいくらか好ましいものにしています。（後で、より強力な頑健性特性を持つ MPC に依存することで、より実質的な効率向上を得る方法を示します。）現在の変種の元のプロトコル$\Pi_R$に対する欠点は、理想的な OT チャネルを使用する MPC プロトコル$\Pi_f$をサポートできないことです。

文献からの MPC プロトコルの使用: 半正直モデル用のほとんどの標準的な MPC プロトコルは、上記の変換で使用できます。おそらく最も単純なインスタンスは、各プレイヤーペア間に理想的な OT チャネルを用いて実装された、2-private 3-player GMW プロトコル^{8 12}です。2-private 5-player BGW プロトコル⁹（または、基本構成の代替変種を用いた 1-private 3-player BGW プロトコルでさえも）や、⁴⁶からのいくらか単純なプロトコルも使用できます。最後に、線形代数関数のような特定の関数クラスに対する効率的な特殊目的 MPC プロトコルに関する膨大な研究があります。これらのプロトコルは、今や対応する関係クラスに対する効率的なゼロ知識プロトコルを得るために使用できます。

3.1 統計的正当性への対処

上記で述べたように、我々の基本構成は MPC プロトコルが完全に正しいことに依存しています。ここでは、$\Pi_f$が統計的に正しいことを許容する基本構成の変種を記述します⁴³。$\Pi'_R$の以下の修正は、証明者がプレイヤーの入力$w_i$にコミットすることから始まります。次に、証明者と検証者は、最終的な結果$r_1, ..., r_n$が証明者にのみ知られるコイントス手順を呼び出します。最後に、2 つのビューを明かすとき、検証者は「正しい」ランダム入力が使用されたことを検証できます。

以前と同様に、我々は主にコミットメントハイブリッドモデルで構成を記述し分析し、後でプロトコルを一方向性関数に基づかせるために必要な修正を記述することに焦点を当てます。

修正されたゼロ知識プロトコル$\Pi'_R$は、コミットメントハイブリッドモデルで、図 2 に記述されているように進行します。

図 2: コミットメントハイブリッドモデルにおける ZK プロトコル$\Pi'_R$

1. 証明者は、$w_1 \oplus ... \oplus w_n = w$となるような$w_1, ..., w_n \in \{0,1\}^l$をランダムに選びます。彼女は各入力$w_i$、および$n$個のランダムな文字列$r^1_p, ..., r^n_p$に個別にコミットします。ここで各$r^i_p$は$\Pi_f$における$P_i$のランダム入力と同じ長さです。
2. 検証者は、証明者に$n$個のランダムな文字列$r^1_v, ..., r^n_v$を送信します。ここで$|r^i_v| = |r^i_p|$です。
3. 証明者は、各プレイヤー$P_i$に対してランダム性$r_i = r^i_p \oplus r^i_v$を用いて、入力$(x, w_1, ..., w_n)$に対する$\Pi_f$の実行をエミュレートします。この実行に基づき、証明者はプロトコル内の$n$人のプレイヤーのビュー$V_1, ..., V_n$を準備し、これらのビューにコミットします。
4. 検証者は、ランダムに異なる$i, j \in [n]$を選び、それらを証明者に送信します。
5. 証明者は、2 つのビュー$V_i, V_j$、および対応するコミットされた入力$w_i, w_j$、ランダム入力のシェア$r^i_p$と$r^j_p$を開きます。
6. 検証者は、すべてのデコミットメントが成功し、$V_i, V_j$によって暗示される$P_i$と$P_j$の出力が 1 であり、2 つのビューが互いに、そして開かれた入力$w_i, w_j$と（$x$と$\Pi_f$に関して）一貫しており、それらのランダム入力が$r_i = r^i_p \oplus r^i_v$および$r_j = r^j_p \oplus r^j_v$を満たす場合に限り受理します。

定理 3.3 $n \ge 3$とし、$R, f$を定理 3.1 のとおりとします。$\Pi_f$が$n$者間機能$f$を統計的な正当性と、完全、統計的、または計算量的な 2-プライバシー（半正直モデルで）で実現すると仮定します。そのとき、図 2 で説明されたプロトコル$\Pi'_R$は、コミットメントハイブリッドモデルにおける NP 関係$R$に対するゼロ知識証明プロトコルであり、統計的な完全性と、健全性エラー$\epsilon < 1 - 1 / \binom{n}{2} + \delta(k)$を持つ。ここで$\delta(\cdot)$はいくつかの無視できる関数です。

証明: 完全性は、以前と同様、検証が容易です：正直な証明者との正しい対話で検証者が拒否する確率は、まさに$\Pi_f$のエラー確率です。（完全な完全性は、証明者が彼女の$\Pi_f$の呼び出しが誤った出力を生成した場合に$w$を送信させることで容易に達成できます。これは無視できる確率でしか起こらないため、ゼロ知識特性は影響を受けません。）

健全性: すべての$w$に対して$R(x, w) = 0$となるような$x$を仮定します。検証者が少なくとも$1 / \binom{n}{2} - \delta(k)$の確率で拒否することを示します。ここで$\delta(\cdot)$はいくつかの無視できる関数です。健全性を考えているので、一般性を失うことなく、証明者は常にプロトコルを終了し、要求されたすべてのコミットされた値を適切に開くと仮定できます（コミットメントを開くのに失敗すると、検証者は自動的に拒否します）。つまり、時々コミットメントを開くのに失敗したり、プロトコルを終了するのに失敗したりする証明者は、常にコミットメントを開き、プロトコルを終了し、検証者に受理させる確率が少なくとも同じである証明者に自明に変換できます。$\Pi_f$の入力$w_i$およびランダム入力のシェア$r^i_p$はステップ 1 でコミットされるため、ステップ 2 で決定される有効なランダム入力$r_i = r^i_p \oplus r^i_v$は、有効な入力$w_i$から独立であることが保証されます。（実際、検証者は、証明者がすでに$r^i_p$にコミットした後に、$r^i_v$を均一かつ独立にランダムに選択します。）我々は今、以下のケースを区別できます。

• 入力$w_i$とランダム入力$r_i$が、$\Pi_f$の正直な実行において、あるプレイヤーを（誤った）出力 1 に導く。$\Pi_f$の統計的正当性と、$r_i$が$w_i$から独立であることにより、このイベントは無視できる確率で発生します。
• それ以外の場合（すなわち、$w_i, r_i$がすべてのプレイヤーを出力 0 に導く）：ここでは 2 つのサブケースを区別します。
  • ステップ 3 でコミットされたビュー$V_i$が、入力$w_i$とランダム入力$r_i$で$\Pi_f$を正直に実行することによって得られる。この場合、すべてのビュー$V_i$は出力 0 を意味し、検証者は常に拒否します。
  • それ以外の場合、あるビュー$V_i$の入力がステップ 1 で決定された文字列$w_i$と異なるか、ある$V_i$のランダム入力がステップ 2 で決定された$r_i$と異なるか、または$x$と$\Pi_f$に関して一貫性のないビューのペア$V_i, V_j$が存在します。（これらのタイプの不整合のいずれも発生しない場合、我々は最初のサブケースにいなければなりません。）いずれにせよ、不整合は少なくとも$1 / \binom{n}{2}$の確率で検出されます。

全体として、検証者の拒否確率は少なくとも$1 / \binom{n}{2} - \delta(k)$です。ここで$\delta$は$\Pi_f$のエラー確率です。$\Pi_f$の統計的正当性は、ランダム入力$r_i$が均一に分布しているだけでなく、入力$x, w_i$から独立に選ばれることも仮定していることに注意してください。したがって、証明者がまず$w_1, ..., w_n$にコミットすることが不可欠です（ステップ 1 で行われるように）。

ゼロ知識: ゼロ知識特性は、基本的なケースと同様に証明されます。直感的には、証明者のコミットメントの秘匿特性は、検証者が$\Pi_f$を呼び出す際に使用されるランダム性に影響を与えることができず、また$P_i, P_j$以外のプレイヤーのランダム入力について何も学ぶことができないことを保証します。これらのビューは、以前と同様に、$\Pi_f$の 2-プライバシーによって保証されるシミュレータ SIM を使用してシミュレートできます。不正直な検証者$V^*$のシミュレータ$M^*$は、入力$(k, x)$に対して次のように動作します。

1. 入力$(k, x)$で$V^*$を実行します。$r^1_v, ..., r^n_v$をステップ 2 で$V^*$によって送信された文字列とし、$i, j$をステップ 4 で送信されたインデックスのペアとします。（以前と同様、コミットメントハイブリッドモデルでは証明者のコミットメントは自明にシミュレートできます。）
2. ランダムな$w_i, w_j$を選び、$\text{SIM}(k, \{i,j\}, x, (w_i, w_j), 1)$を実行してビューのペア$(V_i, V_j)$をシミュレートします。$r_i, r_j$をシミュレートされたビューに含まれるランダム入力のペアとします。
3. 上記の$w_i, w_j, V_i, V_j$と$r^i_p = r_i \oplus r^i_v, r^j_p = r_j \oplus r^j_v$を用いて、ステップ 5 の証明者のデコミットメントをシミュレートします。

$M^*$の正当性は、完全に正しい$\Pi_f$の以前のケースと同様に論じられます。唯一の違いは、今や証明者が$\Pi_f$を実行するために使用するランダム入力$r_i$が$V^*$と共同で生成されることです。しかし、証明者の貢献$r^i_p$は検証者の貢献$r^i_v$から独立しているため、$\Pi'_R$におけるビュー$(V_i, V_j)$は、$V^*$のランダム性に条件付けられた場合でも、$\text{SIM}(k, \{i,j\}, x, (w_i, w_j), 1)$の出力と区別不能です。□

我々は、統計的に拘束力のあるコミットメントプロトコル Com を用いて$\Pi'_R$を実装する問題に目を向けます。基本構成とは異なり、ここでは理想的なコミットメントの各呼び出しを Com で自然に置き換えることによって得られるプロトコルは、ゼロ知識であることが知られていません。問題は、ステップ 2 で不正直な検証者によって選ばれたランダム性が、ステップ 1 で証明者から受信したメッセージに依存する可能性があることです。これは、効率的なシミュレーションの文脈で問題となることが判明しています。

我々は、この問題を標準的な方法で解決します。ステップ 2 を、証明者と検証者の両方を巻き込むシミュレート可能なコイントスプロトコルを用いて$r^i_v$を共同で生成することで置き換えます。この目的のために、Blum のコイントスプロトコル²⁷の逐次的な繰り返しを使用できます。具体的には、長さ$m$のランダムな文字列$r^i_v$を生成するために、証明者と検証者は$m$回のフェーズで対話します。各フェーズで、証明者は Com を用いてランダムなビット$p^i_p$にコミットし、検証者はランダムなビット$p^i_v$を送信し、証明者は$p^i_p$を開きます。（証明者が$p^i_p$を開くのに失敗した場合、検証者は拒否します。）このフェーズから得られるランダムビットは、$p^i_v \oplus p^i_p$とされます。

この修正版を、$\Pi'_{R,com}$と（若干の記法乱用を伴って）表記し、図 3 に示します。

定理 3.4 $n \ge 3$とし、$R, f$を定理 3.1 のとおりとします。$\Pi_f$が$n$者間機能$f$を統計的な正当性と、完全、統計的、または計算量的な 2-プライバシー（半正直モデルで）で実現すると仮定します。Com を任意の統計的に拘束力のあるコミットメントプロトコルとします。そのとき、図 3 で説明された$\Pi'_{R,com}$は、NP 関係$R$に対するゼロ知識証明プロトコルであり、健全性エラー$\epsilon(k) < 1 - 1 / \binom{n}{2} + \delta(k)$です。ここで$\delta(\cdot)$はいくつかの無視できる関数です。さらに、$\Pi'_{R,com}$の$kn^2$回の逐次的な繰り返しから得られるプロトコルは、健全性エラー$2^{-\Omega(k)}$を持つゼロ知識証明です。

証明: 完全性はプロトコル$\Pi'_R$と全く同じように従います。健全性もプロトコル$\Pi'_R$とほぼ同じように従います。唯一の違いは、$r_i$値の均一性と独立性が、コイントスサブプロトコルにおける正直な検証者の$p^i_v$の選択によって保証されることです。

ゼロ知識: ゼロ知識を論じるために、我々のプロトコルのステップ 2 で実行されるコイントスプロトコル$\Pi_{coin}$に関する以下の標準的な補題を利用します（例えば、[^17, Chapter 7]参照）。

補題 3.5（コイントス補題） プロトコル$\Pi_{coin}$において、多項式時間オラクルマシン$S_{coin}$が存在し、任意の多項式時間敵対的検証者$V^*$に対して、以下が成り立ちます：

1. 均一にランダムに選ばれたビット$b$に対する$S_{coin}(k, b)$の出力は、$V^*$と正直な証明者の間の実際の対話と計算量的に区別不能です。
2. 任意のビット$b$に対する$S_{coin}(k, b)$の出力は、任意の中止しないシミュレートされた対話において、$p^i_p \oplus p^i_v = b$という特性を持ちます。

これでシミュレーションを記述できます。不正直な検証者$V^*$のシミュレータ$M^*$は、入力$(k, x)$に対して次のように動作します。

図 3: プレーンモデルにおける ZK プロトコル$\Pi'_{R,com}$

1. 証明者は、$w_1 \oplus ... \oplus w_n = w$となるような$w_1, ..., w_n \in \{0,1\}^l$をランダムに選びます。彼女は Com を用いて各入力$w_i$、および$n$個のランダムな文字列$r^1_p, ..., r^n_p$に個別にコミットします。ここで$r^i_p$は$\Pi_f$における$P_i$のランダム入力と同じ長さです。$z = |r^1_p| + ... + |r^n_p|$とします。

2. $y = 1$から$z$まで、以下のプロトコル$\Pi_{coin}$が続き、長さ$z$の文字列$p$を決定します。 (a) 証明者は Com を用いてランダムに選ばれたビット$p^y_p$にコミットします。 (b) 検証者はランダムに選ばれたビット$p^y_v$を証明者に送信します。 (c) 証明者は$p^y_p$へのコミットメントを開きます。証明者がコミットメントを開くのに失敗した場合、検証者は中止します。この時点で、文字列$p$の$y$番目のビット（$p_y$で示される）を$p^y_p \oplus p^y_v$に設定します。

3. 上記の手順を通じて、$n$個の文字列$r^1_v, ..., r^n_v$（$|r^i_v| = |r^i_p|$）が、文字列$(r^1_v \circ ... \circ r^n_v)$の$y$番目のビットが$p_y$に等しくなるように定義されます。

4. 証明者は、各プレイヤー$P_i$に対してランダム性$r_i = r^i_p \oplus r^i_v$を用いて、入力$(x, w_1, ..., w_n)$に対する$\Pi_f$の実行をエミュレートします。この実行に基づき、証明者はプロトコル内の$n$人のプレイヤーのビュー$V_1, ..., V_n$を準備し、Com を用いて各ビューに個別にコミットします。

5. 検証者は、ランダムに異なる$i, j \in [n]$を選び、それらを証明者に送信します。

6. 証明者は、2 つのビュー$V_i, V_j$、および対応するコミットされた入力$w_i, w_j$、ランダム入力のシェア$r^i_p$と$r^j_p$を開きます。

7. 検証者は、すべてのデコミットメントが成功し、$V_i, V_j$によって暗示される$P_i$と$P_j$の出力が 1 であり、2 つのビューが互いに、そして開かれた入力$w_i, w_j$と（$x$と$\Pi_f$に関して）一貫しており、それらのランダム入力が$r_i = r^i_p \oplus r^i_v$および$r_j = r^j_p \oplus r^j_v$を満たす場合に限り受理します。

8. シミュレータは、成功するまで以下の$l = n^2k$回の「試行」を行います。シミュレータがすべての試行で失敗した場合、中止します。

9. シミュレータはまず、異なるパーティのペア$\{i, j\}$と入力$w_i, w_j$をランダムに選び、MPC シミュレータ$\text{SIM}(k, \{i,j\}, x, (w_i, w_j), 1)$を呼び出して、これらのパーティのシミュレートされたビュー$V_i$と$V_j$を取得します。$r_i, r_j$をシミュレートされたビューに含まれるランダム入力のペアとします。すべての$h \notin \{i,j\}$に対して、シミュレータはランダムなビュー$V_h$を準備します。

10. シミュレータは、ステップ 1 で正直な証明者が行うように振る舞います。

11. ステップ 2 では、シミュレータは補題 3.5 によって保証される$S_{coin}$を繰り返し呼び出し、それを用いて、各$p^y_p \oplus p^y_v$に適切な要件を課すことにより、$r^i_v = r_i \oplus r^i_p$および$r^j_v = r_j \oplus r^j_p$を保証します。

12. 各ビュー$V_i$に対して、シミュレータは検証者アルゴリズムでコミットメントプロトコルを実行します。

13. 検証者がチャレンジ$\{i,j\}$で応答した場合、「試行」は成功したと言い、そうでなければ試行は失敗し、やり直します。試行が成功した場合、シミュレータは$V_i$と$V_j$を検証者に開き、成功した対話から得られる検証者のビューを出力します。

このシミュレータの正当性は、基本プロトコルのシミュレータの正当性と同じ議論に従います（定理 3.2 の証明と同じハイブリッドのシーケンスを使用し、さらに補題 3.5 によって提供されるシミュレータ保証を使用します）。□

3.2 応用：証拠長への接近

このセクションでは、通信複雑性が$m \cdot \text{poly}(k) \cdot \text{polylog}(s)$であるゼロ知識プロトコルを提示します。ここで$m$は証拠長、$k$は暗号セキュリティパラメータ、$s$は証拠検証回路$C(w)$（$R(x, \cdot)$を検証する）のサイズです。これは、$C$が定数深さを持つ場合に成り立ちます。

ゼロ知識プロトコルは、¹⁴からの定数深さ回路用の MPC プロトコルに依存します。このプロトコルの基本バージョンは、Razborov と Smolensky ^{19 20}の多項式表現技術と BGW ⁹の MPC プロトコルを組み合わせたものです。（¹⁴のプロトコルには、我々の大まかな複雑性分析には重要でないいくつかの追加の最適化が含まれています。）

事実 3.6 ¹⁴ $C$をサイズ$s$、入力$v$の長さ$m$の定数深さ回路（ファンイン無制限の$\vee, \wedge, \oplus, \neg$ゲートを使用）とします。そのとき、$n = \text{polylog}(s)$に対して、$n$人のプレイヤー間の$v$の任意の分割$(v_1, ..., v_n)$に対して、$C(v_1, ..., v_n)$を統計的な正当性と 2-プライバシーで計算する$n$者間 MPC プロトコル$\Pi$が存在し、$\Pi$の通信複雑性とランダム性複雑性は最大で$m \cdot k \cdot \text{polylog}(s)$です。

事実 3.6 と定理 3.4 を組み合わせると、以下が得られます：

系 3.7 一方向性関数が存在すると仮定します。そのとき、サイズ$s$で定数深さ（ファンイン無制限の$\vee, \wedge, \oplus, \neg$ゲートを使用）の回路$C(w)$によって検証できる任意の NP 関係$R(x, w)$に対して、通信複雑性が$|w| \cdot \text{poly}(k) \cdot \text{polylog}(s)$であるゼロ知識証明プロトコルが存在します。ここで$k$は暗号セキュリティパラメータです。

付録 A では、同様の通信複雑性を達成する上記プロトコルの非対話バージョンを記述します。

4. 悪意のあるモデルにおける MPC からのゼロ知識証明

このセクションでは、複雑性に$k^2(n)$の乗法的なオーバーヘッドをもたらす単純な繰り返しを避けつつ、無視できる健全性エラー$2^{-k}$を持つゼロ知識プロトコルを得ることを目指します。我々は、基礎となる MPC プロトコル$\Pi_f$からのセキュリティ要件を、悪意のあるモデルにおける$t$-セキュリティに強化することによってこれを行います。（これは、前のセクションで使用された半正直モデルにおける 2-プライバシーまたは 1-プライバシーとは対照的です。）実際には、MPC プロトコルが半正直モデルで$t$-private であり、悪意のあるモデルで（完全または統計的に）t-robust であることのみが必要である（定義 2.6 で定義）。

まず、$\Pi_f$が完全に$t$-robust であると仮定します。我々は、$t$が健全性パラメータ$k$の定数倍であり、$n$が$t$の定数倍となるようにパラメータを選びます。この場合のゼロ知識プロトコルは、基本構成（図 1）で説明されたプロトコル$\Pi_R$と同一ですが、検証者が証明者に$t$個のランダムに選択されたビューを開くよう要求し、それらの一貫性をチェックする点が異なります。プロトコル$\Pi_{R,t}$は図 4 で正式に記述されます。

図 4: コミットメントハイブリッドモデルにおける ZK プロトコル$\Pi_{R,t}$

1. 証明者は、排他的論理和が証拠$w$に等しくなるような$w_1, ..., w_n \in \{0,1\}^l$をランダムに選びます。彼女は入力$(x, w_1, ..., w_n)$に対する$\Pi_f$の実行をエミュレートします。この実行に基づき、証明者は$n$人のプレイヤーのビュー$V_1, ..., V_n$を準備し、これらの$n$個のビューそれぞれに個別にコミットします。
2. 検証者は、ランダムに$t$個の異なるプレイヤーインデックス$i_1, ..., i_t \in [n]$を選び、それらを証明者に送信します。
3. 証明者は、$t$個のビュー$V_{i_1}, ..., V_{i_t}$に対応するコミットメントを開きます。
4. 検証者は、以下の場合に限り受理します： (a) 証明者が要求された$t$個のビューを正常に開いた。 (b) これらのビューのすべてのプレイヤーの出力が 1 である。 (c) $1 \le j, h \le t$の各々に対して、ビュー$V_{i_j}$と$V_{i_h}$が互いに一貫している（$x$と$\Pi_f$に関して）。

定理 4.1 $\Pi*f$が$n$者間機能$f$を完全な$t$-頑健性（悪意のあるモデルで）と、完全、統計的、または計算量的な$t$-プライバシー（半正直モデルで）で実現すると仮定します。ここで$t = \Omega(k)$かつ$n = ct$（$c > 1$は定数）です。そのとき、図4で説明された$\Pi*{R,t}$は、コミットメントハイブリッドモデルにおけるNP関係$R$に対するゼロ知識証明プロトコルであり、健全性エラー$2^{-\Omega(k)}$です。

証明: 完全性とゼロ知識の議論は定理 3.1 の証明と同様であり、健全性のみが新しい証明を必要とします。健全性の証明の根底にある直感は次のとおりです。証明者によってコミットされたビュー$V_1, ..., V_n$を考えます。これらのビュー間のすべての不整合が、最大$t$個のビューを排除することによって解決できる場合（言い換えれば、互いに一貫性のある$n-t$個のビューが存在する場合）、$V_1, ..., V_n$を介してコミットされたプロトコル実行は、最大$t$人のプレイヤーを汚染する敵対者によって実現され得ます。（我々は、$t$個の除外されたビューが他の$n-t$個のビューと一貫していることを要求しません：除外されたビューは敵対者によって報告されたものと考えることができます。）$\Pi_f$の完全な$t$-頑健性により、入力$x \notin L$に対するそのような実行では、すべての汚染されていないプレイヤーは 0 を出力しなければなりません。これは、出力が 0 である$P_i$のコミットされたビュー$V_i$が少なくとも$n-t$個存在することを意味します。$t$は$n$の定数割合であるため、検証者は、$n$において無視できる確率を除いて、これらのビューの少なくとも 1 つを開く（そしてしたがって拒否する）でしょう。一方、すべての不整合を解決するために$t$個以上のビューを排除する必要がある場合、開かれた$t$個のビューは、圧倒的な確率で、検証者に少なくとも 1 つの不整合を明らかにします。

健全性を正式に論じるために、n 個のコミットされたビュー$V_1, ..., V_n$に基づいて定義される以下の不整合グラフ$G$を考えます。グラフ$G$は$n$個の頂点（$n$個のビューに対応）を持ち、ビュー$V_i, V_j$が不整合である（$\Pi_f$と$x$に関して）場合に$G$に辺$(i,j)$が存在します。すなわち、ビュー$V_j$における$P_i$からの受信メッセージが、$V_i$に暗黙的に含まれる$P_j$への送信メッセージと異なるか、またはその逆です。我々は、両方のケースで検証者が$x \notin L$を圧倒的な確率で拒否することを示し、健全性を 2 つのケースに従って分析します。

• ケース 1: $G$にサイズが最大$t$の頂点被覆集合$B$が存在する。この場合、$i \notin B$であるすべてのビュー$V_i$の出力は 0 でなければならないと主張します。（直感的には、「小さな」頂点被覆はビュー間のすべての不整合を「説明」できる。）これを見るために、敵対者がプレイヤーの集合$B$を汚染し、$i \notin B$である任意のプレイヤー$P_i$のビューが$V_i$になるように振る舞うプロトコル$\Pi_f$の実行を考えます。そのような実行は、$P_i \in B$から$P_j \notin B$へのすべてのメッセージをビュー$V_j$のように選択することによって得られます。$B$は頂点被覆であるため、$i, j \notin B$であるビュー$V_i, V_j$のすべてのペアはグラフ$G$で接続されておらず、したがって一貫しています。最後に、$\Pi_f$の完全な$t$-頑健性により、そのような汚染は正直なプレイヤーの出力に影響を与えるべきではなく、出力は 0 でなければなりません。したがって、$i \notin B$であるすべてのビュー$V_i$で出力が 0 である場合、検証者が彼の$t$個の選択の中で、$B$にないプレイヤーを少なくとも 1 人選ぶだけで十分です。パラメータの選択により、これが起こらない確率は最大で$(t/n)^t = 2^{-\Omega(t)} = 2^{-\Omega(k)}$です。

• ケース 2: $\text{min-VC}(G) > t$。（ここで、また以下で、$\text{min-VC}(G)$は$G$の最小頂点被覆のサイズを示します。）そのようなグラフでは、頂点の定数割合のランダムな選択が、圧倒的な確率で辺に当たると主張したいです。このために、我々は最小頂点被覆のサイズと最大マッチングのサイズの間のよく知られた関連性を利用します。（マッチングを考える利点は、辺間の独立性が得られることです。）より詳細には、グラフ$G$はサイズが$t/2$より大きいマッチングを持たなければなりません（そうでなければ、最大マッチングが$t/2$未満の辺を含む場合、このマッチングの頂点はサイズが$t$未満の VC を形成します）。検証者が$G$の少なくとも 1 つの辺を選べば、彼は拒否します。検証者が選ぶ$t$個の頂点（ビュー）が$G$のすべての辺を外す確率は、彼がマッチングのすべての辺を外す確率よりも小さく、これもまた最大で$2^{-\Omega(t)} = 2^{-\Omega(k)}$です。（実際、最初の$t/2$個の頂点$i_1, ..., i_{t/2}$がマッチングの辺に当たらなかったと仮定します。そのとき、それらの$t/2$個のマッチングの隣接点は、後続の各頂点$i_j$によってヒットされる確率が$\Omega(t/n) = \Omega(1)$となります。）□

定理 4.1 の証明は、なぜ我々が$t$-プライバシーだけに頼ることができず、MPC プロトコルが悪意のある敵対者に対して$t$-robust である必要があるのかを説明しています。実際、$t$-private プロトコルでは、単一の悪意のあるプレイヤー$P_i$が、単に誤ったメッセージを送信することによって、すべての正直なプレイヤーに誤った出力を持たせることがあるかもしれません。これは、$P_i$だけが頂点被覆を形成する不整合グラフ$G$に対応します。そのような場合、検証者は$P_i$がランダムに選ばれた場合にのみ不整合を検出しますが、これは定数の確率でしか起こりません。

上記のプロトコルでコミットメントを実現する方法については、このセクションの最終的なプロトコルに到達するまで（下記参照）遅らせます。

4.1 MPC モデルの変更

基本構成の健全性増幅オーバーヘッドを排除するために必要な最後の変更は、$n$人のプレイヤー間での$w$の秘密分散を避けることです。代わりに、我々は以下の修正された機能$f'$に対する MPC プロトコル$\Pi_{f'}$を使用します。この機能は、「入力クライアント」（²⁵の用語に従う）と呼ばれる特別なプレイヤー$I$から入力$w$全体を受け取り、$R(x, w)$を全$n$人のプレイヤー$P_i$に出力します。（NP 言明$x$は、以前と同様、全プレイヤーに知られていますが、$I$以外のプレイヤーは秘密入力を持たない。）プロトコル$\Pi_{f'}$は、$I$と最大$t$人のプレイヤー$P_i$を汚染する可能性のある敵対者に対して、悪意のあるモデルで安全であると仮定できます。以前と同様、我々はプロトコルが定義 2.5 および 2.6 からの$t$-プライバシーと（完全な）$t$-頑健性の要件を満たすことのみを必要としますが、$t$-頑健性は敵対者が最大$t$人のプレイヤー$P_i$に加えて$I$を汚染することを許容する点が異なります。後で使用する²⁵の MPC プロトコルは、すでにこの「入力クライアント」フレームワークで提示されていることに注意してください。

この場合、$\Pi_{R,I,t}$と表記されるゼロ知識プロトコルは、図 4 のプロトコル$\Pi_{R,t}$と同じ方法で進行しますが、以下の変更点があります：(1) $w$を$n$人のプレイヤー間で秘密分散する代わりに、$w$は証明者によって$\Pi_{f'}$を呼び出す際に$I$への入力として直接使用されます。(2) 検証者は、ランダムに選択された$t$人のプレイヤー$P_i$（入力クライアント$I$を除く）のビューを見るよう要求し、それらがすべて 1 を出力し、互いに一貫していることをチェックします。$I$のビューは開くことができません（したがってコミットする必要はありません）。なぜなら、これは$w$を明かすことになるからです。

定理 4.2 $f$を入力クライアント$I$と$n$人のプレイヤー$P_1, ..., P_n$に対する以下の機能とします。公開入力$x$と$I$から受信した秘密入力$w$が与えられると、機能は$R(x, w)$をすべてのプレイヤー$P_i$に配信します。$\Pi_{f'}$が$f$を完全な$t$-頑健性（悪意のあるモデルで）と、完全、統計的、または計算量的な$t$-プライバシー（半正直モデルで）で実現すると仮定します。ここで$t = \Omega(k)$かつ$n = ct$（$c > 1$は定数）です。そのとき、上記で説明された$\Pi_{R,I,t}$は、コミットメントハイブリッドモデルにおける NP 関係$R$に対するゼロ知識証明プロトコルであり、健全性エラー$2^{-\Omega(k)}$です。

証明: 完全性とゼロ知識特性は、$\Pi_{R,t}$と本質的に同じ方法で論じられます。（ゼロ知識特性については、MPC シミュレータは、シミュレートされたプレイヤー$P_i$に、これらのプレイヤーがもはや秘密入力を持たないため、入力$w_i$を供給する必要はありません。）

健全性の証明は、異なる MPC ネットワークとゼロ知識プロトコルを考慮して、わずかに修正する必要があります。具体的には、定理 4.1 の証明との違いは、1 人のプレイヤー$I$のビューが決して開かれないことです。しかし、これは、修正された$t$-頑健性の定義が、最大$t$人の追加のプレイヤーと共に$I$が汚染されることを許容するという事実によって、すでに考慮されています。完全性のために、現在のわずかに修正された MPC モデルにおける健全性のための修正された議論の概要を述べます。

$x$が偽の言明であると仮定し、悪意のある証明者によってコミットされたビューによって定義される（$n$個の頂点$P_1, ..., P_n$上の）不整合グラフ$G$を考えます。我々は以下の 2 つのケースを区別します：

1. $\text{min-VC}(G) \le t$: 前の分析のケース 1 と同様に、コミットされたビューは、$I$と最大$t$人のプレイヤー$P_i$が汚染されるプロトコルの実行によって説明できます。完全な$t$-頑健性により、そのような実行では、残りのすべての$n-t$人のプレイヤーは 0 を出力すべきであり、これは$2^{-\Omega(k)}$の確率を除いて検証者によって検出されます。
2. $\text{min-VC}(G) > t$: 前の分析のケース 2 と同様に、グラフはサイズが$t/2$より大きい最小マッチングを持たなければなりません。したがって、プレイヤー$P_i, P_j$のペア間の不整合は、$2^{-\Omega(k)}$の確率を除いて検出されます。

4.2 統計的頑健性への対処

このセクションでは、$\Pi_{f'}$が統計的にのみ頑健である場合に適用される、4.1 節の前のプロトコルの変種を記述します。これは、4.4 節で記述される定数レートのゼロ知識への応用によって動機付けられています。

$\Pi_{f'}$が統計的にのみ$t$-robust である場合、$I$と最大$t$人のプレイヤー$P_j$を汚染する悪意のある敵対者は、不正を行う、すなわち$x$が偽の言明であるときに一部のプレイヤーに 1 を出力させる無視できる確率を持つことができます。興味深いことに、この場合、3.1 節で提示されたコイントスベースの基本プロトコルの修正は、望ましいレベルの健全性を達成するには不十分です。これは、証明者が、制御できないランダム入力にコミットしている間、すべてのプレイヤーのランダム入力が与えられた後にビュー$V_1, ..., V_n$を生成することが許されるからです。（これは、敵対者が汚染されたプレイヤーのランダム性しか知らない$\Pi_{f'}$の実際の実行とは対照的です。）そのような場合、単一の悪意のあるプレイヤーでさえ、すべての出力を高い確率で誤らせるのに十分かもしれません。もしこの特定のプレイヤーが検証者によって選ばれなければ、不整合は明らかにされないが、それでも出力は誤っている可能性があります。

この困難を回避するために、プロトコルのプライバシーに使用されるランダム入力$r_i$と、その頑健性を保証するために使用されるランダム入力を分離すると便利です。以下では、プロトコルがフェーズ 1 とフェーズ 2 の 2 つのフェーズに分割されている場合に機能する構成を記述します。フェーズ 1 に続いて、プレイヤーはフェーズ 2 で使用される長さ$l$の公開ランダム文字列$r$を取得します。これは、2 つ以上のフェーズを持つプロトコルに一般化できます。しかし、重要な点は、プロトコルの途中で生成される各文字列$r$は、前のフェーズでは予測不可能でなければならないということです。2 フェーズプロトコルの頑健性は、ランダムな文字列$r$を見た後で（一部の）$t$人の汚染されたプレイヤーを選択する可能性のある適応的な敵対者に関しても保持されるべきです。より正確には、我々は以下の適応的な$t$-頑健性の要件を課します。

定義 4.3（適応的に$t$-頑健な 2 フェーズプロトコル） $\Pi$を上記の（入力クライアント$I$と$n$人のプレイヤー$P_i$を伴う）2フェーズMPCプロトコルとし、$f$を定理4.2のとおりとします。$\Pi$が適応的な統計的$t$-頑健性で$f$を実現するとは、定義2.4のように統計的に正しく、さらに、任意の計算量的に無制限な敵対者が以下のゲームに勝つ確率が$k$において無視できる場合を言います。まず、敵対者は偽の言明$x$（すべての$w$に対して$R(x,w) = 0$となるような）、最大$t$人の汚染されたプレイヤーの集合$T_1$、およびすべての汚染されていないプレイヤーのランダム入力$r_i$を選びます。今、敵対者は$\Pi$のフェーズ1を実行し、$I$と$T_1$のプレイヤーを任意に制御します。フェーズ1が終了した後、コイントスオラクルが呼び出され、ランダムなチャレンジ$r$が生成されます。$r$に基づいて、敵対者は最大$t - |T_1|$人の追加のプレイヤーを汚染し、プロトコルのフェーズ 2 の間、正直なプレイヤーと対話し続けます。敵対者は、一度も汚染されなかったプレイヤーが 1 を出力した場合に勝利します。

この適応的な頑健性特性は、4.4 節で採用する具体的な MPC プロトコルによって満たされ、健全性分析がうまくいくために重要です。

そのような 2 フェーズ MPC プロトコル$\Pi_{f'}$から得られるゼロ知識プロトコル$\Pi'_{R,I,t}$は、図 5 に記述されています。便宜上、ここでは証明者と検証者が理想的なコミットメントだけでなく、理想的なコイントスオラクルにもアクセスできると仮定します。しかし、後者のオラクルは、我々の設定では前者に基づいて容易に実装できます。

図 5: コミットメントおよびコイントスハイブリッドモデルにおける ZK プロトコル$\Pi'_{R,I,t}$

1. 証明者は、$I$のランダム入力$r_I$と、すべてのプレイヤー$P_i$のランダム入力$r_i$を選びます。彼女は、フェーズ 1 の終わりまでのプレイヤーのビュー（$(V^1_1, ..., V^1_n)$で示される）を計算し、それらすべてにコミットします。MPC プロトコルのこのフェーズでブロードキャストされたメッセージは、$P$から$V$に直接送信されます。
2. 証明者と検証者は、コイントスオラクルを呼び出して、長さ$l$のランダムなチャレンジ文字列$r$を生成します。
3. 証明者は、前のステップで生成された文字列$r$を用いて、頭の中でプロトコルを実行し続け、フェーズ 2 のビュー$(V^2_1, ..., V^2_n)$を生成します。証明者はこれらの$n$個のビューにコミットします。再び、MPC プロトコルのフェーズ 2 でブロードキャストされたメッセージは、$P$から$V$に直接送信されます。
4. 検証者は、ランダムに異なる$i_1, ..., i_t \in [n]$を選び、それらを証明者に送信します。
5. 証明者は、対応する$2t$個のコミットメント$V^1_{i_1}, ..., V^1_{i_t}, V^2_{i_1}, ..., V^2_{i_t}$を開きます。
6. 検証者は、証明者が要求された$2t$個のビューを正常に開いた場合、開かれたビューがすべて（公開値$x, r$および証明者によって送信されたブロードキャストメッセージが与えられた場合に）一貫しており、これらのビューのすべての出力が 1 である場合に限り受理します。

定理 4.4 $f$を定理 4.2 のとおりとします。$\Pi_{f'}$が、適応的な統計的$t$-頑健性（悪意のあるモデルで、定義 4.3 参照）と、完全、統計的、または計算量的な$t$-プライバシー（半正直モデルで）で$f$を実現する 2 フェーズプロトコルであると仮定します。ここで$t = \Omega(k)$かつ$n = ct$（$c > 1$は定数）です。そのとき、図 5 で説明された$\Pi'_{R,I,t}$は、コミットメントおよびコイントスハイブリッドモデルにおける NP 関係$R$に対するゼロ知識証明プロトコルであり、健全性エラー$2^{-\Omega(k)} + \delta(k)$です。ここで$\delta(k)$は$\Pi_{f'}$の頑健性エラーです。

証明: 完全性とゼロ知識特性は以前と同様に論じられます。我々は、ZK プロトコルにおける任意の不正な証明者の戦略に、同じビューを生成する MPC プロトコルにおける対応する敵対的戦略を割り当てることによって、健全性を論じます。そのようなシミュレーションは、ZK 証明者が不整合なビューをあまり多く作成しない場合にのみ可能ですが、彼女がそうする場合、ZK 検証者は不整合を検出し、圧倒的な確率で拒否します。

我々は今、この議論を形式化します。偽の言明$x$を固定します。$P^*$を、入力$x$に対する ZK プロトコルにおける（決定論的で、計算量的に無制限な）証明者戦略とします。$V^1_{P^*}$を、$P^*$がステップ 1 でコミットするビュー$V^1_1, ..., V^1_n$とし、$V^2_{P^*}(r)$を、$P^*$がランダムなチャレンジ$r$に応答してステップ 3 でコミットするビュー$V^2_1, ..., V^2_n$とします。最後に、$G_{P^*}(r)$を、ビューの完全な集合$V_{P^*}(r) = (V^1_{P^*}, V^2_{P^*}(r))$によって定義される不整合グラフとします。

我々は、MPC プロトコルで$I$と最大$t$人のプレイヤー$P_i$を汚染することによって$P^*$と同じビューを生成しようとする、対応する（決定論的で、計算量的に無制限な）MPC 敵対者$A^*$を定義します。（MPC 敵対者は、汚染しないプレイヤーも含め、すべてのプレイヤーのランダム入力$r_i$を決定できますが、2 つのフェーズ間で生成されるランダムなチャレンジ$r$を予測することはできないことを思い出してください。）

MPC 敵対者$A^*$は、部分的なビュー$V^1_{P^*}$によって定義される不整合グラフ$G^1_{P^*}$を考慮することから始めます。これは、まだ$A^*$には未知の最終的な不整合グラフ$G_{P^*}(r)$の部分グラフであることに注意してください。グラフがサイズ$t/2$の頂点被覆$T_1$を持たない場合、$A^*$は諦めます。そうでなければ、$A^*$は$T_1$のすべてのプレイヤーを汚染します。それは、$V^1_{P^*}$で指定されたように、$I$の入力$w$と秘密のランダム入力$r_I, r_1, ..., r_n$を設定します。今、$A^*$は MPC プロトコルのフェーズ 1 と対話し、汚染されたプレイヤーに代わってメッセージを送信し、すべての汚染されていないプレイヤーのビューを$V^1_{P^*}$と一致させます。（これは、$T_1$が頂点被覆であるという仮定によって可能です。）次に、$A^*$はランダムなチャレンジ$r$を取得します。それが受け取る$r$は、最終的な不整合グラフ$G_{P^*}(r)$を定義します。再び、グラフがサイズ$t/2$の頂点被覆$T_2$を持たない場合、$A^*$は諦めます。そうでなければ、それは$T_2$のすべての汚染されていないプレイヤーを汚染し、MPC プロトコルのフェーズ 2 と対話します。（全体で最大$t$人のプレイヤーが汚染されたので、これは確かに$A^*$にとって許容される適応的な汚染戦略であることに注意してください。）以前と同様に、$A^*$は汚染されたプレイヤーに代わってメッセージを送信し、すべての汚染されていないプレイヤーの最終的なビューを$V_{P^*}(r)$と一致させます。最終的な MPC ビュー$V_{A^*}(r)$は、汚染されていないプレイヤーの実際のビューと、汚染されたプレイヤーに対する$V_{P^*}(r)$に現れるビューと共に定義されます。

補題 4.5 すべての$r$に対して、$G_{P^*}(r)$がサイズが最大$t/2$の頂点被覆を持つ場合、$V_{A^*}(r) = V_{P^*}(r)$です。

証明: $G^1_{P^*}$は$G_{P^*}(r)$の部分グラフであるため、仮定は要求される$T_1$と$T_2$の両方が存在することを意味し、したがって$A^*$は諦めません。補題は、プロトコルの 2 つのフェーズを通じて汚染されていないプレイヤーに送信されるメッセージが$V_{P^*}(r)$と一致していることに注意することで従います。□

以下の補題は、完全な頑健性の場合の健全性分析と同様に証明されます。

補題 4.6 $G_{P^*}(r)$がサイズ$t/2$の頂点被覆を持たないすべての$r$に対して、ZK 検証者は$2^{-\Omega(k)}$の確率を除いて拒否します。

我々は今、ゼロ知識プロトコルの健全性エラーに関する望ましい$2^{-\Omega(k)} + \delta(k)$の限界を証明する準備ができました。我々は、$r$のすべての可能な選択をカバーする 3 つのイベントを考えます：

1. $r$が$A^*$に$\Pi_{f'}$の$t$-頑健性を破らせる。$\Pi_{f'}$に関する仮定により、このイベントは最大で$\delta(k)$の確率で発生します。
2. 前のイベントが発生せず、さらに$G_{P^*}(r)$がサイズが最大$t/2$の頂点被覆を持つ。補題 4.5 により、$V_{P^*}(r)$には出力が 0 であるビューが少なくとも$n-t$個存在します。したがって、このイベントに条件付けられると、検証者はこれらのビューの少なくとも 1 つを開き、結果として拒否する確率は、$2^{-\Omega(k)}$を除いてです。
3. $G_{P^*}(r)$がサイズが最大$t/2$の頂点被覆を持たない。補題 4.6 により、このイベントに条件付けられると、検証者が受理する確率は最大で$2^{-\Omega(k)}$です。

全体として、検証者の受理確率は最大で$2^{-\Omega(k)} + \delta(k)$であり、要求どおりです。 これで定理 4.4 の証明は完了します。□

頂点被覆のサイズ$t/2$と MPC 汚染閾値$t$の間のギャップは、適応的汚染の「オンライン」的な性質に関連していることに注意してください。フェーズ 1 の終わりには、MPC 敵対者は、最終的なグラフで最小頂点被覆として機能するプレイヤーの集合を予測できません。

4.3 コミットメントとコイントスの実装

プレーンモデルにおける我々の以前のプロトコルに対して与えられたゼロ知識の証明はすべて、検証者が彼が見るビューに関するチャレンジに対して、多項式個の選択肢の中から 1 つを選ぶことに依存していました。ここでは、検証者が行う選択ははるかに大きな集合からのものであり、したがってゼロ知識シミュレータによって単純に推測することはできません。代わりに、我々は、検証者が健全性を維持するために、統計的に秘匿性のあるコミットメントスキーム ComSH を用いて、彼の選択に事前にコミットする「前文」を持つという標準的な技術（^{47 15 48 49}参照）を採用します。この前文では、検証者は彼の選択の「知識を証明」する必要もあります。

⁵⁰の最近の結果を用いて、統計的に秘匿性のあるコミットメントスキーム ComSH は、任意の一方向性関数に基づかせることができます。以前のプロトコルと同様に、我々は標準的な統計的に拘束力のあるコミットメントスキーム ComSB も利用します。

結果として得られるプロトコルを図 6 に示します。

定理 4.7 $f$を定理 4.2 のとおりとします。ComSH を統計的に秘匿性のあるコミットメントスキーム、ComSB を統計的に拘束力のあるコミットメントスキームとします。$\Pi_{f'}$が、適応的な統計的$t$-頑健性（悪意のあるモデルで、定義 4.3 参照）と、完全、統計的、または計算量的な$t$-プライバシー（半正直モデルで）で$f$を実現する 2 フェーズプロトコルであると仮定します。ここで$t = \Omega(k)$かつ$n = ct$（$c > 1$は定数）です。そのとき、図 6 で説明された$\Pi'_{R,I,t,com}$は、NP 関係$R$に対する無視できる健全性エラーを持つゼロ知識証明プロトコルです。

証明: 完全性と健全性の証明は、ステップ 1 と 2 が検証者の選択を統計的に秘匿に保つため、定理 4.4 の証明と本質的に同じであることに注意してください。

我々はゼロ知識特性の証明を提供するだけでよいです。不正直な（そして一般性を失うことなく、決定論的な）検証者$V^*$のシミュレータ$M^*$は、入力$(k, x)$に対して以下のように記述されます。シミュレーションの正当性は自明です。

1. シミュレータはステップ 1 で正直な証明者として振る舞い、ComSH プロトコルに従って検証者のコミットメントを受け取ります。
2. ステップ 2 では、各$i$に対して、シミュレータは次のように進みます： (a) シミュレータは検証者の状態$\sigma_i$を保存し、次に正直な証明者が行うように$b_i$をランダムに選び、それを送信し、検証者から応答を得ます。 (b) デコミットメント応答が無効な場合、シミュレータは（正直な証明者が行ったように）停止し、これまでの検証者の部分的なビューを出力します。応答が有効な場合、シミュレータは現在の状態$\sigma'_i$を保存し、検証者を状態$\sigma_i$に巻き戻します。次に$1 - b_i$を送信します。 (c) 検証者が有効なデコミットメントで応答した場合、シミュレータは$r_{i,0}$と$r_{i,1}$の両方を取得し、したがって検証者の$i_1, ..., i_t \in [n]$の選択を再構築できます。有効な応答を受け取ったかどうかにかかわらず、シミュレータは検証者の状態を$\sigma_i$に戻し、続けます。
3. シミュレータがどの$i$に対しても$r_{i,0}$と$r_{i,1}$の両方を取得できなかった場合、シミュレータは中止し、$\perp$を出力します。シミュレータが中止した場合、そのステップ 1 のメッセージを条件として検証者がプロトコルのステップ 2 を完了する確率は$2^{-k}$であり、したがってシミュレータが中止する確率は無視できることに注意してください¹⁰。そうでなければ、シミュレータは続けます。
4. シミュレータは今、MPC シミュレータ SIM を呼び出し、上記で検証者から抽出したインデックスのリスト$\{i_j\}$を SIM に提供します。次に、SIM は、MPC プロトコル中のブロードキャストされたメッセージとランダムなチャレンジ$r$と共に、これらのパーティのシミュレートされたビュー$\{V_{i_j}\}$をシミュレータに提供します。すべての$h \notin \{i_j\}$に対して、シミュレータはランダムなビュー$V_h$を準備します。これらの各ビュー$V_i$は、MPC プロトコルのフェーズ 1 とフェーズ 2 のビューに対応する 2 つの部分$V^1_i$と$V^2_i$に分割されます。
5. ステップ 3 では、シミュレータはすべてのフェーズ 1 ビュー$(V^1_1, ..., V^1_n)$にコミットし、フェーズ 1 のすべてのブロードキャストされたメッセージを送信します。
6. ステップ 4 では、シミュレータはコイントス補題によって保証される$S_{coin}$を繰り返し呼び出し、それを用いて、$r$の各ビットが上記の MPC シミュレータによって指定されたランダムなチャレンジに設定されることを保証します。
7. ステップ 5 では、シミュレータはすべてのフェーズ 2 ビュー$(V^2_1, ..., V^2_n)$にコミットし、フェーズ 2 のすべてのブロードキャストされたメッセージを送信します。
8. ステップ 6 では、シミュレータは正直な証明者が行うように振る舞い、検証者によって開かれたすべてのコミットメントが上記の抽出と一致する方法で開かれていることを検証します。そうでなければ、シミュレータは中止します。この種のシミュレータの中止が顕著な確率で発生する場合、それは直接、コミットメントスキーム ComSH の計算量的拘束特性を破るために使用できることに注意してください²⁶。
9. ステップ 7 では、シミュレータは検証者によって要求されたインデックスの集合$\{i_j\}$に対応する$2t$個のコミットメント$\{V^1_{i_j}, V^2_{i_j}\}$を開き、成功した対話から得られる検証者のビューを出力します。□

図 6: プレーンモデルにおける ZK プロトコル$\Pi'_{R,I,t,com}$

1. 検証者は、ランダムに異なる$i_1, ..., i_t \in [n]$を選びます。彼はこれらの選択を長さ$g = O(t \log n)$の文字列$c$にエンコードします。検証者は次に、長さ$g$のランダムな文字列$r_{1,0}, ..., r_{k,0}, r_{1,1}, ..., r_{k,1}$を選び、各$i$に対して$r_{i,b} = r'_{i,b} \oplus c$を設定します。検証者は ComSH を呼び出して、2k 個の文字列$\{r_{i,0}, r_{i,1}\}$それぞれに個別にコミットします。
2. $i = 1$から$k$まで、以下のプロトコルが続きます： (a) 証明者はランダムなビット$b_i$を送信します。 (b) 検証者は$r_{i,b_i}$へのコミットメントを開きます。
3. 証明者は、$I$のランダム入力$r_I$と、すべてのプレイヤー$P_i$のランダム入力$r_i$を選びます。彼女は、フェーズ 1 の終わりまでのプレイヤーのビュー（$(V^1_1, ..., V^1_n)$で示される）を計算し、ComSB を用いてそれらすべてにコミットします。MPC プロトコルのこのフェーズでブロードキャストされたメッセージは、$P$から$V$に直接送信されます。
4. 証明者と検証者は、以下のコイントスプロトコルを呼び出して、長さ$l$のランダムなチャレンジ文字列$r$を生成します。 $i = 1$から$l$まで、以下のプロトコル$\Pi_{coin}$が続きます： (a) 証明者は ComSB を用いてランダムに選ばれたビット$p^i_p$にコミットします。 (b) 検証者はランダムに選ばれたビット$p^i_v$を証明者に送信します。 (c) 証明者は$p^i_p$へのコミットメントを開きます。この時点で、$r$の$i$番目のビット（$r_i$で示される）を$p^i_p \oplus p^i_v$と定義します。
5. 証明者は、上記で生成された文字列$r$を用いて、頭の中でプロトコルを実行し続け、フェーズ 2 のビューのベクトル$(V^2_1, ..., V^2_n)$を生成します。証明者は ComSB を用いてこれらの$n$個のビューにコミットします。再び、MPC プロトコルのフェーズ 2 でブロードキャストされたメッセージは、$P$から$V$に直接送信されます。
6. 検証者は、ステップ 1 で行われた ComSH を用いたすべてのコミットメントを開きます。証明者は一貫性をチェックし（不整合があれば中止）、集合$i_1, ..., i_t \in [n]$を抽出します。
7. 証明者は、対応する$2t$個のコミットメント$V^1_{i_1}, ..., V^1_{i_t}, V^2_{i_1}, ..., V^2_{i_t}$を開きます。
8. 検証者は、証明者が要求された$2t$個のコミットメントを正常に開いた場合、開かれたビューがすべて（公開値$x, r$および証明者によって送信されたブロードキャストメッセージが与えられた場合に）一貫しており、これらのビューのすべての出力が 1 である場合に限り受理します。

4.4 応用：「定数レート」ゼロ知識証明

このセクションでは、4.2 節の一般構成を²⁵の MPC プロトコルの変種の上に適用することにより、通信複雑性が回路サイズ$s$に線形であるゼロ知識プロトコルの構成を記述します。

²⁵のプロトコルは、4.2 節で定義された 2 フェーズプロトコルの要件に、$t = \Omega(n)$で、長さ$l = \text{poly}(k, \log s)$のランダムなチャレンジ$r$で準拠します。したがって、一般構成を適用できます。実際、フェーズ 2 はブロードキャストメッセージのみを含む縮退した形式を取ることができます。したがって、一般構成のステップ 3 で、証明者はコミットする代わりにこれらのメッセージを検証者に送信できます。

入力が定数個のクライアントから発信される場合の²⁵の MPC プロトコルの通信複雑性は、$\text{poly}(k) \cdot \log n \cdot s + \text{poly}(k, n, \log s)$です²⁴。我々は今、我々の応用で要求される機能$f'$のタイプに対して、この複雑性を$O(s) + \text{poly}(k, n, \log s)$に削減する方法を記述します。

²⁵における乗法的な$\text{poly}(k)$オーバーヘッドの原因は、任意の深さの回路を扱う必要があることです。しかし、証明検証の文脈では、一般性を失うことなく、証拠がサイズ$s$である（そして$w$に加えて$C(w)$の計算における中間値を含む）と仮定し、$R$が$s$個の出力ビットを持ち、それぞれが$C$の 1 つのゲートの出力とその 2 つの入力との一貫性を検証すると仮定できます。（拡張された$f'$の出力$1^s$は、元の$R$の出力 1 として解釈されます。拡張された$f'$の他のすべての出力は 0 として解釈されます。）

$R$の$s$個の出力ビットのそれぞれが、$s$個の入力ビットのうち 3 つだけに依存することに注意してください。この設定では、²⁵のプロトコルの総通信複雑性は、$O(\log n \cdot s) + \text{poly}(k, n, \log s)$のみです。ここで、$O(\log n)$の乗法的なオーバーヘッドは、Shamir の秘密分散⁵¹（より正確には、Franklin と Yung ⁵²によるこの秘密分散の変種）の使用から生じます。これは、体サイズがプレイヤーの数より大きいことを要求します。最終的な最適化として、代数幾何符号²⁶に基づく秘密分散によって、⁵²の秘密分散を定数サイズの体上で実装できます。これにより、セキュリティ閾値がさらに分数的に減少し、ゼロ知識プロトコルの漸近的な複雑性には影響しません。

以下の補題は、定数レートのゼロ知識プロトコルを得るために使用する MPC プロトコルの特性を要約します。

補題 4.8 (^{25 26}) $f$を入力クライアント$I$から入力$w$を受け取り、その出力$f(w)$を$n$人のプレイヤー$P_1, ..., P_n$に配信する機能とします。$f$がサイズ$s$でファンインが限定され、定数深さの回路で計算できると仮定します。そのとき、$f$は、$t = \Omega(n)$で、以下の効率特性を持つ、完全に$t$-private で適応的に統計的に$t$-robust な 2 フェーズ MPC プロトコル$\Pi_{f'}$によって実現できます：

• フェーズ 1 は、$I$から$n$人のプレイヤー$P_i$に送信される合計$O(s) + \text{poly}(k, n, \log s)$ビットを含みます。
• 2 つのフェーズ間のランダムなチャレンジ$r$は、長さ$\text{poly}(k, n, \log s)$です。
• フェーズ 2 は、全長が$O(s) + \text{poly}(k, n, \log s)$であるブロードキャストメッセージを含みます。

補題 4.8 と定理 4.7 の一般変換を組み合わせると、以下が得られます：

系 4.9 一方向性関数が存在すると仮定します。そのとき、サイズ$s$の回路$C(w)$（ファンインが限定されたゲートを使用）によって検証できる任意の NP 関係$R(x, w)$に対して、通信複雑性が$O(s) + \text{poly}(k, \log s)$であるゼロ知識証明プロトコルが存在します。ここで$k$は暗号セキュリティパラメータです。

証明: 補題 4.8 と定理 4.4 を組み合わせると、コミットメントハイブリッドモデルで要求されるプロトコルが直接得られます。プレーンモデルで望ましい結果を定理 4.7 から導出するには、$\Pi'_{R,I,t,com}$によって呼び出されるコミットメントプロトコルの効率的なインスタンス化を、任意の一方向性関数に基づかせる必要があります。統計的に秘匿性のあるコミットメントプロトコル ComSH は、全長が$\text{poly}(k, \log s)$の文字列にのみ適用されるため、効率のボトルネックにはなりません。したがって、長さ$l$のメッセージに対するコミットメントとデコミットメントが通信複雑性$O(l) + \text{poly}(k)$で実行できる統計的に拘束力のあるコミットメントプロトコル Com を提示すれば十分です。そのようなコミットメントプロトコル Com は、任意の一方向性関数^{45 44}から、標準的な方法で、任意の統計的に拘束力のあるコミットメントプロトコル Com’と擬似乱数生成器$G$から得ることができます：メッセージ$m$にコミットするために、Com の送信者は Com’をランダムなシード$r \in \{0,1\}^k$に適用し、次に$m \oplus G(r)$を送信します。□

5. 結論

本研究は、ゼロ知識証明と MPC の間に新しい一般的な関連性を確立しました。特に、正直者多数の場合の MPC プロトコルが、効率的で概念的に単純なゼロ知識証明の設計において有用な構成要素として機能することを示しました。これには、すべての NP に対する「定数レート」ゼロ知識証明の最初の構成も含まれます。安全な二者間計算および正直者多数のいない MPC の文脈で、正直者多数を持つ MPC を一般的に使用するというアイデアは、本研究で検討された応用を超えて、追加の応用を見出す可能性が高いです。この方向性の証拠は、最近^{53 54}で与えられました。

MPC は概念的に魅力的で非常によく研究された概念ですが、我々のゼロ知識プロトコルで要求される組み合わせ論的オブジェクトの最も一般的な抽象化であるとは限らないことに注意して締めくくります。これらのプロトコルにおける MPC コンポーネントは、大きなアルファベット上の確率的検査可能証明（PCP）のゼロ知識変種を実装するものと見なすことができます。他の種類の証明システム（対話型 PCP ⁵⁵および準線形時間検証者を持つ対話型証明⁵⁶）は、最近、効率的なゼロ知識プロトコルを構成するために利用され、特に 3.2 節の結果を改善しました。これらの証明システム、ゼロ知識証明、および MPC の間の関係をよりよく理解することは興味深いでしょう。

謝辞: 1-private MPC を使用する基本構成の変種を提案してくれた Amos Fiat と Yishay Mansour に感謝します。また、有益なコメントと提案をくれた Salil Vadhan と匿名の査読者にも感謝します。

付録 A: 非対話的設定における証拠長への接近

このセクションでは、¹⁸と³⁷で以前に検討された、前処理を伴う NIZK のモデルにおける 3.2 節のプロトコルの実現について説明します。

以下の説明では、前処理フェーズは、証明者と検証者にランダム化されたメッセージを（入力$z$が利用可能になる前に）送信し、その後姿を消す信頼できるディーラーによって実行されると仮定します。

非対話的プロトコルを得るための最初のアイデアは、（対話的な）コミット・アンド・チャレンジアプローチを、非対話的な 2-out-of-n OT の以下の実装に置き換えることです。前処理ステップでは、ディーラーは証明者に$n$個のランダムな暗号化キーを送信し、検証者にはこれらのキーのうちランダムな 2 つのサブセット（その ID は証明者には不明）を送信します。オンラインフェーズでは、証明者は対話的プロトコルと同様に$n$個のビューを生成し、対応するキーを使用して各ビュー$V_i$の暗号化を送信します。検証者はランダムなビューのペアを学習し、基本プロトコルと同様に、それらの一貫性を検証します。（これは健全性を増幅するために並行して繰り返すことができます。）

基礎となる MPC プロトコル$\Pi$の統計的正当性は、追加の困難をもたらします。プロトコル$\Pi$で使用されるランダム性を前処理ステップ中に選択することは問題があります。なぜなら、証明者がこのランダム性を知った後で、ある$x \notin L$に対してその入力$w$を選択する可能性があるからです。しかし、ここでは、¹⁴の単純な修正を使用できます。これは、プロトコルのファミリー$\Pi_p, p \in \{0, 1\}^{k \cdot \text{polylog}(s)}$を与え、各$\Pi_p$は$\Pi$とほぼ同じ複雑性を持ち、このファミリーからのランダムなプロトコルは、$p$の選択に対して$2^{-k}$の確率を除いて完全に正しく、プライベートです。プロトコルは、ランダムな$p$が前処理ステップ中に証明者と検証者の両方に与えられ、$p$が証明で使用されるプロトコル$\Pi_p$を定義するために使用される点を除いて、完全なケースと同様に進行できます。（$x$の選択が$p$に依存できる場合、$p$の長さは$|x|$程度、またはより一般的には$x$の記述サイズだけ長くする必要があります。）

事実 A.1 (修正¹⁴) $C$を事実 3.6 のような定数深さの回路とします。そのとき、事実 3.6 のようなパラメータ$n, m$と、通信複雑性およびランダム性複雑性が$m \cdot \text{polylog}(s)$である、$(2, n)$-セキュアな MPC プロトコルのファミリー$\{\Pi_p\}_{p \in \{0,1\}^{mk \cdot \text{polylog}(s)}}$が存在します。さらに、$p$の選択に対して圧倒的な確率で、プロトコル$\Pi_p$は$C(\cdot)$を完全な正当性とプライバシーで計算します。

（¹⁴の用語と記法を使用すると、サイズ$mk \cdot \text{polylog}(s)$の公開ランダム性$p$を持つ RPC $p_r(z, \pi)$を得る必要があります。これは、$p$の選択に対して圧倒的な確率で、完全に正しいです。これは、¹⁴の基本的な RPC 構成を$O(mk)$回繰り返し、任意の固定入力$w \in \{0,1\}^m$に対するエラー確率を$2^{-\Omega(m)}$に減らし、次に出力に対するしきい値関数に効率的な次数 3 のランダム化多項式を適用することで達成できます。ユニオンバウンドの議論により、$p$の圧倒的な割合がすべての入力$w$に対して良好になります。）

そのようなファミリー$\Pi_p$が与えられると、非対話モデルにおけるゼロ知識プロトコル$\Pi_R$は次のように進行します：

1. (前処理フェーズ) 信頼できるディーラーはランダムなプロトコルインデックス$p$を選び、それを証明者と検証者の両方に送信します。また、$n$個のランダムな対称暗号化キー$K_1, ..., K_n$を選んで証明者に送信し、ランダムに 2 つの異なるインデックス$i, j \in [n]$を選び、検証者に$(i, j, K_i, K_j)$を送信します。
2. (証明) 証明者は、ランダムに$w_1, ..., w_n \in \{0,1\}^l$を選び、$w_1 \oplus ... \oplus w_n = w$となるようにし、同様に$\Pi_p$のためのランダム性$r_1, ..., r_n$も選びます。彼女は入力$(x, w_1, ..., w_n)$とランダム入力$r_1, ..., r_n$に対する$\Pi_p$の実行をエミュレートします。この実行に基づき、証明者は$\Pi_p$における$n$人のプレイヤーのビュー$V_1, ..., V_n$を準備します。彼女は、前処理フェーズで与えられたキー$K_i$を使用して各ビュー$V_i$を個別に暗号化し、$e_1 = \text{ENCRYPT}(V_1, K_1), ..., e_n = \text{ENCRYPT}(V_n, K_n)$を検証者に送信します。
3. (検証) 検証者は、$e_i, e_j$と前処理フェーズで得たキー$K_i, K_j$を使用して$V_i, V_j$を復号し、両方の$P_i$と$P_j$の出力（ビューからわかる）が 1 であり、2 つのビューが一貫している（$\Pi_p$に従って）場合に限り受理します。

我々の以前の構成との類似性のため、プロトコルの特性の概要のみを述べます。プロトコルの完全性は容易に検証できます。健全性については、前処理フェーズが信頼できるパーティによって実行されると仮定しているため、$i, j$は証明者から完全に隠されています。ランダムに選ばれたプロトコル$\Pi_p$が完全に正しくない場合、プロトコル$\Pi$は保証を提供しません。しかし、これは無視できる確率でしか起こりません。そうでなければ（すなわち、$\Pi_p$が完全に正しい場合）、ビューがすべて一貫していない場合、これは少なくとも$1/n^2$の確率で検出され、ビューが一貫している場合、完全な正当性により、出力は常に正しい（すなわち、0）です。ゼロ知識に関しては、ENCRYPT のセマンティックセキュリティにより、検証者は、証明者によって実際に送信されたメッセージと、暗号化キーを持つ実際のビュー$V_i, V_j$の暗号化と、残りの$n-2$個のビューのランダム値の暗号化を含むメッセージとを区別できません。したがって、このメッセージは、MPC シミュレータを使用してビュー$V_i, V_j$を生成することによってシミュレートできます。

上記のプロトコルの健全性は、入力$x$が$p$とは独立に選ばれるという仮定に依存します。（そうでなければ、ランダムな$\Pi_p$が高い確率で完全に正しいとは保証されません。）$x$の適応的な選択は、$p$の長さを（大まかに$|x|$、またはより一般的には$x$の記述サイズだけ）長くすることで対処できます。

脚注

1. Computer Science Department, Technion and UCLA. Email: yuvali@cs.technion.ac.il. Supported by BSF grant 2004361, ISF grant 1310/06, and NSF grants 0205594, 0430254, 0456717, 0627781, 0716835, 0716389. ↩

2. Computer Science Department, Technion. Email: eyalk@cs.technion.ac.il. Research supported by grant 1310/06 from the Israel Science Foundation and by grant 2002354 from the U.S.-Israel Binational Science Foundation. ↩

3. Computer Science Department and Department of Mathematics, UCLA. Email: rafail@cs.ucla.edu. Supported in part by IBM Faculty Award, Xerox Innovation Group Award, NSF grants 0430254, 0716835, 0716389, 0830803 and U.C. MICRO grant. ↩

4. Computer Science Department, UCLA. Email: sahai@cs.ucla.edu. Research supported in part from grants from the NSF ITR and Cybertrust programs (including grants 0627781, 0456717, 0830803, and 0205594), BSF grant 2004361, a subgrant from SRI as part of the Army Cyber-TA program, an equipment grant from Intel, an Alfred P. Sloan Foundation Fellowship, and an Okawa Foundation Research Grant. ↩

5. Y. Ishai, E. Kushilevitz, R. Ostrovsky, and A. Sahai. Zero-knowledge from secure multiparty computation. In Proc. 39th STOC, pages 21—30, 2007. ↩

6. S. Goldwasser, S. Micali, and C. Rackoff. The Knowledge Complexity of Interactive Proof Systems. SIAM J. Comput., Vol. 18, No. 1, pp. 186-208, 1989. ↩ ↩²

7. A. C. Yao. How to generate and exchange secrets. In Proc. 27th FOCS, pages 162-167, 1986. ↩ ↩²

8. O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game (extended abstract). In Proc. of 19th STOC, pages 218-229, 1987. ↩ ↩² ↩³ ↩⁴ ↩⁵

9. M. Ben-Or, S. Goldwasser, and A. Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation. In Proc. of 20th STOC, pages 1-10, 1988. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷

10. D. Chaum, C. Crépeau, and I. Damgard. Multiparty unconditionally secure protocols (extended abstract). In Proc. of 20th STOC, pages 11-19, 1988. ↩ ↩² ↩³

11. T. Rabin and M. Ben-Or. Verifiable secret sharing and multiparty protocols with honest majority. In Proc. 21st STOC, pages 73-85, 1989. ↩

12. O. Goldreich. Foundations of Cryptography: Basic Applications. Cambridge University Press, 2004. ↩ ↩² ↩³ ↩⁴ ↩⁵

13. O. Goldreich, S. Micali, and A. Wigderson. How to Prove all NP-Statements in Zero-Knowledge, and a Methodology of Cryptographic Protocol Design. In CRYPTO 1986, pages 171-185. ↩ ↩² ↩³ ↩⁴

14. O. Barkol and Y. Ishai. Secure Computation of Constant-Depth Circuits with Applications to Database Search Problems. In Proc. CRYPTO 2005, pages 395-411. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷ ↩⁸ ↩⁹

15. M. Bellare, S. Micali, and R. Ostrovsky. The (True) Complexity of Statistical Zero Knowledge. In Proc. of 22nd STOC, pages 494-502, 1990. ↩ ↩²

16. M. Rabin. How to Exchange Secrets by Oblivious Transfer. Tech. Memo TR-81, Aiken Computation Laboratory, Harvard U., 1981. ↩ ↩²

17. S. Even, O. Goldreich and A. Lempel. A Randomized Protocol for Signing Contracts. In Communications of the ACM, 28(6):637-647, 1985. ↩ ↩²

18. Y. T. Kalai and R. Raz. Succinct Non-Interactive Zero-Knowledge Proofs with Preprocessing for LOGSNP. In Proc. 47th FOCS, pages 355-366, 2006. ↩ ↩² ↩³

19. A. Razborov. Lower bounds for the size of circuits of bounded depth with basis {AND, XOR}. Math. Notes of the Academy of Science of the USSR, 41(4):333-—338, 1987. ↩ ↩²

20. R. Smolensky. Algebric methods in the theory of lower bound for boolean circuit complexity. In Proc. 19th STOC, pages 77-82, 1987. ↩ ↩²

21. R. Ostrovsky and A. Wigderson. One-Way Functions are Essential for Non-Trivial Zero-Knowledge. In Proc. of ISTCS 1993, pages 3-17. ↩

22. J. Kilian. A Note on Efficient Zero-Knowledge Proofs and Arguments (Extended Abstract). In Proc. STOC 1992, pages 723-732. ↩ ↩² ↩³

23. O. Goldreich and J. Hastad. On the Complexity of Interactive Proofs with Bounded Communication. Inf. Process. Lett. 67(4): 205-214, 1998. ↩

24. R. Cramer and I. Damgard. Linear Zero-Knowledge - A Note on Efficient Zero-Knowledge Proofs and Arguments. In Proc. STOC 1997, pages 436-445. ↩ ↩² ↩³

25. I. Damgard and Y. Ishai. Scalable Secure Multiparty Computation. In Proc. CRYPTO 2006, pages 501-520. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷ ↩⁸ ↩⁹

26. H. Chen and R. Cramer. Algebraic Geometric Secret Sharing Schemes and Secure Multi-Party Computations over Small Fields. In Proc. CRYPTO 2006, pages 521-536. ↩ ↩² ↩³ ↩⁴

27. M. Blum. Coin Flipping by Telephone - A Protocol for Solving Impossible Problems. In Proc. COMPCON 1982: 133-137. ↩ ↩²

28. R. Impagliazzo and S. Rudich. Limits on the Provable Consequences of One-way Permutations. In Proc. CRYPTO ’88, pages 8—26. ↩

29. J. Kilian. Founding Cryptography on Oblivious Transfer. In 20th STOC, pages 20-31, 1988. ↩

30. E. Kushilevitz, S. Micali, R. Ostrovsky. Reducibility and Completeness in Multi-Party Private Computations. In FOCS 1994, pages 478-489. ↩

31. J. Kilian, E. Kushilevitz, S. Micali, R. Ostrovsky. Reducibility and Completeness in Private Computations. In SIAM J. Comput. 29(4): 1189-1208 (2000). ↩

32. I. Damgard and Y. Ishai. Constant-Round Multiparty Computation Using a Black-Box Pseudorandom Generator. In CRYPTO 2005, pages 378-394. ↩

33. Y. Ishai, E. Kushilevitz, Y. Lindell, and E. Petrank. Black-box constructions for secure computation. In Proc. 38th STOC, pages 99-108, 2006. ↩

34. I. Haitner. Semi-Honest to Malicious Oblivious Transfer - The Black-Box Way. In Proc. 5th TCC, pages 412-426, 2008. ↩

35. J. Boyar, G. Brassard and R. Peralta. Subquadratic zero-knowledge. J. ACM, 42(6), pages 1169-1193, 1995. Earlier version in FOCS ’91. ↩ ↩²

36. J. Kilian and E. Petrank. An Efficient Noninteractive Zero-Knowledge Proof System for NP with General Assumptions. J. Cryptology 11(1), pages 1-27, 1998. ↩

37. J. Kilian, S. Micali, and R. Ostrovsky. Minimum Resource Zero-Knowledge Proofs. In FOCS 1989, pages 474-479. ↩ ↩²

38. R. Cramer and I. Damgard. Zero-Knowledge Proofs for Finite Field Arithmetic; or: Can Zero-Knowledge be for Free? In Proc. CRYPTO 1998, pages 424-441. ↩

39. J. Boyar, I. Damgard and R. Peralta. Short Non-interactive Cryptographic Proofs. J. Cryptology 13(4): 449-472 (2000). ↩ ↩²

40. J. Groth, R. Ostrovsky, and A. Sahai. Perfect Non-interactive Zero Knowledge for NP. In Proc. EUROCRYPT 2006, pages 339-358. ↩

41. S. Micali. Computationally Sound Proofs. SIAM Journal on Computing, 30(4):1253—1298, 2000. ↩ ↩²

42. O. Goldreich. Foundations of Cryptography: Basic Tools. Cambridge University Press, 2001. ↩ ↩² ↩³ ↩⁴ ↩⁵

43. R. Canetti. Security and composition of multiparty cryptographic protocols. In J. of Cryptology, 13(1), 2000. ↩ ↩² ↩³

44. M. Naor. Bit commitment using pseudorandomness. J. of Cryptology, 4:151—158, 1991. ↩ ↩² ↩³

45. J. Hastad, R. Impagliazzo, L. A. Levin, and M. Luby. A Pseudorandom Generator from any One-way Function. SIAM J. Comput. 28(4): 1364-1396 (1999). ↩ ↩² ↩³

46. U. Maurer. Secure Multi-party Computation Made Simple. In Proc. SCN 2002, pages 14-28. ↩

47. O. Goldreich and A. Kahan. How to Construct Constant-Round Zero-Knowledge Proof Systems for NP. J. Cryptology 9(3): 167-190 (1996) ↩

48. A. Rosen. A Note on Constant Round Zero Knowledge Proofs for NP. In Proc. 1st TCC, pages 191-202, 2004. ↩

49. M. Prabhakaran, A. Rosen, and A. Sahai. Concurrent Zero-Knowledge with Logarithmic Round Complexity. In Proc. of FOCS 2002, pages 366-375. ↩

50. I. Haitner and O. Reingold. Statistically-Hiding Commitment from Any One-Way Function. In Proc. 39th STOC, pages 1-10, 2007. ↩

51. A. Shamir. How to share a secret. Commun. ACM, 22(6):612—-613, June 1979. ↩

52. M. K. Franklin and M. Yung. Communication Complexity of Secure Computation. In Proc. of STOC 1992, pages 699-710. ↩ ↩²

53. D. Harnik, Y. Ishai, E. Kushilevitz, and J.B. Nielsen. OT-Combiners from Secure Computation. In Proc. 5th TCC, pages 393-411, 2008. ↩

54. Y. Ishai, M. Prabhakaran, and A. Sahai. Founding cryptography on oblivious transfer — efficiently. In Proc. CRYPTO 2008, to appear. ↩

55. Y. T. Kalai and R. Raz. Interactive PCP. In Proc. 35th ICALP, pages 536-547, 2008. Earlier version: Electronic Colloquium on Computational Complexity (ECCC) Report TR07-031, 2007. ↩

56. S. Goldwasser, Y. T. Kalai, and G. Rothblum. Delegating computation: interactive proofs for muggles. In Proc. 40th STOC, pages 113-122, 2008. ↩