1. bookVolume 2022 (2022): Issue 1 (January 2022)
Journal Details
License
Format
Journal
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English
access type Open Access

Polaris: Transparent Succinct Zero-Knowledge Arguments for R1CS with Efficient Verifier

Published Online: 20 Nov 2021
Page range: 544 - 564
Received: 31 May 2021
Accepted: 16 Sep 2021
Journal Details
License
Format
Journal
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English
Abstract

We present a new zero-knowledge succinct argument of knowledge (zkSNARK) scheme for Rank-1 Constraint Satisfaction (RICS), a widely deployed NP-complete language that generalizes arithmetic circuit satisfiability. By instantiating with different commitment schemes, we obtain several zkSNARKs where the verifier’s costs and the proof size range from O(log2 N) to O(N) O\left( {\sqrt N } \right) depending on the underlying polynomial commitment schemes when applied to an N-gate arithmetic circuit. All these schemes do not require a trusted setup. It is plausibly post-quantum secure when instantiated with a secure collision-resistant hash function. We report on experiments for evaluating the performance of our proposed system. For instance, for verifying a SHA-256 preimage (less than 23k AND gates) in zero-knowledge with 128 bits security, the proof size is less than 150kB and the verification time is less than 11ms, both competitive to existing systems.

Keywords

[1] A pure-Rust implementation of group operations on Ristretto and curve25519. https://github.com/dalek-cryptography/curve25519-dalek. Search in Google Scholar

[2] libiop: a C++ library for IOP-based zkSNARKs. https://github.com/scipr-lab/libiop. Search in Google Scholar

[3] libsnark: a C++ library for zkSNARK proofs. https://github.com/scipr-lab/libsnark. Search in Google Scholar

[4] Marlin. https://github.com/arkworks-rs/marlin. Search in Google Scholar

[5] Spartan: High-speed zkSNARKs without trusted setup. https://github.com/microsoft/spartan. Search in Google Scholar

[6] Virgo ZK reference implementation. https://github.com/sunblaze-ucb/virgo. Search in Google Scholar

[7] Scott Ames, Carmit Hazay, Yuval Ishai, and Muthuramakrishnan Venkitasubramaniam. Ligero: Lightweight sublinear arguments without a trusted setup. CCS 2017: 2087–2104. Search in Google Scholar

[8] Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Fast reed-solomon interactive oracle proofs of proximity. ICALP 2018: 14:1–14:17. Search in Google Scholar

[9] Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Scalable, transparent, and post-quantum secure computational integrity. IACR Cryptology ePrint Archive, 2018: 46. Search in Google Scholar

[10] Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, and Shubhangi Saraf. Proximity gaps for Reed-Solomon codes. FOCS 2020: 900–909. Search in Google Scholar

[11] Eli Ben-Sasson, Alessandro Chiesa, Michael A. Forbes, Ariel Gabizon, Michael Riabzev, and Nicholas Spooner. Zero knowledge protocols from succinct constraint detection. TCC 2017: 172–206. Search in Google Scholar

[12] Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, and Madars Virza. Quasi-linear size zero knowledge from linear-algebraic PCPs. TCC 2016-A: 33–64. Search in Google Scholar

[13] Eli Ben-Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, and Madars Virza. Zerocash: Decentralized anonymous payments from bitcoin. IEEE Symposium on Security and Privacy 2014: 459–474. Search in Google Scholar

[14] Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, and Eran Tromer. Fast reductions from RAMs to delegatable succinct constraint satisfaction problems. ITCS 2013: 401–414. Search in Google Scholar

[15] Eli Ben-Sasson, Alessandro Chiesa, Lior Goldberg, Tom Gur, Michael Riabzev, and Nicholas Spooner. Linear-Size Constant-Query IOPs for Delegating Computation. TCC (2) 2019: 494–521. Search in Google Scholar

[16] Eli Ben-Sasson, Alessandro Chiesa, Michael Riabzev, Nicholas Spooner, Madars Virza, and Nicholas P. Ward. Aurora: Transparent succinct arguments for R1CS. EURO-CRYPT (1) 2019: 103–128. Search in Google Scholar

[17] Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner. Interactive oracle proofs. TCC (2) 2016: 31–60. Search in Google Scholar

[18] Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, and Madars Virza. Succinct non-interactive zero knowledge for a von neumann architecture. USENIX Security Symposium 2014: 781–796. Search in Google Scholar

[19] Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, and Shubhangi Saraf. DEEP-FRI: Sampling outside the box improves soundness. ITCS 2020: 5:1–5:32. Search in Google Scholar

[20] Rishabh Bhadauria, Zhiyong Fang, Carmit Hazay, Muthuramakrishnan Venkitasubramaniam, Tiancheng Xie, and Yupeng Zhang. Ligero++: A new optimized sublinear IOP. CCS 2020: 2025–2038. Search in Google Scholar

[21] Jonathan Bootle, Andrea Cerulli, Pyrros Chaidos, Jens Groth, and Christophe Petit. Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting. EUROCRYPT (2) 2016: 327–357. Search in Google Scholar

[22] Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, and Gregory Maxwell. Bulletproofs: Short proofs for confidential transactions and more. IEEE Symposium on Security and Privacy 2018: 315–334. Search in Google Scholar

[23] Benedikt Bünz, Ben Fisch, and Alan Szepieniec. Transparent snarks from DARK compilers. EUROCRYPT (1) 2020: 677–706. Search in Google Scholar

[24] Nigel P. Byott and Robin J. Chapman. Power sums over finite subspaces of a field. Finite Fields and Their Applications, 5(3): 254–265, 1999. Search in Google Scholar

[25] Benedikt Bünz, Mary Maller, Pratyush Mishra, and Noah Vesely. Proofs for inner pairing products and applications. IACR Cryptology ePrint Archive, 2019: 1177. Search in Google Scholar

[26] Matteo Campanelli, Rosario Gennaro, Steven Goldfeder, and Luca Nizzardo. Zero-knowledge contingent payments revisited: Attacks and payments for services. CCS 2017: 229–243. Search in Google Scholar

[27] Alessandro Chiesa, Michael A. Forbes, and Nicholas Spooner. A zero knowledge sumcheck and its applications. IACR Cryptology ePrint Archive, 2017: 305. Search in Google Scholar

[28] Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Noah Vesely, and Nicholas P. Ward. Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS. EUROCRYPT (1) 2020: 738–768. Search in Google Scholar

[29] Alessandro Chiesa, Dev Ojha, and Nicholas Spooner. Fractal: Post-quantum and transparent recursive proofs from holography. EUROCRYPT (1) 2020: 769–793. Search in Google Scholar

[30] Graham Cormode, Michael Mitzenmacher, and Justin Thaler. Practical verified computation with streaming interactive proofs. ITCS 2012: 90–112. Search in Google Scholar

[31] Amos Fiat and Adi Shamir. How to prove yourself: Practical solutions to identification and signature problems. CRYPTO 1986: 186–194. Search in Google Scholar

[32] Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova. Quadratic span programs and succinct nizks without PCPs. EUROCRYPT 2013: 626–645. Search in Google Scholar

[33] Craig Gentry and Daniel Wichs. Separating succinct noninteractive arguments from all falsifiable assumptions. STOC 2011: 99–108. Search in Google Scholar

[34] Oded Goldreich. The Foundations of Cryptography - Volume 1: Basic Techniques. Cambridge University Press, 2001. Search in Google Scholar

[35] Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Roth-blum. Delegating computation: Interactive proofs for muggles. Journal of the ACM, 62(4): 27:1–27:64, 2015. Search in Google Scholar

[36] Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 18(1): 186–208, 1989. Search in Google Scholar

[37] Jens Groth. On the size of pairing-based non-interactive arguments. EUROCRYPT (2) 2016: 305–326. Search in Google Scholar

[38] Jens Groth and Yuval Ishai. Sub-linear zero-knowledge argument for correctness of a shuffle. EUROCRYPT 2008: 379–396. Search in Google Scholar

[39] Daira Hopwood, Sean Bowe, Taylor Hornby, and Nathan Wilcox. Zcash Protocol Specification, March 2020. Search in Google Scholar

[40] Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg. Constant-size commitments to polynomials and their applications. ASIACRYPT 2010: 177–194. Search in Google Scholar

[41] Joe Kilian. A note on efficient zero-knowledge proofs and arguments (extended abstract). STOC 1992: 723–732. Search in Google Scholar

[42] Jonathan Lee. Dory: Efficient, transparent arguments for generalised inner products and polynomial commitments. IACR Cryptology ePrint Archive, 2020: 1274. Search in Google Scholar

[43] Rudolf Lidl and Harald Niederreiter. Finite Fields. Second Edition. Cambridge University Press, 1997. Search in Google Scholar

[44] Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. FOCS (1) 1990: 2–10. Search in Google Scholar

[45] Ralph C. Merkle. A certified digital signature. CRYPTO 1989: 218–238. Search in Google Scholar

[46] Silvio Micali. Computationally sound proofs. SIAM Journal on Computing, 30(4): 1253–1298, 2000. Search in Google Scholar

[47] NIST. Common vulnerabilities and exposures. https://nvd.nist.gov/vuln/detail/cve-2019-7167, March 2019. Search in Google Scholar

[48] Srinath Setty. Spartan: Efficient and general-purpose zk-SNARKs without trusted setup. CRYPTO (3) 2020: 704–737. Search in Google Scholar

[49] Adi Shamir. IP = PSPACE. Journal of the ACM, 39(4): 869–877, 1992. Search in Google Scholar

[50] Justin Thaler. Time-optimal interactive proofs for circuit evaluation. CRYPTO (2) 2013: 71–89. Search in Google Scholar

[51] Paul Valiant. Incrementally verifiable computation or proofs of knowledge imply time/space efficiency. TCC 2008: 1–18. Search in Google Scholar

[52] Alexander Vlasov and Konstantin Panarin. Transparent polynomial commitment scheme with polylogarithmic communication complexity. IACR Cryptology ePrint Archive, 2019: 1020. Search in Google Scholar

[53] Riad S. Wahby, Ye Ji, Andrew J. Blumberg, Abhi Shelat, Justin Thaler, Michael Walfish, and Thomas Wies. Full accounting for verifiable outsourcing. CCS 2017: 2071–2086. Search in Google Scholar

[54] Riad S. Wahby, Ioanna Tzialla, Abhi Shelat, Justin Thaler, and Michael Walfish. Doubly-efficient zkSNARKs without trusted setup. IEEE Symposium on Security and Privacy 2018: 926–943. Search in Google Scholar

[55] Tiancheng Xie, Jiaheng Zhang, Yupeng Zhang, Char-alampos Papamanthou, and Dawn Song. Libra: Succinct zero-knowledge proofs with optimal prover computation. CRYPTO (3) 2019: 733–764. Search in Google Scholar

[56] Jiaheng Zhang, Tiancheng Xie, Yupeng Zhang, and Dawn Song. Transparent polynomial delegation and its applications to zero knowledge proof. IEEE Symposium on Security and Privacy 2020: 859–876. Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo