Proofs for Inner Pairing Products and Applications

被引:55
作者
Bunz, Benedikt [1 ]
Maller, Mary [2 ]
Mishra, Pratyush [3 ]
Tyagi, Nirvan [4 ]
Vesely, Psi [5 ]
机构
[1] Stanford Univ, Stanford, CA 94305 USA
[2] Ethereum Fdn, Bern, Switzerland
[3] Univ Calif Berkeley, Berkeley, CA USA
[4] Cornell Univ, Ithaca, NY USA
[5] Univ Calif San Diego, San Diego, CA USA
来源
ADVANCES IN CRYPTOLOGY - ASIACRYPT 2021, PT III | 2021年 / 13092卷
关键词
STRUCTURE-PRESERVING SIGNATURES; COMMITMENTS;
D O I
10.1007/978-3-030-92078-4_3
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
We present a generalized inner product argument and demonstrate its applications to pairing-based languages. We apply our generalized argument to prove that an inner pairing product is correctly evaluated with respect to committed vectors of n source group elements. With a structured reference string (SRS), we achieve a logarithmic-time verifier whose work is dominated by 6 log n target group exponentiations. Proofs are of size 6logn target group elements, computed using 6n pairings and 4n exponentiations in each source group. We apply our inner product arguments to build the first polynomial commitment scheme with succinct (logarithmic) verification, O(v d) prover complexity for degree d polynomials (not including the cost to evaluate the polynomial), and a SRS of size O(v d). Concretely, this means that for d = 2(28), producing an evaluation proof in our protocol is 76x faster than doing so in the KZG commitment scheme, and the CRS in our protocol is 1000x smaller: 13MB vs 13GB for KZG. As a second application, we introduce an argument for aggregating n Groth16 zkSNARKs into an O(log n) sized proof. Our protocol is significantly faster (>1000x) than aggregating SNARKs via recursive composition: we aggregate similar to 130, 000 proofs in 25 min, versus 90 proofs via recursive composition. Finally, we further apply our aggregation protocol to construct a low-memory SNARK for machine computations that does not rely on recursive composition. For a computation that requires time T and space S, our SNARK produces proofs in space (O) over tilde (S + T), which is significantly more space efficient than a monolithic SNARK, which requires space (O) over tilde (S center dot T).
引用
收藏
页码:65 / 97
页数:33
相关论文
共 51 条
[1]   Structure-Preserving Signatures and Commitments to Group Elements [J].
Abe, Masayuki ;
Fuchsbauer, Georg ;
Groth, Jens ;
Haralambiev, Kristiyan ;
Ohkubo, Miyako .
JOURNAL OF CRYPTOLOGY, 2016, 29 (02) :363-421
[2]   Compressed Σ-Protocol Theory and Practical Application to Plug & Play Secure Algorithmics [J].
Attema, Thomas ;
Cramer, Ronald .
ADVANCES IN CRYPTOLOGY - CRYPTO 2020, PT III, 2020, 12172 :513-543
[3]  
Backes Michael, 2013, Topics in Cryptology - CT-RSA 2013. The Cryptographers Track at the RSA Conference 2013. Proceedings, P259, DOI 10.1007/978-3-642-36095-4_17
[4]  
Bayer S, 2013, LECT NOTES COMPUT SC, V7881, P646, DOI 10.1007/978-3-642-38348-9_38
[5]  
Ben-Sasson E., 2013, ITCS, P401
[6]  
Ben-Sasson E, 2014, PROCEEDINGS OF THE 23RD USENIX SECURITY SYMPOSIUM, P781
[7]   Zerocash: Decentralized Anonymous Payments from Bitcoin [J].
Ben-Sasson, Eli ;
Chiesa, Alessandro ;
Garmant, Christina ;
Green, Matthew ;
Miers, Ian ;
Tromer, Eran ;
Virza, Madars .
2014 IEEE SYMPOSIUM ON SECURITY AND PRIVACY (SP 2014), 2014, :459-474
[8]  
Ben-Sasson E, 2014, LECT NOTES COMPUT SC, V8617, P276, DOI 10.1007/978-3-662-44381-1_16
[9]  
Ben-Sasson E, 2013, LECT NOTES COMPUT SC, V8043, P90, DOI 10.1007/978-3-642-40084-1_6
[10]  
Bitansky N, 2013, STOC'13: PROCEEDINGS OF THE 2013 ACM SYMPOSIUM ON THEORY OF COMPUTING, P111