Ligero: Lightweight Sublinear Arguments Without a Trusted Setup

ABSTRACT

We design and implement a simple zero-knowledge argument protocol for NP whose communication complexity is proportional to the square-root of the verification circuit size. The protocol can be based on any collision-resistant hash function. Alternatively, it can be made non-interactive in the random oracle model, yielding concretely efficient zk-SNARKs that do not require a trusted setup or public-key cryptography.

Our protocol is attractive not only for very large verification circuits but also for moderately large circuits that arise in applications. For instance, for verifying a SHA-256 preimage in zero-knowledge with 2^-40 soundness error, the communication complexity is roughly 44KB (or less than 34KB under a plausible conjecture), the prover running time is 140 ms, and the verifier running time is 62 ms. This proof is roughly 4 times shorter than a similar proof of ZKB++ (Chase et al., CCS 2017), an optimized variant of ZKBoo (Giacomelli et al., USENIX 2016).

The communication complexity of our protocol is independent of the circuit structure and depends only on the number of gates. For 2^-40 soundness error, the communication becomes smaller than the circuit size for circuits containing roughly 3 million gates or more. Our efficiency advantages become even bigger in an amortized setting, where several instances need to be proven simultaneously.

Our zero-knowledge protocol is obtained by applying an optimized version of the general transformation of Ishai et al. (STOC 2007) to a variant of the protocol for secure multiparty computation of Damgard and Ishai (Crypto 2006). It can be viewed as a simple zero-knowledge interactive PCP based on "interleaved" Reed-Solomon codes.

References

1. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. 1998. Proof Verification and the Hardness of Approximation Problems. J. ACM 45, 3 (1998), 501--555.
2. Sanjeev Arora and Shmuel Safra. 1998. Probabilistic Checking of Proofs: A New Characterization of NP. J. ACM 45, 1 (1998), 70--122.
3. László Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy. 1991. Checking Computations in Polylogarithmic Time. In STOC. 21--31.
4. Eli Ben-Sasson, Iddo Bentov, Alessandro Chiesa, Ariel Gabizon, Daniel Genkin, Matan Hamilis, Evgenya Pergament, Michael Riabzev, Mark Silberstein, Eran Tromer, and Madars Virza. 2017. Computational Integrity with a Public Random String from Quasi-Linear PCPs. In EUROCRYPT. 551--579.
5. Eli Ben-Sasson, Iddo Bentov, Ynon Horesh, and Michael Riabzev. 2017. Scalable, transparent, and post-quantum secure computational integrity. Manuscript. (2017). Slides at https://people.eecs.berkeley.edu/~alexch/docs/pcpip_bensasson. pdf.
6. Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, and Nicholas Spooner. 2016. Short Interactive Oracle Proofs with Constant Query Complexity, via Composition and Sumcheck. IACR Cryptology ePrint Archive 2016 (2016), 324.
7. Eli Ben-Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, and Madars Virza. 2014. Zerocash: Decentralized Anonymous Payments from Bitcoin. In 2014 IEEE Symposium on Security and Privacy, SP 2014, Berkeley, CA, USA, May 18--21, 2014. 459--474.
8. Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, and Eran Tromer. 2013. On the concrete efficiency of probabilistically-checkable proofs. In Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1--4, 2013. 585--594.
9. Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner. 2016. Interactive Oracle Proofs. In TCC. 31--60.
10. Eli Ben-Sasson, Matan Hamilis, Mark Silberstein, and Eran Tromer. 2016. Fast Multiplication in Binary Fields on GPUs via Register Cache. In Proceedings of the 2016 International Conference on Supercomputing, ICS 2016, Istanbul, Turkey, June 1--3, 2016. 35:1--35:12.
11. Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer. 2013. Recursive composition and bootstrapping for SNARKS and proof-carrying data. In STOC. 111--120.
12. Nir Bitansky, Alessandro Chiesa, Yuval Ishai, Rafail Ostrovsky, and Omer Paneth. 2013. Succinct Non-interactive Arguments via Linear Interactive Proofs. In TCC. 315--333.
13. Melissa Chase, David Derler, Steven Goldfeder, Claudio Orlandi, Sebastian Ramacher, Christian Rechberger, Daniel Slamanig, and Greg Zaverucha. 2017. PostQuantum Zero-Knowledge and Signatures from Symmetric-Key Primitives. IACR Cryptology ePrint Archive 2017 (2017), 279.
14. Hao Chen and Ronald Cramer. 2006. Algebraic Geometric Secret Sharing Schemes and Secure Multi-Party Computations over Small Fields. In CRYPTO. 521--536.
15. Graham Cormode, Michael Mitzenmacher, and Justin Thaler. 2012. Practical verified computation with streaming interactive proofs. In ITCS. 90--112. [16] Ivan Damgård and Yuval Ishai. 2006. Scalable Secure Multiparty Computation. In CRYPTO. 501--520.
16. Ivan Damgård, Yuval Ishai, and Mikkel Krøigaard. 2010. Perfectly Secure Multiparty Computation and the Computational Overhead of Cryptography. In EUROCRYPT. 445--465.
17. George Danezis, Cédric Fournet, Markulf Kohlweiss, and Bryan Parno. 2013. Pinocchio coin: building zerocoin from a succinct pairing-based proof system. In PETShop'13, Proceedings of the 2013 ACM Workshop on Language Support for Privacy-Enhancing Technologies, Co-located with CCS 2013, November 4, 2013, Berlin, Germany. 27--30.
18. Amos Fiat and Adi Shamir. 1986. How to Prove Yourself: Practical Solutions to Identification and Signature Problems. In CRYPTO. 186--194.
19. Shuhong Gao and Todd Mateer. 2010. Additive Fast Fourier Transforms over Finite Fields. IEEE Trans. Inf. Theor. 56, 12 (Dec. 2010), 6265--6272.
20. Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova. 2013. Quadratic Span Programs and Succinct NIZKs without PCPs. In EUROCRYPT. 626--645.
21. Irene Giacomelli, Jesper Madsen, and Claudio Orlandi. 2016. ZKBoo: Faster Zero-Knowledge for Boolean Circuits. In USENIX. 1069--1083.
22. Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. 2015. Delegating Computation: Interactive Proofs for Muggles. J. ACM 62, 4 (2015), 27:1--27:64.
23. Shafi Goldwasser, Silvio Micali, and Charles Rackoff. 1985. The Knowledge Complexity of Interactive Proof-Systems (Extended Abstract). In STOC. 291-- 304.
24. Vipul Goyal, Yuval Ishai, Mohammad Mahmoody, and Amit Sahai. 2010. Interactive Locking, Zero-Knowledge PCPs, and Unconditional Cryptography. In CRYPTO. 173--190.
25. Jens Groth. 2009. Linear Algebra with Sub-linear Zero-Knowledge Arguments. In CRYPTO. 192--208.
26. Jens Groth. 2010. Short Pairing-Based Non-interactive Zero-Knowledge Arguments. In ASIACRYPT. 321--340.
27. Yuval Ishai, Eyal Kushilevitz, and Rafail Ostrovsky. 2007. Efficient Arguments without Short PCPs. In CCC. 278--291.
28. Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai. 2007. Zeroknowledge from secure multiparty computation. In STOC. 21--30.
29. Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai. 2009. ZeroKnowledge Proofs from Secure Multiparty Computation. SIAM J. Comput. 39, 3 (2009), 1121--1152.
30. Yuval Ishai, Mohammad Mahmoody, and Amit Sahai. 2012. On Efficient ZeroKnowledge PCPs. In TCC. 151--168.
31. Yuval Ishai, Manoj Prabhakaran, and Amit Sahai. 2008. Founding Cryptography on Oblivious Transfer - Efficiently. In CRYPTO. 572--591.
32. Yuval Ishai, Manoj Prabhakaran, and Amit Sahai. 2009. Secure Arithmetic Computation with No Honest Majority. In TCC. 294--314. Full version: IACR Cryptology ePrint Archive 2008: 465.
33. Yuval Ishai and Mor Weiss. 2014. Probabilistically Checkable Proofs of Proximity with Zero-Knowledge. In TCC. 121--145.
34. Yael Tauman Kalai and Ran Raz. 2008. Interactive PCP. In ICALP. 536--547.
35. Joe Kilian. 1992. A Note on Efficient Zero-Knowledge Proofs and Arguments (Extended Abstract). In STOC. 723--732.
36. Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan. 1990. Algebraic Methods for Interactive Proof Systems. 2--10.
37. Ralph C. Merkle. 1989. A Certified Digital Signature. In CRYPTO. 218--238.
38. Silvio Micali. 1994. CS Proofs (Extended Abstracts). In FOCS. 436--453.
39. Alexander Polishchuk and Daniel A. Spielman. 1994. Nearly-linear size holographic proofs. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23--25 May 1994, Montréal, Québec, Canada. 194--203.
40. Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum. 2016. Constant-round interactive proofs for delegating computation. In STOC. 49--62.
41. Srinath T. V. Setty, Benjamin Braun, Victor Vu, Andrew J. Blumberg, Bryan Parno, and Michael Walfish. 2013. Resolving the conflict between generality and plausibility in verified computation. In Eighth Eurosys Conference 2013, EuroSys '13, Prague, Czech Republic, April 14--17, 2013. 71--84.
42. Srinath T. V. Setty, Richard McPherson, Andrew J. Blumberg, and Michael Wal-fish. 2012. Making argument systems for outsourced computation practical (sometimes). In 19th Annual Network and Distributed System Security Symposium, NDSS 2012, San Diego, California, USA, February 5--8, 2012.
43. Adi Shamir. 1990. IP=PSPACE. 11--15.
44. Justin Thaler. 2013. Time-Optimal Interactive Proofs for Circuit Evaluation. In CRYPTO. 71--89.
45. Victor Vu, Srinath T. V. Setty, Andrew J. Blumberg, and Michael Walfish. 2013. A Hybrid Architecture for Interactive Verifiable Computation. In SP. 223--237.
46. Michael Walfish and Andrew J. Blumberg. 2015. Verifying computations without reexecuting them. Commun. ACM 58, 2 (2015), 74--84.
47. Yupeng Zhang, Daniel Genkin, Jonathan Katz, Dimitrios Papadopoulos, and Charalampos Papamanthou. 2017. vSQL: Verifying Arbitrary SQL Queries over Dynamic Outsourced Databases. In 2017 IEEE Symposium on Security and Privacy, SP 2017, San Jose, CA, USA, May 22--26, 2017. 863--880.

Index Terms

• Security and privacy

  • Cryptography

  • Network security

    • Security protocols