\def\vector#1{\boldsymbol{#1}}

論文翻訳: Quadratic Span Programs and Succinct NIZKs without PCPs

2019年11月25日 2013年の論文 #zk-SNARK

Rosario Gennaro

Graig Gentry

Bryan Parno

Mariana Raykova

Abstract

我々は Quadratic Span Program (QSP) と呼ぶ NP 複雑性クラスの新しい特性化を導入する。これは Karchmer と Wigderson によって定義された Span Program の自然な拡張である。我々の主な動機は、NP ステートメントを迅速に構築し検証する簡潔な議論の構築である。QSP はこの作業に適しているようで、おそらく確率的検証可能証明 (PCPs; Probablistically Checkable Proofs) より優れている。

2010 年に Groth は双線形群の 42 の元のみで構成される Circuit-SAT の共通参照列 (CRS; common reference string) モデルにおいて NIZK 議論を構築した。興味深いことに彼の主張は (明示的に) PCP を使用していない。しかしこの方法にはいくつかの欠点がある。つまり、CRS サイズと Prover の計算はどちらも Curcuit サイズにおいて二次である。2011 年に Lipmaa は CRS サイズを準線形に縮小したが Prover の計算ではまだ二次であった。

我々は QSP を用いて 7 個の群元からなる Circuit-SAT に対する CRS モデルにおいて NIZK 議論を構成した。CRS サイズは Circuit サイズにおいて線形であり、Prover 計算は準線形であるためこのスキームは一見して非常に実用的である。(Prover は線形数の群操作を行うのみで良い; 準線形計算は多点評価と補間である。)

我々の結果は CRS サイズと Prover と Verifier 計算を低減するために論議の "Bootstrapping" (再帰的構成) を使用した Valiant (TCC 2008) と Bitansky ら (2012) の結果と相補的である。QSP はまた Groth と Lipmaa の構築の基礎となる手法のいくつかの鮮明な数学的抽象化を提供する。

Abstract
1 導入
2 Quadratic span Programs (QSPs)
3 Overview of Our Cryptographic Constructions and Security
4 Cryptographic Constructions from Strong QSPs
5 Security of Our Public-Verifier SNARK and NIZK
6 Security: the Designated-Verifier Case
1. 6.1 Assumptions
2. 6.2 Security Theorem
7 Quadratic Programs for Arithmetic Circuits
8 SNARK Construction from QAP
1. 8.1 Zero-Knowledge SNARKs (including NIZKs) from QAP
2. 8.2 Designated-Verifier SNARK from QAP
9 Conclusions and Open Questions
References
翻訳抄

1 導入

PCP 定理 [BFLS91, FGL+96, AS98, ALM+98] は NP の新しい特性を提供し "証明" の概念に革命をもたらした。特に、NP ステートメントには確率的に検証可能な証明 (PCP) があり、従来の証明のサイズで時間の対数で検証することができることが示された。Kilian は NP のこの新しい特性を暗号化設定に適合させ、PCP を使用して簡潔 (succient)、つまり通信複雑度において多対数な NP の対話的引数 (すなはち計算上の sound proof [BMC88]) を作成できることを示した。Micali [Mic00] は Flat-Shamir ヒューリスティック [FS86] を適用することでこれらの引数を非対話型にする方法を示した。すなはち、証明者はランダムオラクル [BR93] としてモデル化されたハッシュ関数を、コミットメントの形式、および検証者の PCP クエリーを非対話的に生成するために、その PCP データ列に適用する。最近の研究 [BCCT12a, GLR11, DFH12] ([CL08] も参照) はインスタンス化することができないことが知られているランダムオラクル [CGH04] を除外し "抽出可能な衝突耐性ハッシュ関数" (ECRH; extractable collision-resistance hash functions) に置き換えることによって Micali の構造を改善した。このセキュリティは、ECRH のイメージを計算する任意のアルゴリズムにはプレイメージを計算する抽出器 (アルゴリズムを監視する) が存在するという、もっともらしいが反証不可能 (non-falsifiable) [Nao03] な仮定に依存する¹。これらの最近の構築は知識 (SNARKs) の簡潔な非対話的引数 (SNARGs; succinct non-interactive arguments) と呼ばれている。これは知識の仮定の下では SNARG はハッシュプレイメージ全体、すなはち PCP 全体の "知識" 抽出を可能にするからである。

手短に言えば、PCP 定理はとりわけ SNARG および SNARK を構築するために有用な NP の非常に強力な特徴付けを提供する。しかし PCP 定理が注目に値するように、暗号化アプリケーションのためだけに考えられたわけではない。従って (明示的に) PCP を使わず、より良い SNARG/SNARK を構築することができるだろうか? 暗号アプリケーションに適した NP の別の特徴はあるだろうか? と問うことは理にかなっているように思われる。

¹ 我々は、簡潔な非対話的引数の安全性はブラックボックスの縮小 [AF07, GW11] を通じた偽造可能な仮定に基づくことができないことを知っている; 従ってこの文脈では反証不可能な "知識" 仮定は避けられないように思われる。

1.1 二次スパンプログラム: NP の新しい特性

我々は PCP なしで非常に効率的な SNARK を構築できる NP の新しい特性である二次スパンプログラム (quadratic span programs) (QSPs) を導入する。

QSP を説明するためには Karchmer and Wigdarson [KW93] によって導入された計算の線形代数モデルであるスパンプログラム (SPs) について思い出すことが役に立つ。体 $F$ 上の SP は $F$ 上の非ゼロ対象ベクトル $\vector{t}$ 、ベクトル集合 $\vector{\mathcal{V}} = \{\vector{v}_1,\ldots,\vector{v}_m\}$ 、二つの集合 $\mathcal{L}_{\it labeled}$ と $\mathcal{L}_{\it free}$ へのインデックス $\mathcal{L} = \{1, \ldots, m\}$ の区画、および $\mathcal{L}_{\it labeled}$ の $\cup_{i \in [n],\ j \in \{0,1\}} \mathcal{L}_{ij}$ 区画で構成される。SP は全ての入力引数 $u \in \{0,1\}^n$ に対して次が当てはまる場合に関数 $f$ を "計算する" と言う: 対象ベクトルは入力引数 $u$ に "属する" ベクトルのスパン内にある ─ つまり $f(u) = 1$ である場合にのみ $\mathcal{L}_u = \mathcal{L}_{\it free} \cup_i \mathcal{L}_{i, u_i}$ のインデックスを持つベクトルである。スパンプログラムのサイズは $m$ である。

線形代数が ${\rm NC}^2$ にあることから多項式サイズの SP を持つ関数は ${\rm NC}^2$ にある。したがって SP は P の全ての関数を効率的に計算する (または全ての NP 関係を検証する) ほど強力ではないと広く信じられている。

我々はSP といくぶん似ている QSP を定義する。

定義 1 (Quadratic Span Program). 体 $F$ 上の二次スパンプログラム (QSP) $Q$ には、二つの多項式 $\mathcal{V} = \{v_k(x): k \in \{0,\ldots,m\}\}$ 、 $\mathcal{W}=\{w_k(x): k \in \{0,\ldots,m\}\}$ セットと一つの対象多項式 $t(x)$ を含んでいる。これらは全て $F[x]$ からである。 $Q$ にはまたインデックス $\mathcal{L}=\{1,\ldots,m\}$ の 2 つのセット $\mathcal{L}_{\it labeled}$ と $\mathcal{L}_{\it free}$ への区画と、 $\mathcal{L}_{\it labeled}$ の $\cup_{i \in [n],\ j \in \{0,1\}} \mathcal{L}_{ij}$ としての区画も含まれている。

入力 $u \in \{0, 1\}^n$ について、入力 $u$ に "属する" インデックスの集合を $\mathcal{L}_u = \mathcal{L}_{\it free} \cup_i \mathcal{L}_{i,u_i}$ とする。 $Q$ は $F^m$ からタプル $(a_1,\ldots,a_m)$ と $(b_1,\ldots,b_m)$ が存在し、全ての $k \not\in \mathcal{L}_u$ に対して $a_k = 0 = b_k$ であり $\begin{equation} t(x) \ \ {\rm divides} \ \ \left( v_0(x) + \sum_{k=1}^m a_k \cdot v_k(x) \right) \cdot \left( w_0(x) + \sum_{k=1}^m b_k \cdot w_k(x) \right) \end{equation}$ である場合にのみ入力 $u$ を受け入れる。 $Q$ は $f(u)=1$ の入力 $u$ を正確に受け入れる場合にブール関数 $f: \{0,1\}^n \to \{0,1\}$ を "計算する"。 $Q$ のサイズは $m$ である。 $Q$ の次数は $\deg(t(x))$ である。

QSP は (線形) SP の自然な拡張のように思える。SP はターゲットベクトルが $u$ に "属する" ベクトルの線形結合として表現できる場合に限り入力 $u$ を受け入れる。QSP はターゲット多項式 (の乗算) が $u$ に "属する" ベクトルの 2 つの線形結合の積として表現できる場合にのみ $u$ を受け入れる。ここで "積" は多項式の乗算として定義される。

重要なことは、SP とは異なり QSP は任意の効率的に計算可能な関数を効率的に計算できることであり、従って NP を QSP によって効率的に検証できる証明を持つ言語のセットとして定義できることである。

定理 1 . (Informal) $s$ 個のゲートとサイズが少なくとも $d=O(s)$ の任意の体 $F$ を持つ任意のブーリアン回路 $f$ に対して、 $f$ を計算する $F$ 上のサイズと (小さな定数を持つ) 次数 $O(s)$ の QSP が存在する。

1.2 From QSPs to SNARKs and NIZKs

1.3 Comparisons to Other work on Succinct Arguments without PCPs

2 Quadratic span Programs (QSPs)

2.1 Component 1: A Useful Linear Span Program

2.2 Component 2: A Consistency Checker

2.3 Our Canonical QSP

2.4 QSP Efficiency considerations

3 Overview of Our Cryptographic Constructions and Security

3.1 Our SNARK Construction

3.2 Making the SNARK Statistical Zero-Knowledge (NIZKs)

3.3 Performance and Optimizations

3.4 Security

4 Cryptographic Constructions from Strong QSPs

4.1 Definitions: SNARGs, SNARKs, Verifiable Computation, NIZKs

4.1.1 Succinct Non-Interactive Arguments

4.1.2 Verifiable Computation

4.1.3 Non-Interactive Zero Knowledge

4.2 Verifiable Computation from Designated-Verifier SNARKs

4.3 Constructions of Designated-Verifier / Public-Verifier SNAKRKs from Strong QSPs

4.4 Zero-Knowledge SNARKs (including NIZKs) from Strong QSPs: How to Randomize Our SNARKs

4.5 Optimizations

4.5.1 Reducing the Verifier's Work without PCPs

4.5.2 Reducing the Verifier's Work with PCPs

4.5.3 Reducing the Verifier's Preprocessing: Combining Universal Circuits with the Hash Trick or PCPs

4.5.4 Even Shorter Proofs in the Designated-Verifier Setting

5 Security of Our Public-Verifier SNARK and NIZK

5.1 Assumptions

5.2 Lemmas

5.3 Security Theorem

6 Security: the Designated-Verifier Case

6.1 Assumptions

6.2 Security Theorem

7 Quadratic Programs for Arithmetic Circuits

7.1 Definitions: QAP and Strong QAP

7.2 QAPs for Arithmetic Circuits with One Multiplication Gate

7.3 Composition of QAPs, and QAPs for General Arithmetic Circuits

7.4 Illustration of a QP for a Simple Arithmetic Circuit

7.5 QAP Efficiency Considerations

8 SNARK Construction from QAP

8.1 Zero-Knowledge SNARKs (including NIZKs) from QAP

8.2 Designated-Verifier SNARK from QAP

9 Conclusions and Open Questions

References

[AF07] Masayuki Abe and Serge Fehr. Perfect NIZK with adaptive soundness. In Salil P. Vadhan, editor, TCC, volume 4392 of Lecture Notes in Computer Science, pages 118–136. Springer, 2007.
[AIK10] Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. From secrecy to soundness: Efficient verification via secure computation. In Samson Abramsky, Cyril Gavoille, Claude Kirchner, Friedhelm Meyer auf der Heide, and Paul G. Spirakis, editors, ICALP (1), volume 6198 of Lecture Notes in Computer Science, pages 152–163. Springer, 2010.
[ALM+98] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. J. ACM, 45(3):501–555, 1998.
[AS98] Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP. J. ACM, 45(1):70–122, 1998.
[BBG05] Dan Boneh, Xavier Boyen, and Eu-Jin Goh. Hierarchical identity based encryption with constant size ciphertext. In Ronald Cramer, editor, EUROCRYPT, volume 3494 of Lecture Notes in Computer Science, pages 440–456. Springer, 2005.
[BCC88] Gilles Brassard, David Chaum, and Claude Crépeau. Minimum disclosure proofs of knowledge. J. Comput. Syst. Sci., 37(2):156–189, 1988.
[BCCT12a] Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer. From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again. In Goldwasser [Gol12], pages 326–349.
[BCCT12b] Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer. Recursive composition and bootstrapping for snarks and proof-carrying data. IACR Cryptology ePrint Archive, 2012. http://eprint.iacr.org/2012/095.
[BFLS91] László Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy. Checking computations in polylogarithmic time. In Cris Koutsougeras and Jeffrey Scott Vitter, editors, STOC, pages 21–31. ACM, 1991.
[BFM88] Manuel Blum, Paul Feldman, and Silvio Micali. Non-interactive zero-knowledge and its applications (extended abstract). In STOC, pages 103–112, 1988.
[BGW05] Dan Boneh, Craig Gentry, and Brent Waters. Collusion resistant broadcast encryption with short ciphertexts and private keys. In Victor Shoup, editor, CRYPTO, volume 3621 of Lecture Notes in Computer Science, pages 258–275. Springer, 2005.
[BP04] Mihir Bellare and Adriana Palacio. The knowledge-of-exponent assumptions and 3- round zero-knowledge protocols. In Matthew K. Franklin, editor, CRYPTO, volume 3152 of Lecture Notes in Computer Science, pages 273–289. Springer, 2004.
[BR93] Mihir Bellare and Phillip Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In Dorothy E. Denning, Raymond Pyle, Ravi Ganesan, Ravi S. Sandhu, and Victoria Ashby, editors, ACM Conference on Computer and Communications Security, pages 62–73. ACM, 1993.
[BSMP91] Manuel Blum, Alfredo De Santis, Silvio Micali, and Giuseppe Persiano. Noninteractive zero-knowledge. SIAM Journal on Computing, 20(6):1084–1118, 1991.
[BSW12] Dan Boneh, Gil Segev, and Brent Waters. Targeted malleability: homomorphic encryption for restricted computations. In Goldwasser [Gol12], pages 350–366.
[CD09] Ran Canetti and Ronny Ramzi Dakdouk. Towards a theory of extractable functions. In Omer Reingold, editor, TCC, volume 5444 of Lecture Notes in Computer Science, pages 595–613. Springer, 2009.
[CGH04] Ran Canetti, Oded Goldreich, and Shai Halevi. The random oracle methodology, revisited. J. ACM, 51(4):557–594, 2004.
[CKLM12] Melissa Chase, Markulf Kohlweiss, Anna Lysyanskaya, and Sarah Meiklejohn. Malleable proof systems and applications. In David Pointcheval and Thomas Johansson, editors, EUROCRYPT, volume 7237 of Lecture Notes in Computer Science, pages 281–300. Springer, 2012.
[CKV10] Kai-Min Chung, Yael Tauman Kalai, and Salil P. Vadhan. Improved delegation of computation using fully homomorphic encryption. In CRYPTO, volume 6223 of Lecture Notes in Computer Science, pages 483–501. Springer, 2010.
[CL08] Giovanni Di Crescenzo and Helger Lipmaa. Succinct NP proofs from an extractability assumption. In Arnold Beckmann, Costas Dimitracopoulos, and Benedikt L¨owe, editors, CiE, volume 5028 of Lecture Notes in Computer Science, pages 175–185. Springer, 2008.
[Dam91] Ivan Damg˚ard. Towards practical public key systems secure against chosen ciphertext attacks. In Joan Feigenbaum, editor, CRYPTO, volume 576 of Lecture Notes in Computer Science, pages 445–456. Springer, 1991.
[DFH12] Ivan Damg˚ard, Sebastian Faust, and Carmit Hazay. Secure two-party computation with low communication. In Ronald Cramer, editor, TCC, volume 7194 of Lecture Notes in Computer Science, pages 54–74. Springer, 2012.
[DN07] Cynthia Dwork and Moni Naor. Zaps and their applications. SIAM J. Comput., 36(6):1513–1543, 2007.
[FGL+96] Uriel Feige, Shafi Goldwasser, L´aszl´o Lov´asz, Shmuel Safra, and Mario Szegedy. Interactive proofs and the hardness of approximating cliques. J. ACM, 43(2):268–292, 1996.
[FS86] Amos Fiat and Adi Shamir. How to prove yourself: Practical solutions to identification and signature problems. In Andrew M. Odlyzko, editor, CRYPTO, volume 263 of Lecture Notes in Computer Science, pages 186–194. Springer, 1986.
[Gen09a] Craig Gentry. A fully homomorphic encryption scheme. PhD thesis, Stanford University, 2009. crypto.stanford.edu/craig.
[Gen09b] Craig Gentry. Fully homomorphic encryption using ideal lattices. In Michael Mitzenmacher, editor, STOC, pages 169–178. ACM, 2009.
[GGP10] Rosario Gennaro, Craig Gentry, and Bryan Parno. Non-interactive verifiable computing: Outsourcing computation to untrusted workers. In CRYPTO, volume 6223 of Lecture Notes in Computer Science, pages 465–482. Springer, 2010.
[Gjø04] Kristian Gjøsteen. Subgroup membership problems and public key cryptosystems. PhD thesis, Norwegian University of Science and Technology, 2004. urn.kb.se/resolve?urn=urn:nbn:no:ntnu:diva-128.
[GKR08] Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. Delegating computation: interactive proofs for muggles. In Cynthia Dwork, editor, STOC, pages 113–122. ACM, 2008.
[GLR11] Shafi Goldwasser, Huijia Lin, and Aviad Rubinstein. Delegation of computation without rejection problem from designated verifier CS-proofs. IACR Cryptology ePrint Archive, 2011:456, 2011.
[Gol12] Shafi Goldwasser, editor. Innovations in Theoretical Computer Science 2012, Cambridge, MA, USA, January 8-10, 2012. ACM, 2012.
[GOS06] Jens Groth, Rafail Ostrovsky, and Amit Sahai. Perfect non-interactive zero knowledge for np. In Serge Vaudenay, editor, EUROCRYPT, volume 4004 of Lecture Notes in Computer Science, pages 339–358. Springer, 2006.
[Gro10] Jens Groth. Short pairing-based non-interactive zero-knowledge arguments. In Masayuki Abe, editor, ASIACRYPT, volume 6477 of Lecture Notes in Computer Science, pages 321–340. Springer, 2010.
[GS08] Jens Groth and Amit Sahai. Efficient non-interactive proof systems for bilinear groups. In Nigel P. Smart, editor, EUROCRYPT, volume 4965 of Lecture Notes in Computer Science, pages 415–432. Springer, 2008.
[GW11] Craig Gentry and Daniel Wichs. Separating succinct non-interactive arguments from all falsifiable assumptions. In STOC, pages 99–108. ACM, 2011.
[HT98] Satoshi Hada and Toshiaki Tanaka. On the existence of 3-round zero-knowledge protocols. In Hugo Krawczyk, editor, CRYPTO, volume 1462 of Lecture Notes in Computer Science, pages 408–423. Springer, 1998.
[IKO07] Yuval Ishai, Eyal Kushilevitz, and Rafail Ostrovsky. Efficient arguments without short PCPs. In IEEE Conference on Computational Complexity, pages 278–291. IEEE Computer Society, 2007.
[KW93] Mauricio Karchmer and Avi Wigderson. On span programs. In Structure in Complexity Theory Conference, pages 102–111, 1993.
[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. Springer, 2012.
[LMSV11] Jake Loftus, Alexander May, Nigel P. Smart, and Frederik Vercauteren. On CCAsecure somewhat homomorphic encryption. In Ali Miri and Serge Vaudenay, editors, Selected Areas in Cryptography, volume 7118 of Lecture Notes in Computer Science, pages 55–72. Springer, 2011.
[Mic00] Silvio Micali. Computationally sound proofs. SIAM J. Comput., 30(4):1253–1298, 2000. extended abstract in FOCS ’94.
[Nao03] Moni Naor. On cryptographic assumptions and challenges. In Dan Boneh, editor, CRYPTO, volume 2729 of Lecture Notes in Computer Science, pages 96–109. Springer, 2003.
[Pai99] Pascal Paillier. Public-key cryptosystems based on composite degree residuosity classes. In Jacques Stern, editor, EUROCRYPT, volume 1592 of Lecture Notes in Computer Science, pages 223–238. Springer, 1999.
[PRV12] Bryan Parno, Mariana Raykova, and Vinod Vaikuntanathan. How to delegate and verify in public: Verifiable computation from attribute-based encryption. In IACR Theory of Cryptography Conference (TCC), 2012.
[RAD78] Ron Rivest, Leonard Adleman, and Michael L. Dertouzos. On data banks and privacy homomorphisms. In Foundations of Secure Computation, pages 169–180, 1978.
[RV10] Guy N. Rothblum and Salil P. Vadhan. Are PCPs inherent in efficient arguments? Computational Complexity, 19(2):265–304, 2010.
[SMBW12] Srinath Setty, Richard McPherson, Andrew J. Blumberg, and Michael Walfish. Making argument systems for outsourced computation practical (sometimes). In Proceedings of the ISOC Symposium on Network and Distributed System Security (NDSS), 2012.
[Val08] Paul Valiant. Incrementally verifiable computation or proofs of knowledge imply time/space efficiency. In Ran Canetti, editor, TCC, volume 4948 of Lecture Notes in Computer Science, pages 1–18. Springer, 2008.
[WS07] Jiang Wu and Douglas R. Stinson. An efficient identification protocol and the knowledge-of-exponent assumption. IACR Cryptology ePrint Archive, 2007:479, 2007.
[YYZZ07] Andrew Chi-Chih Yao, Frances F. Yao, Yunlei Zhao, and Bin Zhu. Deniable internet key-exchange. IACR Cryptology ePrint Archive, 2007:191, 2007.

翻訳抄

Rosario Gennaro, Craig Gentry, Bryan Parno, Mariana Raykova, Quadratic Span Programs and Succient NIZKs without PCPs, In Advances in Cryptology-EUROCRYPT 2013, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013. Proceedings, pp.626-645 (2013)