Abstract
We construct a new polynomial commitment scheme for multivariate polynomials over finite fields, with public-coin evaluation proofs that have logarithmic communication in the degree of the polynomial. The techniques are reminiscent of Diophantine Arguments of Knowledge (Lipmaa, Asiacrypt'03), leveraging integer representations of polynomials and groups of unknown order. Security is shown from falsifiable assumptions that hold in generic groups. Moreover, the scheme does not require a trusted setup if instantiated with class groups. We apply this new cryptographic compiler to a restricted class of algebraic linear IOPs in order to obtain doubly-efficient public-coin IPs with succinct communication and witness-extended emulation for any NP relation. Allowing for linear preprocessing, the online verifier's work is logarithmic in the circuit complexity of the relation.
Concretely, we obtain quasi-linear prover time when compiling the IOP employed in Sonic[MBKM19] based on bivariate Laurent polynomials. Applying the Fiat-Shamir transform in the random oracle model results in a transparent SNARK system with quasi-linear preprocessing, quasi-linear (online) prover time, logarithmic proof size, and logarithmic (online) verification time for arbitrary circuits. We also obtain zk-SNARKs by applying a hiding/zero-knowledge variant of our polynomial commitment scheme, which is secure in the generic group model. This is the first transparent zk-SNARK (i.e. without trusted setup) that has both a practical prover time as well as strictly logarithmic proof size and verification time. We call our system Supersonic.