Many constructions of SNARGs rely on pairing-based cryptography. In these constructions a proof consists of a number of group elements and the verification consists of checking a number of pairing product equations. The question we address in this article is how efficient pairing-based SNARGs can be.
Our first contribution is a pairing-based (preprocessing) SNARK for arithmetic circuit satisfiability, which is an NP-complete language. In our SNARK we work with asymmetric pairings for higher efficiency, a proof is only 3 group elements, and verification consists of checking a single pairing product equations using 3 pairings in total. Our SNARK is zero-knowledge and does not reveal anything about the witness the prover uses to make the proof.
As our second contribution we answer an open question of Bitansky, Chiesa, Ishai, Ostrovsky and Paneth (TCC 2013) by showing that 2-move linear interactive proofs cannot have a linear decision procedure. It follows from this that SNARGs where the prover and verifier use generic asymmetric bilinear group operations cannot consist of a single group element. This gives the first lower bound for pairing-based SNARGs. It remains an intriguing open problem whether this lower bound can be extended to rule out 2 group element SNARGs, which would prove optimality of our 3 element construction.Category / Keywords: SNARKs, non-interactive zero-knowledge arguments, linear interactive proofs, quadratic arithmetic programs, bilinear groups Original Publication (with minor differences): IACR-EUROCRYPT-2016 Date: received 8 Mar 2016, last revised 31 May 2016 Contact author: j groth at ucl ac uk Available format(s): PDF | BibTeX Citation Version: 20160531:125532 (All versions of this report) Short URL: ia.cr/2016/260 Discussion forum: Show discussion | Start new discussion