Ligero: Lightweight Sublinear Arguments Without a Trusted Setup

We design and implement a simple zero-knowledge argument protocol for NP whose communication complexity is proportional to the square-root of the veri cation 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 e cient zk-SNARKs that do not require a trusted setup or public-key cryptography. Our protocol is attractive not only for very large veri cation circuits but also for moderately large circuits that arise in applications. For instance, for verifying a SHA-256 preimage in zeroknowledge 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 veri er 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 e ciency 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 Damgård and Ishai (Crypto 2006). It can be viewed as a simple zero-knowledge interactive PCP based on "interleaved" Reed-Solomon codes. INTRODUCTION Verifying outsourced computations is important for tasks and scenarios when there is an incentive for the party performing the computation to report incorrect answers. In this work, we present