Paper 2021/353

Succinct Publicly Verifiable Computation

Alonso González and Alexandros Zacharakis

Abstract

In this work we construct for the first time a delegation scheme for arithmetic circuits with proof-size and verification complexity comparable to those of pairing based zk-SNARKS (e.g. Gennaro et al. at Eurocrypt 2013 or Groth at Eurocrypt 2016), but based on standard assumptions. Each proof comprises $O(1)$ group elements of a bilinear group and verification requires $O(1)$ pairings plus $n$ exponentiations, where $n$ is the number of inputs. Soundness can be proven under any Matrix Diffie-Hellman (MDDH) assumption of size $k\geq 2$. The size of the reference string as well as the prover's complexity is quadratic in the size of the circuit. Our techniques combine the ideas for constructing delegation schemes of Paneth and Rothblum (TCC 2017), and then refined by Kalai et al. (STOC 2019), with the so called Quasi-Adaptive NIZK arguments for linear languages (Jutla and Roy at Asiacrypt 2014 and Crypto 2015, Libert et al. Eurocrypt 2015, Kiltz and Wee Eurocrypt 2015) and for quadratic languages (González et al. at Asiacrypt 2015 and 2019). We obtain a delegation scheme with asymptotically shorter proofs and verification. Our construction can be turned into a NIZK argument for NP of size $n+O(1)$ group elements under the same assumptions and can be used to construct zk-SNARKs from quantitatively weaker assumptions than the state of the art. Additionally, the NIZK argument for NP yields a compact NIZK for NP with proof size linear in the size of the witness by using the same techniques and improving on Katsumata et al. (Crypto 2019 and Eurocrypt 2020) which has proof size linear in the size of the circuit.