論文翻訳: On the Size of Pairing-based Non-interactive Arguments^$\star$

2019年12月1日 2016年の論文 #zk-SNARK

Jenes Groth^$\star\star$
Univercity college London, UK
j.groth@ucl.ac.jk

Abstract

非対話型のアーギュメントは証明者が検証者にあるステートメントが真実であることを革新させることができる。最近、サイズが小さく検証の複雑性が低い非常に効率的な非対話型アーギュメント、いわゆる簡潔な (succinct) 非対話型アーギュメント (SNARGs; succinct non-interactive arguments) 及び簡潔な知識日対話型アーギュメント (SNARKs; succinct non-interactive arguments of knowledge) の構築に関して理論と実践の両方で多くの進展があった。

SNARG の構築の多くはペアリングベースの暗号に依存している。これらの構成では、証明は多数の群要素で構成され、検証は多数のペアリング積方程式のチェックで構成されている。この論文で取り上げる問題はペアリングベースの SNARG がいかに効率的であるかということである。

我々の最初のコントリビュートは NP 完全言語である算術回路充足可能性 (arithmetic circuit satisfiability) に対する (前処理) SNARK である。我々の SNARK はより高い効率のために非対称ペアリングを用いて研究を行っている。証明は 3 つの群要素のみであり、検証においては合計 3 つのペアリングを用いて単一ペアリング積方程式をチェックすることで構成される。我々の SNARK はゼロ知識であり、証明者が証明するために使う prover について何も明らかにしない。

我々の二番目のコントリビュートとして、2 移動線形対話型証明 (2-move linear interactive proof) が線形決定手順 (linear decision procedure) を持てないことを示すことで Bitansky, Chiesa, Ishai, Ostrovsky and Paneth (TCC 2013) における未解決の問題に応えている。このことから、証明者と検証者が一般的な非対称双線形群演算を使用する SNARG は単一の群要素で構成できないことが分かる。これによりペアリングベースの SNARG の最初の下限が得られる。この下限を拡張して 2 つの群要素の SNARG を除外できるかは興味ある未解決問題であり、これは 3 要素構成の最適性を証明する。

Abstract
1 導入
1. 1.1 我々の構造
2 予備知識
3 非対話型アーギュメントの構築
1. 3.1 二次算術プログラムの非対話型線形証明 [under construction]
2. 3.2 NIZK arguments for quadratic arithmetic programs
4 Lower bounds for non-interactive arguments
1. 4.1 Linear interactive proofs cannot have linear decision procedures
2. 4.2 Lower bound for the size of generic pairing-based non-interactive arguments
acknowledgements
References
翻訳抄

キーワード : SNARKs, non-interactive zero-knowledge arguments / 非対話型ゼロ知識アーギュメント, linear interactive proofs / 線形対話型証明, quadratic arithmetic programs / 二次演算プログラム, bilinear groups / 双線形群

^$\star$ (c) IACR 2016. This article is a minor revision of the version published by Springer-Verlag at http://dx.doi.org/10.1007/978-3-662-49896-5_11
^$\star\star$ The research leading to these results has received funding from the European Research Council under the European Union’s Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement n. 307937 and the Engineering and Physical Sciences Research Council grant EP/J009520/1. This work was done in part while the author was visiting the Simons Institute for the Theory of Computing, supported by the Simons Foundation and by the DIMACS/Simons Collaboration in Cryptography through NSF grant #CNS-1523467.

1 導入

Goldwasser, Micali, Rackoff [GMR89] は、証明者がそれ以上の情報を明かすこと無くステートメントが真であることを検証者が確証できるようにするゼロ知識証明を導入した。これらには 3 つのコアプロパティが存在する:

完全性 (completeness): ステートメントと証人 (witness) が与えられれば、証明者は検証者に確証させることができる。
健全性 (soundness): 悪意のある証明者は、検証者に虚偽のステートメントを確証させることができない。
ゼロ知識 (zero-knowledge): 証明はステートメントの事実以外の何も明らかにせず、特に証明者の証人は明らかにしない。

Blum, Feldman, and Mical [BFM88] はこの概念を共通参照情報モデル (common reference string model) における非対話型ゼロ知識 (NIZK) 証明に拡張した。NIZK 証明はデジタル署名や CCA-セキュア公開鍵暗号などの非対話型暗号化スキームの構築に有用である。

通信性はゼロ知識証明に対する重要なパフォーマンスパラメータである。Kilian [Kil92] は証明されるステートメントのサイズより小さいビットを送る最初の準線形通信ゼロ知識アーギュメントを与えた。Micali [Mic00] は通信効率の良いアーギュメントの証明者に暗号関数を使用して検証者のチャレンジを計算させることにより準線形サイズのアーギュメントを提案した。そして Kilian [Kil95] で述べられているように、これは対話的なアーギュメントが公開コインでありゼロ知識である場合、これは準線形サイズの NIZK 証明を導く。

Groth, Ostrovsky and Sahai [GOS12, GOS06, Gro06, GS12] はペアリングに基づく NIZK 証明を導入し、標準的な過程に基づく最初の線形サイズの証明をもたらした。Groth [Gro10] はこれらの手法と対話型ゼロ知識アーギュメント [Gro09] のアイディアと組み合わせ、最初の一定サイズの NIZK アーギュメントを与えた。Lipmaa [Lip12] は共通参照情報のサイズを小さくするために progression-free 集合に基づくだいたい構造を使用した。

Groth の定数サイズ NIZK アーギュメントは多項式の集合を構築しペアリングを使用してこれらの方程式を効率的に検証することに基づいている。Gennaro, Gentry, Parno and Raykova [GGPR13] は、ステートメントと証人のサイズに比例する共通の参照列を持つペアリングベースの NIZK アーギュメントを生成するラグランジュ補間多項式に基づく、洞察に満ちた多項式の構築を発見した。彼らは、ブール回路の充足可能性を証明するための二次スパンプログラムと、算術回路の充足可能性を証明するための二次算術プログラムの 2 種類の多項式を与えた。Lipmaa [Lip13] 誤り訂正符号を用いたより効率的な二次スパンプログラムを提案し、Danezis, Fournet, Groth and Kohlweiss [DFGK14] は二次スパンプログラムをブール回路充足可能性に対する 4 つの群要素で構成されr NIZK アーギュメントを与える平方スパンプログラムに改良した。

実装に関する興味深い研究は、上記の理論的進歩に続いている [PHGR13, BCG+13, BFR+13, BCTV14b, KPP+14, BBFR15, CTV15, WSR+15, WSR+15, CFH+15, SVdV16]。最も効率的な実装は Gannaro ら [GGPR13] の二次算術プログラムアプローチを改良し、証明されるべきステートメントと等価な適切な二次算術プログラムを生成するコンパイラとの組み合わせである; libsnark [BCTV14b, BSCG+14] にも [DFGK14] に基づく NIZK アーギュメントが含まれている。

効率的な非対話型アーギュメントを構築する強力な動機の一つは検証可能な計算である。クライアントは複雑な計算タスクをクラウド内のサーバにアウトソーシングし、その結果を得ることができる。サーバは計算が正しいことをクライアントに確証させるための正確性の非対話的なアーギュメントを結果に含めることができる。ただし、検証車は多くの計算リソースを持たないことから、アーギュメントがコンパクトで検証のための計算が歩い場合、つまりそれが簡潔な非対話型アーギュメント (SNARG) または簡潔な非対話型知識アーギュメント (SNARK) である場合にのみ意味を持つ。ペアリングベースの SNARG は検証者にとっては効率的だが、アウトソーシングされた計算 [WB15, Wal15] での使用を保証するには証明者の計算オーバーヘッドは依然として桁違いに大きくさらなる効率改善を必要とする。しかしゼロ知識 SNARK は現在の状態でもプライベートデータに関するステートメントを証明するときに既に使用されている。ゼロ知識 SNARK は具体的に仮想通貨 Pinocchio coin [DFKP13] と Zerocach [BCG+14] の提案の重要な要素である。

ペアリングベースの NIZK アーギュメントの開発と並行して SNARK の理解に関する興味深い研究が行われていた。Gentry and Wichs [GW11] は SNARK が偽造不可能な仮定に必ず依存しなければならないことを示し、Bitansky ら [BCCT12] は抽出可能な衝突耐性ハッシュ関数が存在する場合にのみ検証者 SNARK が存在することを証明した。効率の観点で特に興味深いのは SNARK がどのように構成されているかの一連の研究 [Val08, BCCT13, BCTV14a] である。これらは、特に長い参照列を持つ前処理 SNARK を使用して、短い共通参照情報を持つ完全に簡潔な SNARK を構築できることを示している。

Bitansky ら [BCI+13] は体要素の線形符号化に依存する SNARK の中小モデルを提供している。線形相互作用証明 (LIPs; linear interactive proofs) と呼ばれる情報理論的フレームワークは、証明者がメッセージの計算において線形演算の使用に限定される証明システムを捕らえている。それらはペアリングベースの手法を使用して、2-move LIP を公に検証可能な SNARK へ、または加法準同型暗号化手法を使用して指定された検証者へ一般的変換を与える。

1.1 我々の構造

簡潔な NIZK. 証明が 3 つの群要素だけで構成される算術回路充足可能性に対する NIZK アーギュメントを作成する。証明の小ささに加えて検証も簡単である。検証者は単にステートメントのサイズに比例するべき乗の数を計算し、3 つのペアリングしかないペアリング積方程式を検証するだけである。我々のこの構造は、最も効率的なペアリングであるタイプ III ペアリングなど、あらゆるタイプのペアリングでインスタンス化することができる。

アーギュメントは正確な完全性と正確なゼロ知識を持っている。健全性に関して我々は積極的な姿勢を取り、最適な性能を得るために一般的な双線形群モデル [Sho97, Nec94] のセキュリティ証明に依存する。この立場は、標準的な偽造可能仮定 (standard falsifiable assumption) に基づいて SNARG を除外する Gentry and Wichs [GW11] によって正当化される。しかし Abe, Groth, Ohkubo and Tibouchi [AGOT14] に従い、対象ペアリング設定でセキュアな構造であることを証明することで、暗号解析に対するヘッジを提供する。最適な効率を得るためには、非対称設定において我々の NIZK アーギュメントを使用することは理にかなっているが、対称設定においてセキュリティ証明を提供することにより我々は付加的なセキュリティを得ている: 暗号解読の進歩によりソース群間でこれまでに知られていなかった効率的に計算可能な銅系製が得られたとしても、これは必ずしも我々のスキームの破綻に繋がるものではない。従って、我々は最適効率と最適一般双線形群弾性の両方をもたらすような、任意の型のペアリングでインスタンス化できる統一 NIZK アーギュメントを得ている。

**Table 1.** $\ell$ -bit ステートメント、 $m$ ワイヤー、 $n$ fan-in 2 論理ゲートを使用したブール回路の充足可能性の比較。表記: $\mathbb{G}$ は群要素、 $M$ は乗算、 $E$ はべき乗、 $P$ はペアリングを意味する。それぞれ関連する群の添え字を持つ。 $\mathbb{G}_1$ の $m+2n$ 要素と $\mathbb{G}_2$ の $n$ 要素の CRS サイズを得ることは可能だが、証明者の計算を減らすために CRS に事前計算された値を含めることを選択した。Sect. 3.2 参照。
	CRS サイズ	証明サイズ	証明者の計算	検証者の計算	PPE
[DFGK14]	$2m+n-2\ell \mathbb{G}_1$ , $m + n - \ell \mathbb{G}_2$	$3 \mathbb{G}_1$ , $1\mathbb{G}_2$	$m + n - \ell E_1$	$\ell M_1$ , $6P$	3
この研究	$3m+n\mathbb{G}_1$ , $m\mathbb{G}_2$	$2 \mathbb{G}_1$ , $1\mathbb{G}_2$	$nE_1$	$\ell M_1$ , $3P$	1

**Table 2**. $\ell$ -要素ステートメント、 $m$ ワイヤー、 $n$ 乗算ゲートを使用した算術回路の充足可能性の比較。表記: $\mathbb{G}$ は群要素、 $E$ はべき乗、 $P$ はペアリングを意味する。最初の 2 行の対称ペアリング同士と後の 2 行の非対称ペアリング同士を比較する。
	CRS サイズ	証明サイズ	証明者の計算	検証者の計算	PPE
[PHGR13]	$7m+n-2\ell\mathbb{G}$	$8\mathbb{G}$	$7m+n-2\ell E$	$\ell E$ , $11P$	5
この研究	$m+2n\mathbb{G}$	$3\mathbb{G}$	$m+3n-\ell E$	$\ell E$ , $3P$	1
[BCTV14a]	$6m+n+\ell\mathbb{G}_1$ , $m\mathbb{G}_2$	$7\mathbb{G}_1$ , $1\mathbb{G}_2$	$6m+n-\ell E_1$ , $mE_2$	$\ell E_1$ , $12P$	5
この研究	$m+2n\mathbb{G}_1$ , $n\mathbb{G}_2$	$2\mathbb{G}_1$ , $1\mathbb{G}_2$	$m+3n-\ell E_1$ , $nE_2$	$\ell E_1$ , $3P$	1

共通参照情報 (CRS) サイズ、証明サイズ、証明者の計算、検証者の計算、証明を計算するために使用したペアリング積方程式の数について、ブール回路充足可能性を Table 1 に、算術回路充足可能性を Table 2 に示した。我々は全ての効率パラメータにおいて最新の技術よりも優れてたパフォーマンスを発揮している。

どちらの比較でも各ゲートは出力ワイヤーを有するためワイヤーの数は $m \ge n$ とゲートの数を超えている。典型的なケースではステートメントのサイズ $\ell$ は $m$ や $n$ と比べて小さくなるだろう。どちらの表でも証明する関係を表すサイズを除外している。ブール回路充足可能性の場合は任意の fan-in 2 論理ゲートを考慮した。演算回路充足可能性の場合は各入力因子が他のワイヤーの重み付き合計となることができる fan-in 2 論理ゲートを使用する。各乗算ゲート入力は一定数のワイヤーに依存すると想定している; そうしないと関係自体を評価するコストが後続の証明生成コストを上回る可能性がある。

我々は [PHGR13] が $\mathbb{G}_1 = \mathbb{G}_2$ の対称双線形群を使用することに注目し、共通参照列に $n$ 個の要素を保存する我々のスキームの対称双線形群と比較している。しかし Pinocchio と呼ばれるそれらのシステムの実装では効率を向上させるために非対称ペアリングが使用されている。このような SNARK の使用については libsnark ライブラリで実装されている [BCTV14a] を参照。

Size Matters(サイズ問題). 証明サイズの 3 つの群要素への削減と検証時間の削減はそれ自体良いことだが、SNARK を構成する際には特に重要であることを強調したい。[BCCT13, BCTV14a] は、長い CRS を持つ前処理 SNARK は短い CRS¹ を持つ完全に簡潔な SNARK を生成するように構成できることを示している。変換はステートメントをより小さな断片に細分化し、各断片がそれ自身で正しいことを証明し、そして断片が正しく共に適合していることを示す他の証明の知識の証明を再帰的に構築する。証明の再帰的構成では、証明が小さく検証が容易な場合、得られるステートメント "検証式を満たす証明が存在する..." (there exists a proof satisfying the verification equation...) 自体が小さくなるため非常に有用である。従って我々の SNARK では検証手順がより効率的になるため、証明者の計算量がより低く、再帰的構成のステートメントがより小さいという事実の両方が得られる。Chiesa and Virza [CV16] は [BCTV14a] の実装で SNARK を使用することで 4～5 倍の速度向上を報告している。

Technique(技法). 文献の全てのペアリングベースの SNARK は一般的な群操作を使用して証明者が多数の群要素を計算し、検証者が多数のペアリング積方程式を用いて証明をチェックするという共通のパラダイムに従っている。Bitansky ら [BCI+13] は線形対話型証明 (LIP) の定義を通じてこのパラダイムを形式化した。線形対話型証明は有限体上で機能し、証明者と検証者のメッセージは体要素のベクトルで構成される。さらにこれは証明者は線形操作のみを使用してメッセージを計算する必要がある。適切な 2-move LIP が得られたらペアリングベースの暗号を使用して "指数で" 方程式を実行することにより LIP を SNARK にコンパイルできる。効率向上の第一の原因は、検証者が 3 つの体要素のみを送信する演算回路用の LIP システムを設計することである。これに対し [GGPR13, PHGR13] による二次演算プログラムは証明者が 4 つの体要素を送信する LIP に相当する。

過去の研究と比較した効率向上の第二の原因は LIP のより積極的なコンパイルである。Bitansky ら [BCI+13] は対称双線形群の設定での変換を提案している。この場合、各体要素は 2 つの群要素にコンパイルされる。次にそれらは指数仮定の知識を用いて、証明者が関連する体要素を知っていると主張する。少々保守的な選択肢は各体要素を単一の群要素にコンパイルすることである。体要素ごとに単一の群要素でコンパイルすると効率は向上するが、もはや指数仮定の知識を使用できなくなるため、セキュリティ一般群モデル [Sho97, BBG05] のみを証明する。またこれら両極端のいずれかを選択することも可能であり、例えば Parno ら [PHGR13] は 4 つの体要素を持つ LIP があり 7 つの群要素にコンパイルされる。要約するとこの論文では最大の効率を選択し、LIP の各体要素を単一の群要素にコンパイルし、一般群モデルにおけるセキュリティを議論した。

我々は対称双線形群よりも効率が高い非対称双線形群の研究を好んでいる。つまり LIP で証明者が送信する体要素の数や、どの程度積極的なコンパイルを使用するかの選択よりもストーリーが重要であることを意味している。非対称双線形群で研究する場合、体要素は最初のソース群か二番目のソース群、またはその両方で指数として表示することができる。我々の LIP は証明のサイズを合計で 3 つの群要素に最小化するために、単一のソース群要素にコンパイルされるよう慎重に設計されている。

下限 (lower bounds). これまで以上に効率的な非対話型アーギュメントに向けて最小の証明サイズが何かを尋ねることは自然である。ペアリングベースの SNARG が単一の群要素の証明と一緒に存在できないことを示す。この結果は検証者に線形決定手順を持つ LIP があるかどうかという Bitansky ら [BCI+13] が提起した未解決の問題に関係する。このような線形決定手順は非常に有用であろう。例えば ElGamal 暗号に基づく SNARG の構築が可能になるかもしれない。

我々は線形決定手順を持つ LIP が存在しないことを証明することでこの未解決問題に否定的に回答する。この結果、ペアリングベースの SNARG は証明の群要素をペアリングして決定手順を線形ではなく二次にしなければならない。従って、非対称双線形群で研究を行う場合、そのようなペアリングを行うために両方のソース群で要素を持つ必要がある。これは、それがゼロ知識であるかにかかわらず 1 群要素の SNARG の存在を排除し、NIZK アーギュメントが最適な証明サイズに近いことを示している。各ソース群 $\mathbb{G}_1$ と $\mathbb{G}_2$ から正確に 1 つの要素を使用して SNARG を構築するか、またはそのような SNARG の存在を排除することでギャップを完全に埋めることは依然として興味深い未解決の問題である。

¹ 他の SNARK の検証に対応するステートメントを記述する際に、構成が双線形群の具体的なインスタンス化を必要とするため、一般的な敵対者に対する健全性は構成の下で保持されないことに言及する ([Val08] でも示される問題)。我々の SNARK が標準モデルにおける知識健全であるなら、再帰を使用して完全に簡潔な SNARK を取得できると言うことを述べている。

2 予備知識

2 つの関数 $f,g: \mathbb{N} \to [0,1]$ が与えられたとき、 $|f(\lambda)-g(\lambda)|=\lambda^{-\omega(1)}$ のとき $f(\lambda) \approx g(\lambda)$ と書く。 $f(\lambda) \approx 0$ の時 $f$ は無視できる (negligible) と言い、 $f(\lambda) \approx 1$ の時 $f$ は圧倒的である (overwhelming) と言う。ここでは $\lambda$ をセキュリティパラメータとして使用し、 $\lambda$ が大きくなるにつれてセキュリティが強化されることを直感的に期待する。

入力 $x$ 上のアルゴリズム $A$ とランダム性 $r$ が $y$ を出力するとき $y = A(x;r)$ と表す。ランダムにランダム性 $r$ を選び、 $y=A(x;r)$ と設定する処理を $y \leftarrow A(x)$ と表す。また集合 $S$ から一様にランダムに $y$ をサンプリングすることを $y \leftarrow S$ を表す。我々は $\mathbb{Z}_p$ のような集合から一様にランダムにサンプリングすることが可能であると仮定する。

Abe と Fehr [AF07] に従い、入力 $x$ の $\mathcal{A}$ が $y$ を出力し、(ランダムコインを含む) 同じ入力の $\mathcal{X}_\mathcal{A}$ が $z$ を出力するとき $(y;z) \leftarrow (\mathcal{A} \ || \ \mathcal{X}_\mathcal{A})(x)$ と表す。

2.1 双線形群

我々は以下の特性を持つ双線形群 $(p,\mathbb{G}_1,\mathbb{G}_2,\mathbb{G}_T,e,g,h)$ 上で操作を行う。

$\mathbb{G}_1$ , $\mathbb{G}_2$ , $\mathbb{G}_T$ は素数位数 $p$ の群である。
ペアリング $e:\mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$ は双線形写像である。
$g$ は $\mathbb{G}_1$ の生成元であり、 $h$ は $\mathbb{G}_2$ の生成元である。また $e(g,h)$ は $\mathbb{G}_T$ の生成元である。
群操作の計算、双線形写像の評価、群のメンバーシップの決定、群要素の等価性の決定、群の生成元のサンプリングに対する効率的なアルゴリズムが存在する。これらを一般群操作 (generic group operations) と呼ぶ。

双線形群の設定は $\mathbb{G}_1=\mathbb{G}_2$ の対称双線形群と、 $\mathbb{G}_1\neq \mathbb{G}_2$ の非対称線形群の両方を設定する多くの方法が存在する。Galbraith, Paterson and Smart [GPS08] は双線形群を $\mathbb{G}_1 = \mathbb{G}_2$ の Type I、効率的に計算可能で非自明な準同形 $\Psi : \mathbb{G}_2 \to \mathbb{G}_1$ が存在する Type II、および $\mathbb{G}_1$ と $\mathbb{G}_2$ の間にそのような効率的に計算可能な準同形が存在しない Type III に分類している。Type III 双線形群は双線形群の中でも最も効率的なタイプであるため実際のアプリケーションに最も適している。我々は Type III 双線形群におけるペアリングベースの SNARG の下限を与える。一方で我々の構造は 3 タイプ全ての双線形群でインスタンス化することができる。

群要素を離散対数で表す表記法が有用である。我々は離散対数の計算が難しいことを強調し、この表記法が目的の表現には便利である。 $g^a$ を $[a]_1$ 、 $h^b$ を $[b]_2$ 、および $e(g,h)^c$ を $[c]_T$ と表記する。この表記法では $g=[1]_1$ 、 $h=[1]_2$ 、および $e(g,h)=[1]_T$ で単位元は $[0]_1$ 、 $[0]_2$ および $[0]_T$ である。群の離散対数表現を使用すると、全ての群で加算表記法を使用するのが自然であるため、例えば $[a]_T + [b]_T = [a+b]_T$ となる。群要素のベクトルは $[\vector{a}]_i$ として表される。我々の表記法では標準の線形代数表記法を使用して自然操作を定義できるため、 $[\vector{a}]_i+[\vector{b}]_i=[\vector{a}+\vector{b}]_i$ は $\vector{a}$ と $\vector{b}$ が同じ次元であり、適切な次元が $A[\vector{b}]_i = [A\vector{b}]_i$ を定義すると仮定する。 $n$ 個の群要素の 2 つのベクトル $[\vector{a}]_1$ と $[\vector{b}]_2$ が与えられた場合、それらのドット積をペアリング $e$ を用いて効率的に計算できる $[\vector{a}]_1 \cdot [\vector{b}]_2 = [\vector{a} \cdot \vector{b}]_T$ として定義する。

群要素を生成および操作するために一般群操作のみを使用するならばアルゴリズムは一般 (generic) であると言う。Shoup [Sho97] は実際の群要素の代わりにランダムな単射エンコーディング $[\cdot]_i$ を考慮することによって一般群モデルを形式化した。そして一般群操作はアルゴリズムがアクセスするオラクルを介して処理される。例えば $({\rm add},[a]_i,[b]_i)$ は $[a+b]_i$ を返すことができる。エンコードがランダムであるため、一般アルゴリズムは一般群オラクルを介してのみ意味のある操作を実行することができる。この一つの意味は、もし入力 $[\vector{a}]_1$ があり要素 $[\vector{b}]$ を返す場合、 $\mathbb{G}_1$ で行われた追加クエリーをチェックすることで $\vector{b}=M\vector{a}$ となるような行列 $M$ を効率的に推測できる。 $\mathbb{G}_2$ でも同様だが、 $\mathbb{G}_T$ ではペアリング操作から計算される要素もあるが、任意の出力要素を明示的な二次多項式として入力に書き込むことができる。

2.2 知識の非対話型ゼロ知識アーギュメント

$\mathcal{R}$ を単項のセキュリティパラメータ $\lambda$ が与えられた多項時間で決定可能な二項関係 $R$ を返す関係ジェネレータとする。ペア $(\phi,\omega) \in R$ に対して $\phi$ をステートメント、 $\omega$ を証拠 (witness) と呼ぶ。与えられた $1^\lambda$ で関係ジェネレータが出力する可能性のある関係 $R$ の集合を $\mathcal{R}_\lambda$ と定義する。以下では表記を単純化するために $R$ の記述から $\lambda$ を推定できると仮定する。関係ジェネレータは敵対者に与えられるあるサイド情報、補助入力 $z$ を出力することもできる。 $\mathcal{R}$ に対する効率的で公に検証可能な非対話型アーギュメントは確率多項式アルゴリズム ( ${\sf Setup}$ , ${\sf Prove}$ , ${\sf Vfy}$ , ${\sf Sim}$ ) の 4 部分から成る。

$(\sigma,\tau) \leftarrow {\sf Setup}(R)$ : セットアップは共通参照情報 $\sigma$ と関係 $R$ に対するシミュレーショントラップドア $\tau$ を生成する。
$\pi \leftarrow {\sf Prove}(R,\sigma,\phi,\omega)$ : 証明者アルゴリズムは入力に共通参照情報 $\sigma$ および $(\phi,\omega) \in R$ を取りアーギュメント $\pi$ を返す。
$0/1 \leftarrow {\sf Vfy}(R,\sigma,\phi,\pi)$ : 検証アルゴリズムは共通参照情報 $\sigma$ とステートメント $\phi$ 、アーギュメント $\pi$ を入力とし、0 (拒否) または 1 (受け入れ) を返す。
$\pi \leftarrow {\sf Sim}(R,\tau,\phi)$ : シミュレータは入力としてシミュレーショントラップドアとステートメント $\phi$ を取りアーギュメント $\pi$ を返す。

定義 1. 以下で定義するように、もし正確な完全性と計算上の健全性を備えているのであれば $({\sf Setup}$ , ${\sf Prove}$ , ${\sf Vfy})$ は $\mathcal{R}$ の非対話型アーギュメントであると言う。

定義 2. 以下で定義するように、正確な完全性 (perfect completeness)、正確なゼロ知識 (perfect zero-knowledge)、および計算知識の健全性 (computational soundness) を備えているのであれば $({\sf Setup}$ , ${\sf Prove}$ , ${\sf Vfy}$ , ${\sf Sim})$ は $\mathcal{R}$ の知識の正確な非対話型ゼロ知識アーギュメントであると言う。

Perfect Completeness(正確な完全性). 完全性は、真のステートメントが与えられれば正直な証明者は正直な検証者を説得できることを意味する。全ての $\lambda \in \mathbb{N}$ , $R \in \mathcal{R}_\lambda$ , $(\phi,\omega) \in R$ に対して ${\rm Pr}\left[ (\sigma,\tau) \leftarrow {\sf Setup}(R); \pi \leftarrow {\sf Prove}(R,\sigma,\phi,\omega): {\sf Vfy}(R,\sigma,\phi,\pi) = 1 \right] = 1$ となる。

Perfect Zero-Knowledge(正確なゼロ知識). ステートメントの事実以外の情報を漏らさなければ、アーギュメントはゼロ知識である。全ての $\lambda \in \mathbb{N}$ 、 $(R,z) \leftarrow \mathcal{R}(1^\lambda)$ 、 $(\phi,\omega) \in R$ および全ての敵対者 $\mathcal{A}$ に対して $\begin{eqnarray*} & & {\sf Pr}\left[ (\sigma,\tau) \leftarrow {\sf Setup}(R); \pi \leftarrow {\sf Prove}(R,\sigma,\phi,\omega): \mathcal{A}(R,z,\sigma,\tau,\pi) = 1 \right] \\ & = & {\sf Pr}\left[ (\sigma,\tau) \leftarrow {\sf Setup}(R); \pi \leftarrow {\sf sim}(R,\tau,\phi): \mathcal{A}(R,z,\sigma,\tau,\pi) = 1 \right] \end{eqnarray*}$ であれば $({\sf Setup}$ , ${\sf Prove}$ , ${\sf Vfy}$ , ${\sf Sim})$ は正確なゼロ知識である。

Computational Soundness(計算の健全性). 虚偽のステートメントを証明することができないのであれば、つまり証拠が存在しなければ検証者を確証させることができないのであれば $({\sf Setup}$ , ${\sf Prove}$ , ${\sf Vfy}$ , ${\sf Sim})$ は健全である。 $R$ に一致する証拠が存在するステートメントで構成される言語を $L_R$ とする。正式には、全ての非均一多項式時間敵対者 $\mathcal{A}$ に対して ${\rm Pr}\left[ \begin{array}{cc} (R,z) \leftarrow \mathcal{R}(1^\lambda); (\sigma,\tau) \leftarrow {\sf Setup}(R); (\phi,\pi) \leftarrow \mathcal{A}(R,z,\sigma): \\ \phi \not\in L_R \ \mbox{and} \ {\sf Vfy}(R,\sigma,\phi,\pi) = 1 \end{array} \right] \approx 0$ である。

Computational Knowledge Soundness(計算知識の健全性). 健全性の概念を強化し、敵対者が有効なアーギュメントを生成するたびに証拠を計算できる抽出者 (extractor) が存在するのであれば $({\sf Setup}$ , ${\sf Prove}$ , ${\sf Vfy}$ , ${\sf Sim})$ は知識のアーギュメントである。抽出者は任意のランダムコインを含む敵対者の状態に完全にアクセスできる。正式には、全ての非均一多項時間敵対者 $\mathcal{A}$ に対して、次のような非均一多項時間抽出者 $\mathcal{X}_\mathcal{A}$ が存在しなければならない。 ${\rm Pr}\left[ \begin{array}{cc} (R,z) \leftarrow \mathcal{R}(1^\lambda); (\sigma,\tau) \leftarrow {\sf Setup}(R); ((\phi,\pi); \omega) \leftarrow (\mathcal{A} \ || \ \mathcal{X}_\mathcal{A})(R,z,\sigma): \\ (\phi,\omega) \not\in R \ \mbox{and} \ {\sf Vfy}(R,\sigma,\phi,\pi) = 1 \end{array} \right] \approx 0$

Public Verifiability(公開検証可能性) and Designated Verifier Proofs(指定された検証者の証明). $\sigma$ を証明者と検証者が使用する 2 つの部分 $\sigma_P$ と $\sigma_V$ に分割することで非対話型アーギュメントの定義を自然に一般化できる。 $\sigma_P$ から $\sigma_V$ を推定できるのであれば非対話型アーギュメントは公開検証が可能である。そうでないのであれば、指定された検証者アーギュメントとして参照する。指定された検証者アーギュメントの場合、敵対者が $\sigma_P$ のみを参照し $\sigma_V$ は参照しないように健全性と知識健全性を緩和することができる。

SNARGs and SNARKs. 検証者が多項式時間 $\lambda+|\phi|$ で実行され証明のサイズが $\lambda$ の多項式となる非対話型アーギュメントは、もし健全なら前処理 (preprocessing) 簡潔非対話型アーギュメント (SNARG)、知識健全なら前処理簡潔知識アーギュメント (SNARK) と言う。共通参照情報も $\lambda$ の多項式に制限されるなら非対話型アーギュメントは完全に簡潔な SNARG または SNARK と言う。Bitansky ら [BCCT13] は前処理 SNARK が完全に簡潔な SNARK を生成できるように構成できることを示している。この論文の焦点は共通参照情報が長い可能性のある前処理 SNARK である。

Bening Relation Generators(良性関係ジェネレータ). Bitansky ら [BCPR14] は識別不能性の難読化が全ての候補 SNARK に対して証拠を抽出することなく敵対者が有効な証拠を作成できる補助的な出力分布があることを意味することを示している。パブリックコインの入力難読化やその他の暗号化の仮定も異なると仮定すると、Boyle and Pass [BP15] はこの不可能性を強化してすべての候補 SNARK の証拠抽出を無効にする補助的な入力分布があることを示している。ただしこれらの反例は特定の補助手入力分布に依存している。従って、関係と補助入力が我々の構成する SNARK が知識健全であるような方法で分布しているという意味で、以降は関係ジェネレータが良性であると想定する。

2.3 二次算術プログラム

有限体 $\mathbb{F}$ 上の加算ゲートと乗算ゲートで構成される算術回路について考える。入出力ワイヤーの一部をステートメントを特定するものとして指定し、回路内の残りのワイヤーを使用して証拠を定義できる。これにより、算術回路を満足する、つまり指定された入出力ワイヤーと一致するステートメントワイヤーと証拠ワイヤーで構成される 2 値 (binary) 関係 $R$ が得られる。

算術回路を一般化することで変数の集合に対する方程式で記述される関係に興味が湧くかも知れない。一部の変数はステートメントに対応している。残りの変数は証拠に対応している。この関係はすべての方程式を満足するステートメントと証拠で構成される。方程式は $a_0=a$ とする変数 $a_1,\ldots,a_m \in \mathbb{F}$ と $\sum a_i u_{i,q} \cdot \sum a_i v_{i,q} = \sum a_i w_{i,q}$ 上に形成される。ここで $u_{i,q}$ , $v_{i,q}$ , $w_{i,q}$ は $q$ 番目の方程式を特定する $\mathbb{F}$ における定数である。

加算ゲートと乗算ゲートはこのような方程式の特殊なケースであるため、このような算術的に制限されたシステムが実際に算術回路を一般化することを観測している。例えば乗算ゲートは $a_i \cdot a_j = a_k$ と記述することができる ( $u_i=1$ , $v_j=1$ , $w_k=1$ を使用して残りのゲートの定数を 0 に設定する)。加算ゲートは方程式を定義する和で自由に処理される。つまり $a_i + a_j = a_k$ で $a_k$ が $a_\ell$ で乗算されている場合、単に $(a_i + a_j) \cdot a_\ell$ と書くだけで $a_k$ の計算をスキップすることができる。

Gennaro, Gentry, Parno and Raykova [GGPR13] に従い、我々は $\mathbb{F}$ が十分に大きいと仮定して算術制約の集合を二次算術プログラムとして再定式化する。 $n$ 個の方程式が与えられた場合、に二の異なる $r_1, \ldots,r_n \in \mathbb{F}$ を選択し $t(x)=\prod_{q=1}^n(x-r_q)$ を定義する。さらに $i=0,\ldots,m$ , $q=1,\ldots,n$ に対して $u_i(r_q)=u_{i,q} \ \ v_i(r_q) = v_{i,q} \ \ w_i(r_q)=w_{i,q}$ となるように $u_i(x)$ , $v_i(x)$ , $w_i(x)$ を $n-1$ 次多項式とする。ここで $a_0=1$ および変数 $a_1, \ldots,a_m \in \mathbb{F}$ はそれぞれの点 $r_1,\ldots,r_q$ で $\sum_{i=0}^m a_i u_i (r_q) \cdot \sum_{i=0}^m a_i v_i(r_q) = \sum_{i=0}^m a_i w_i(r_q)$ である場合に限り $n$ 個の方程式を満たす。 $t(X)$ はそれぞれの点で $t(r_q) = 0$ となる最低次数単項式であるため、この条件を $\sum_{i=0}^m a_i u_i(X) \cdot \sum_{i=0}^m a_i v_i(X) \equiv \sum_{i=0}^m a_i w_i(X) \bmod t(X)$ として再定式化できる。

我々は形式的には以下の記述となる二次算術プログラム $R$ について作業する。 $R = (\mathbb{F}, {\rm aux}, \ell, \{u_i(X),v_i(X),w_i(X)\}_{i=0}^m,t(X))$ ここで $\mathbb{F}$ は有限体、 ${\rm aux}$ は補助情報、 $1 \le \ell \le m$ , $u_i(X)$ , $v_i(X)$ , $w_i(X)$ , $t(X) \in \mathbb{F}[X]$ と $u_i(X)$ , $v_i(X)$ , $w_i(X)$ は $t(X)$ の次数 $n$ よりも厳密に低い次数を持つ。このような記述の二次算術プログラムは次の二項関係を定義する。ここで $a_0=1$ とする。 $r = \left\{ (\phi,w) \left| \begin{array}{l} \phi = (a_1, \ldots, a_\ell) \in \mathbb{F}^\ell \\ w = (a_{\ell+1}, \ldots, a_m) \in \mathbb{F}^{m-\ell} \\ \sum_{i=0}^m a_i u_i(X) \cdot \sum_{i=0}^m a_i v_i(X) \equiv \sum_{i=0}^m a_i w_i(X) \bmod t(X) \end{array} \right. \right\}$ もし $\mathcal{R}$ が $2^{\lambda-1}$ より大きいサイズの体で上記の関係を生成するなら $\mathcal{R}$ は二次算術プログラムジェネレータであると言える。

実際には様々な方法で関係が生じることがある。関係ジェネレータは決定論的である場合もあればランダム化されている場合もある。最初に体 $\mathbb{F}$ が生成され、それから関係の残り部分が体の上に構築される場合がある。または、最初に多項式が指定され、それからランダム体が選択される場合がある。最大限の柔軟性を得るために、我々は体と関係が生成される正確な方法にとらわれない定義を選択した。関係ジェネレータの適切な選択によって様々なオプションをすべてモデル化できる。

以後はペアリングベースの NIZK アーギュメントで補助情報を双線形群に指定する。関係ジェネレータで双線形群を選択するのは少し意外に思うかも知れないが、これによって既存の双線形群上に関係が構築される設定のより良いモデルが提供される。繰り返すがこの選択には一般性の損失はない。従来の設定では関係が最初に選択されてから双線形群がランダムに選択される。これは関係ジェネレータが 2 つのステップで動作する特殊な場合であり、最初に関係を選択してからランダムな双線形群を選択する。もちろん、関係ジェネレータに双線形群を選択させることも、それが良性であると仮定する必要があるもう一つの正当な理由である。セキュリティのためには双線形群の適切な選択が不可欠である。

2.4 線形非対話型証明

Bintasky ら [BCI+13] は 2-move 代数入力-忘却線形対話型証明と呼ばれる最近の SNARK 構造の情報理論的基盤の有用な特性化を提供している。セクション 2.2 で定義した非対話型アーギュメントとの関係を明確にするために、この概念を非対話型線形証明 (NILP; non-interactive linear proofs) と改名する。NILP は関連ジェネレータ $\mathcal{R}$ に対して定義される。ここで関係は有限体 $\mathbb{F}$ を特定し以下のように機能すると仮定する。

$(\vector{\sigma},\vector{\tau}) \leftarrow {\sf Setup}(R)$ : セットアップはベクトル $\vector{\sigma} \in \mathbb{F}^m$ と $\vector{\tau} \in \mathbb{F}^m$ を返す確率多項式時間アルゴリズムである。我々は表記を簡略化するために $\vector{\sigma}$ のアフィン関数と線形関数の間に区別がないように $\vector{\sigma}$ が常に 1 をエントリとして含んでいると仮定する。

$\pi \leftarrow {\sf Prove}(r,\vector{\sigma},\phi,w)$ : 証明者は 2 段階で動作する:

まず $\Pi \leftarrow {\sf ProofMatrix}(R,\phi,w)$ を実行する。ここで ${\sf ProofMatrix}$ は行列 $\Pi \in \mathbb{F}^{k\times m}$ を生成する確率多項式時間アルゴリズムである。
そして $\vector{\pi} = \Pi \vector{\sigma}$ として証明を計算する。

$0/1 \leftarrow {\sf Vfy}(R,\vector{\sigma},\phi,\vector{\pi}$ : 検証者は 2 段階で実行される。

まず決定論的多項式時間アルゴリズム $\vector{t} \leftarrow {\sf Test}(r,\phi)$ を実行して、総次数 $d$ の多変量多項式ベクトルの評価に対応する演算回路 $\vector{t}: \mathbb{F}^{m+k} \to \mathbb{F}^\eta$ を得る。
そして $\vector{t}(\vector{\sigma},\vector{\pi})=\vector{0}$ の場合にのみ証明を受け入れる。

次数 $d$ と次元 $\mu$ , $m$ , $n$ , $k$ , $\eta$ はセキュリティパラメータ $\lambda$ の定数または多項式である。

定義 3 (線形非対話型証明). タプル $({\sf Setup}, {\sf Prove}, {\sf Vfy})$ は、以下で定義するアフィン証明者ストラテジーに対して正確な完全性と統計的知識健全性を持つのであれば、 $\mathcal{R}$ に対する線形非対話型証明である。

Statistical Knowledge Soundness against Affine Prover Strategies(アフィン証明者ストラテジーに対する統計的知識の健全性). NILP は成功した証明行列 $\Pi$ から証拠を抽出できるのならアフィン証明者ストラテジーに対する知識健全性を持つ。より正確には、すべての敵対者 $\mathcal{A}$ に対して ${\rm Pr}\left[ \begin{array}{c} (R,z) \leftarrow \mathcal{R}(1^\lambda); (\vector{\sigma},\vector{\tau}) \leftarrow {\sf Setup}(R); (\phi,\Pi) \leftarrow \mathcal{A}(R,z); w \leftarrow \mathcal{X}(R,\phi,\Pi): \\ \Pi \in \mathbb{F}^{m \times k} \wedge {\sf Vfy}(R, \vector{\sigma},\phi,\Pi\vector{\sigma}) = 0 \wedge (\phi,w) \not\in R \end{array} \right] \approx 0$ であるような多項式時間抽出器 $\mathcal{X}$ が存在する。セクション 2.2 のゼロ知識の概念は NILP にも適用され、2-move LIP のための正直な検証者のゼロ知識に対応する。別の潜在的な拡張は指定された検証者 NILP であり、共通参照情報 $\vector{\sigma}$ が証明者によって使用される $\vector{\sigma}_P$ と証明者によって使用される $\vector{\sigma}_V$ の 2 つの部分に分割される。

2.5 線形非対話型証明からの非対話型アーギュメント

NILP はペアリングを使用して公開検証可能な非対話型アーギュメントにコンパイルでき、Pailler 暗号化 [BCI+13] の変種を使用して指定された検証者の非対話型アーギュメントにコンパイルできるため便利である。ペアリングの設定で作業するのであれば、直感的に、検証者の次数 $d=2$ を持つ NILP を "離散対数で" 実行できる。共通参照情報は $\vector{\sigma}$ の体要素のエンコーディングを含んでいる。証明者は共通参照情報における群要素の線形結合として証明を計算する。検証者は、多くのペアリング積方程式 (ペアリングの結果を乗算して形成される方程式) を検証することによりアーギュメントをチェックする。ここでこの方法論を形式化する。

Type III のペアリングを使用する場合、離散対数で NILP を実行するには、操作を実行する群の各要素を特定する必要がある。従って、共通参照情報を 2 つの部分 $\vector{\sigma}=(\vector{\sigma}_1,\vector{\sigma}_2)$ に分割でき、証明者の証明を 2 つの部分 $\vector{\pi} = (\vector{\pi}_1,\vector{\pi}_2)$ に分割できるような NILP である分割 NILP を定義する。証明の各部分は共通参照情報の対応する部分から計算される。最後に、検証者が行う証明を検証するテストは各変数の次数が 1 である二次方程式にする必要がある。これを書き出すと分割 NILP は次の形式の NILP となる:

$(\vector{\sigma},\vector{\tau}) \leftarrow {\sf Setup}(R)$ : セットアップアルゴリズムはベクトル $\vector{\sigma} = (\vector{\sigma}_1,\vector{\sigma}_2) \in \mathbb{F}^{m_1} \times \mathbb{F}^{m_2}$ と $vector{\tau} \in \mathbb{F}^n$ を生成する。表記を簡略化するために $\vector{\sigma}_1$ と $\vector{\sigma}_2$ の両方がエントリとして 1 を含み、 $\vector{\sigma}$ のアフィン関数と線形関数の間に区別がないと仮定する。

$\pi \leftarrow {\sf Prove}(R,\vector{\sigma},\phi,w)$ : 証明者は 2 段階で動作する:

まず $\Pi \leftarrow {\sf ProofMatrix}(R,\phi,w)$ を実行する。 ${\sf ProofMatrix}$ は $\Pi=\tiny\left( \begin{array}{cc} \Pi_1 & 0 \\ 0 & \Pi_2 \end{array} \right)$ 形式の行列を生成する必要がある。ここで $\Pi_1 \in \mathbb{F}^{k_1 \times m_1}$ および $\Pi_2 \in \mathbb{F}^{k_2 \times m_2}$ である。
そして $\vector{\pi}_1 = \Pi_1 \vector{\sigma}_1$ と $\vector{\pi}_2 = \Pi_2 \vector{\sigma}_2$ を計算し $\vector{\pi} = (\vector{\pi}_1,\vector{\pi}_2)$ を返す。

$0/1 \leftarrow {\sf Vfy}(R,\vector{\sigma},\phi,\vector{\pi})$ : 検証は 2 段階で実行される:

まず $\vector{t} \leftarrow {\sf Test}(R,\phi)$ を実行して行列 $T_1,\ldots,T_\eta \in \mathbb{F}^{(m_1+k_1) \times(m_2+k_2)}$ に対応する算術回路 $\vector{t}: \mathbb{F}^{m_1+k_1+m_2+k_2} \to \mathbb{F}^\eta$ を得る。
そしてすべての行列 $T_1,\ldots,T_\eta$ が $\left( \begin{array}{c} \vector{\sigma}_1 \\ \vector{\pi}_2 \end{array} \right) \cdot T_i \left( \begin{array}{c} \vector{\sigma}_2 \\ \vector{\pi}_2 \end{array} \right) = 0$ である場合にのみ証明を受け入れる。

直感的に、分割 NILP をコンパイルした後、一般的な群操作を使用する不正証明者が NILP から逸脱することはできないと言うことによって健全性を主張したと考えている。ただし、証明者が共通参照情報を見ることによってそれから有用な情報を学習し、それに依存する方法で行列 $\Pi$ を選択することができる。この種の敵対者に対抗するために、証明者が特別な行列を選択するのに役立つ有用な情報を得られないものとして開示のない (diclosure-free) 共通参照情報を定義する。

定義4 (開示のない NILP). 分割 NILP はすべての敵対者 $\mathcal{A}$ が ${\rm Pr} \left[ \begin{array}{c} (R,z) \leftarrow \mathcal{R}(1^\lambda); T \leftarrow \mathcal{A}(R,z); (\vector{\sigma}_1, \vector{\sigma}_2, \vector{\sigma}_3),(\vector{\sigma}_1', \vector{\sigma}_2', \vector{\sigma}_3') \leftarrow {\sf Setup}(R): \\ \vector{\sigma}_1 \cdot T \vector{\sigma}_2 = 0 \ \ \mbox{if and only if} \ \ \vector{\sigma}_1' \cdot T \vector{\sigma}_2' = 0 \end{array} \right] \approx 1$

開示のない共通参照情報の定義を解釈する方法は、敵対者が $\vector{\sigma}_1$ , $\vector{\sigma}_2$ 上で実行することのできる任意のテストの結果が、独立に生成された $\vector{\sigma}_1'$ , $\vector{\sigma}_2'$ 上で実行することによって予測できることである。

これで開示のない共通参照情報を持つ分割 NILP ( ${\sf Setup}$ , ${\sf Prove}$ , ${\sf Vfy}$ , ${\sf Sim}$ ) を使用してペアリングベースの非対話型アーギュメント ( ${\sf Setup'}$ , ${\sf Prove'}$ , ${\sf Vfy'}$ , ${\sf Sim'}$ ) を与えるコンパイラを説明する準備が整った。

$(\sigma,\tau) \leftarrow {\sf Setup}'(R)$ : $(\vector{\sigma}_1,\vector{\sigma}_2,\vector{\sigma}_3) \leftarrow {\sf Setup}(R)$ を実行し $\sigma = ([\vector{\sigma}_1]_1, [\vector{\sigma}_2]_2)$ と $\tau = \vector{\tau}$ を返す。

$\pi \leftarrow {\sf Prove}'(R,\sigma,\phi,w)$ : $(\Pi_1,\Pi_2) \leftarrow {\sf ProofMatrix}(R,x,w)$ を生成し $[\vector{\pi}_1]_1 = \Pi_1 [\vector{\sigma}_1]_1 \ \ \ [\vector{\pi}_2]_2 = \Pi_2 [\vector{\sigma}_2]_2$ として計算される $\pi = ([\vector{\pi}_1]_1,[\vector{\pi}_2]_2)$ を返す。

$0/1 \leftarrow {\sf Vfy}'(R,\sigma,\phi,\pi)$ : $(T_1,\ldots,T_\eta) \leftarrow {\sf Test}(R,\phi)$ を生成し $\pi = ([\vector{\pi}_1]_1, [\vector{\pi}_2]_2) \in \mathbb{G}_1^{k_1} \times \mathbb{G}_2^{k_2}$ を解析して、すべての $T_1,\ldots,T_\eta$ に対して $\left[ \begin{array}{c} \vector{\sigma}_1 \\ \vector{\pi}_1 \end{array} \right]_1 \cdot T_i \left[ \begin{array}{c} \vector{\sigma}_2 \\ \vector{\pi}_2 \end{array} \right]_2 = [0]_T$ となる場合にのみ証明を受け入れる。

$\pi \leftarrow {\sf Sim}'(R,\tau,\phi)$ : $(\vector{\pi}_1,\vector{\pi}_2) \leftarrow {\sf Sim}(R,\vector{\tau}, \phi)$ をシミュレートして $\pi = ([\vector{\pi}_1]_1,[\vector{\pi}_2]_2)$ を返す。

補題 1. 上記のプロトコルは多項式数の一般群演算のみを行う一般的な敵対者に対して正確な完全性と統計的知識健全性を持つ非対話型アーギュメントである。基礎となる分割 NILP が正確にゼロ知識であれば、これは正確にゼロ知識である。

Proof. 正確な完全性は NILP の正確な完全性とそれが分割 NILP であるという事実から導かれる。これにより敵対者は関連群 $\mathbb{G}_1$ と $\mathbb{G}_2$ の一般群演算を使用して証明 $[\vector{\pi}_1]_1$ , $[\vector{\pi}_2]_2$ の 2 つの部分を計算することが可能になる。

正確なゼロ知識は NILP の正確なゼロ知識特性から導かれる。

一般的な敵対者に対する統計的健全性を主張することは依然として残っている。一般的な敵対者は、一般群演算を使用して $\mathbb{G}_1$ , $\mathbb{G}_2$ および $\mathbb{G}_T$ の要素を乗算し、群のメンバーシップをテストし、ペアリングを評価し、要素が等しいかをテストすることができる。

我々はまず開示がないことによって敵対者が共通参照情報に関する重要な情報を学習する可能性が無視できることを意味すると論じた。敵対者が一般群操作を使用して計算した要素が 0 であるかをテストするときはいつでも $[\vector{\sigma}_1]_1 \cdot T[\vector{\sigma}_2]_2 = [0]_T$ 形式のペアリング積等価テストとして書き出すことができる。ここで行列 $T$ は敵対者が行った一般群演算のクエリーから推定できる。これらのクエリーを生成する代わりに、代わりの共通参照設定 $(\vector{\sigma}_1', \vector{\sigma}_2',\vector{\sigma}_3')$ を選択して $\vector{\sigma}_1' \cdot T \vector{\sigma}_2' = 0$ かをテストすることで、自分自身でクエリーに答える修正された敵対者を実行することができる。開示がないことによって、この方法で行われた答えは敵対者が実際の共通参照設定で見ている者と同じ圧倒的な確率で行われる。このため、一般的な敵対者が共通参照情報を含む要素に対してゼロテストを行わないと仮定することができる。

共通参照情報に対してゼロテストを行わずに一般群演算のみを使用する攻撃者は $[\vector{\sigma}_1]_1$ , $[\vector{\sigma}_2]_2$ とは独立して行列 $\Pi_1$ , $\Pi_2$ を選択し $[\pi_1]_1 = \Pi_1 [\vector{\sigma}_1]_1$ と $[\pi_2]_2 = \Pi_2 [\vector{\sigma}_2]_2$ として証明を計算する攻撃者と同等である。離散対数を取ると、これはまさしく分割 NILP 知識健全性敵対者を実行して行列 $\Pi_1$ , $\Pi_2$ と証明 $\vector{\pi}_1 = \Pi_1 \vector{\sigma}_1$ , $\vector{\pi}_2 = \Pi_2 \vector{\sigma}_2$ を取得することに対応する。

検証方程式の離散対数を取ると、もし敵対者が $\phi$ と有効な証明 $\vector{\pi}_1$ , $\vector{\pi}_2$ を見つけることに成功すれば、これは検定行列 $T_1,\ldots,T_\eta \leftarrow {\sf Test}(R,\phi)$ に対して $\left( \begin{array}{c} \vector{\sigma}_1 \\ \Pi_1 \vector{\sigma}_1 \end{array} \right) \cdot T_i \left( \begin{array}{c} \vector{\sigma}_2 \\ \Pi_2 \vector{\sigma}_2 \end{array} \right) = 0$ となる $\phi$ と $\Pi_1$ , $\Pi_2$ を見つけることに相当する。分割 NILP の統計的健全性により、 $\Pi_1$ , $\Pi_2$ の知識が $(\phi,w) \in R$ のような証拠の抽出を可能にしない限り、これが起きる可能性は無視できるほど小さい。
∎

補題 1 の証明は、行列 $\Pi = \tiny \left( \begin{array}{cc} \Pi_1 & 0 \\ 0 & \Pi_2 \end{array} \right)$ の出力に制限されている分割アフィン攻撃に対してのみ健全な分割 NILP を使用する場合にも成立する。ただし、後に我々が構築する分割 NILP は実際に $\Pi$ の任意の選択に対してセキュアである。この利点は暗号解読に対するヘッジであり、たとえ敵対者が $\mathbb{G}_1$ と $\mathbb{G}_2$ の間で効率的に計算可能な同型性を見つけ、それが $g$ から $h$ の写像だとしても、我々は依然として一般的な群モデルにセキュリティを持っている。もう一つの利点は非常に小さな構造の変更で対称双線形群でも機能することである。

3 非対話型アーギュメントの構築

我々は証明が 3 つの群要素のみで構成される二次算術プログラムのペアリングベースの NIZK アーギュメントを構築する。この構築は二段階で行われる。最初に二次算術プログラムの NILP を構築し、次にそれが分割 NILP であることを確認し、前述のコンパイル手法を使用してペアリングベースの NIZK アーギュメントに変換する。

3.1 二次算術プログラムの非対話型線形証明

3.2 NIZK arguments for quadratic arithmetic programs

4 Lower bounds for non-interactive arguments

4.1 Linear interactive proofs cannot have linear decision procedures

4.2 Lower bound for the size of generic pairing-based non-interactive arguments

acknowledgements

We are grateful to Alessandro Chiesa and Madars Virza for extensive comments on an earlier version of this paper and for their implementation and analysis of the SNARK in the libsnark library [CV16]. We also thank Eran Tromer and Michael Walfish for interesting discussions about the performance of SNARK implementations and the anonymous reviewers for their comments.

References

[AF07] Masayuki Abe and Serge Fehr. Perfect NIZK with adaptive soundness. In TCC, volume 4392 of Lecture Notes in Computer Science, pages 118–136, 2007.
[AGOT14] Masayuki Abe, Jens Groth, Miyako Ohkubo, and Mehdi Tibouchi. Unified, minimal and selectively randomizable structure-preserving signatures. In TCC, volume 8349 of Lecture Notes in Computer Science, pages 688–712, 2014.
[BBFR15] Michael Backes, Manuel Barbosa, Dario Fiore, and Raphael M. Reischuk. ADSNARK: nearly practical and privacy-preserving proofs on authenticated data. In IEEE Symposium on Security and Privacy, pages 271–286, 2015.
[BBG05] Dan Boneh, Xavier Boyen, and Eu-Jin Goh. Hierarchical identity based encryption with constant size ciphertext. Cryptology ePrint Archive, Report 2005/015, 2005.
[BCCT12] Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer. From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again. In Innovations in Theoretical Computer Science, pages 326–349, 2012.
[BCCT13] Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer. Recursive composition and bootstrapping for SNARKS and proof-carrying data. In STOC, pages 111–120, 2013.
[BCG+13] Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer, and Madars Virza. Snarks for C: verifying program executions succinctly and in zero knowledge. In CRYPTO, volume 8043 of Lecture Notes in Computer Science, pages 90–108, 2013.
[BCG+14] Eli Ben-Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, and Madars Virza. Zerocash: Decentralized anonymous payments from bitcoin. In IEEE Symposium on Security and Privacy, pages 459–474, 2014.
[BCI+13] Nir Bitansky, Alessandro Chiesa, Yuval Ishai, Rafail Ostrovsky, and Omer Paneth. Succinct non-interactive arguments via linear interactive proofs. In TCC, volume 7785 of Lecture Notes in Computer Science, pages 315–333, 2013.
[BCPR14] Nir Bitansky, Ran Canetti, Omer Paneth, and Alon Rosen. On the existence of extractable one-way functions. In STOC, pages 505–514, 2014.
[BCTV14a] Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, and Madars Virza. Scalable zero knowledge via cycles of elliptic curves. In CRYPTO, volume 8617 of Lecture Notes in Computer Science, pages 276–294, 2014.
[BCTV14b] Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, and Madars Virza. Succinct noninteractive zero knowledge for a von neumann architecture. In USENIX, pages 781–796, 2014.
[BFM88] Manuel Blum, Paul Feldman, and Silvio Micali. Non-interactive zero-knowledge and its applications. In STOC, pages 103–112, 1988.
[BFR+13] Benjamin Braun, Ariel J. Feldman, Zuocheng Ren, Srinath T. V. Setty, Andrew J. Blumberg, and Michael Walfish. Verifying computations with state. In SOSP, pages 341–357, 2013.
[BP15] Elette Boyle and Rafael Pass. Limits of extractability assumptions with distributional auxiliary input. In ASIACRYPT, volume 9453 of Lecture Notes in Computer Science, pages 236–261, 2015.
[BSCG+14] Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Shaul Kfir, Eran Tromer, and Madars Virza. libsnark, 2014. Available at https://github.com/scipr-lab/libsnark.
[CFH+15] Craig Costello, Cédric Fournet, Jon Howell, Markulf Kohlweiss, Benjamin Kreuter, Michael Naehrig, Bryan Parno, and Samee Zahur. Geppetto: Versatile verifiable computation. In IEEE Symposium on Security and Privacy, pages 253–270, 2015.
[CTV15] Alessandro Chiesa, Eran Tromer, and Madars Virza. Cluster computing in zero knowledge. In EUROCRYPT, volume 9057 of Lecture Notes in Computer Science, pages 371–403, 2015.
[CV16] Alessandro Chiesa and Madars Virza. Personal communication, 2016.
[DFGK14] George Danezis, C´edric Fournet, Jens Groth, and Markulf Kohlweiss. Square span programs with applications to succinct NIZK arguments. In ASIACRYPT, volume 8873 of Lecture Notes in Computer Science, pages 532–550, 2014.
[DFKP13] George Danezis, C´edric Fournet, Markulf Kohlweiss, and Bryan Parno. Pinocchio coin: building zerocoin from a succinct pairing-based proof system. In PETShopCCS, 2013.
[GGPR13] Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova. Quadratic span programs and succinct nizks without pcps. In EUROCRYPT, volume 7881 of Lecture Notes in Computer Science, pages 626–645, 2013.
[GMR89] Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proofs. SIAM Journal on Computing, 18(1):186–208, 1989.
[GOS06] Jens Groth, Rafail Ostrovsky, and Amit Sahai. Non-interactive zaps and new techniques for NIZK. In CRYPTO, volume 4117 of Lecture Notes in Computer Science, pages 97–111, 2006.
[GOS12] Jens Groth, Rafail Ostrovsky, and Amit Sahai. New techniques for noninteractive zeroknowledge. Journal of the ACM, 59(3):11:1–11:35, 2012.
[GPS08] Steven D. Galbraith, Kenneth G. Paterson, and Nigel P. Smart. Pairings for cryptographers.Discrete Applied Mathematics, 156(16):3113–3121, 2008.
[Gro06] Jens Groth. Simulation-sound NIZK proofs for a practical language and constant size group signatures. In ASIACRYPT, volume 4248 of Lecture Notes in Computer Science, pages 444–459, 2006.
[Gro09] Jens Groth. Linear algebra with sub-linear zero-knowledge arguments. In CRYPTO, volume 5677 of Lecture Notes in Computer Science, pages 192–208, 2009.
[Gro10] Jens Groth. Short pairing-based non-interactive zero-knowledge arguments. In ASIACRYPT, volume 6477 of Lecture Notes in Computer Science, pages 321–340, 2010.
[GS12] Jens Groth and Amit Sahai. Efficient noninteractive proof systems for bilinear groups.SIAM Journal on Computing, 41(5):1193–1232, 2012.
[GW11] Craig Gentry and Daniel Wichs. Separating succinct non-interactive arguments from all falsifiable assumptions. In STOC, pages 99–108, 2011.
[Kil92] Joe Kilian. A note on efficient zero-knowledge proofs and arguments. In STOC, pages 723–732, 1992.
[Kil95] Joe Kilian. Improved efficient arguments (preliminary version). In CRYPTO, volume 963 of Lecture Notes in Computer Science, pages 311–324, 1995.
[KPP+14] Ahmed E. Kosba, Dimitrios Papadopoulos, Charalampos Papamanthou, Mahmoud F. Sayed, Elaine Shi, and Nikos Triandopoulos. TRUESET: faster verifiable set computations. In USENIX, pages 765–780, 2014.
[Lip12] Helger Lipmaa. Progression-free sets and sublinear pairing-based non-interactive zeroknowledge arguments. In TCC, volume 7194 of Lecture Notes in Computer Science, pages 169–189, 2012.
[Lip13] Helger Lipmaa. Succinct non-interactive zero knowledge arguments from span programs and linear error-correcting codes. In ASIACRYPT, volume 8269 of Lecture Notes in Computer Science, pages 41–60, 2013.
[Mic00] Silvio Micali. Computationally sound proofs. SIAM Journal on Computing, 30(4):1253– 1298, 2000.
[Nec94] Vasilii I. Nechaev. Complexity of a determinate algorithm for the discrete logarithm. Mat. Zametki, 55(2):91–101, 1994.
[PHGR13] Bryan Parno, Jon Howell, Craig Gentry, and Mariana Raykova. Pinocchio: Nearly practical verifiable computation. In IEEE Symposium on Security and Privacy, pages 238–252, 2013.
[Sho97] Victor Shoup. Lower bounds for discrete logarithms and related problems. In EUROCRYPT, volume 1233 of Lecture Notes in Computer Science, pages 256–266, 1997.
[SVdV16] Berry Schoenmakers, Meilof Veeningen, and Niels de Vreede. Trinocchio: Privacy-friendly outsourcing by distributed verifiable computation. In ACNS, volume ???? of Lecture Notes in Computer Science, pages ???–???, 2016.
[Val08] Paul Valiant. Incrementally verifiable computation or proofs of knowledge imply time/space efficiency. In TCC, volume 4948 of Lecture Notes in Computer Science, pages 1–18, 2008.
[Wal15] Michael Walfish. A wishlist for verifiable computation: An applied cs perspective, 2015.
[WB15] Michael Walfish and Andrew J. Blumberg. Verifying computations without reexecuting them. Communications of the ACM, 58(2):74–84, 2015.
[WSR+15] Riad S. Wahby, Srinath T. V. Setty, Zuocheng Ren, Andrew J. Blumberg, and Michael Walfish. Efficient RAM and control flow in verifiable outsourced computation. In NDSS, 2015.

翻訳抄

2016 年の論文。

Jens Groth, On the Size of Pairing-based Non-interactive Arguments, IACR Cryptography ePrint Archive 2016, P.260 (2016)

論文翻訳: On the Size of Pairing-based Non-interactive Arguments​​