Groth, J;
(2016)
On the Size of Pairing-Based Non-interactive Arguments.
In: Fischlin, M and Coron, J-S, (eds.)
EUROCRYPT 2016: Advances in Cryptology – EUROCRYPT 2016.
(pp. pp. 305-326).
Springer International Publishing AG
Preview |
Text
Groth_SNARK9.pdf - Accepted Version Download (419kB) | Preview |
Abstract
Non-interactive arguments enable a prover to convince a verifier that a statement is true. Recently there has been a lot of progress both in theory and practice on constructing highly efficient non-interactive arguments with small size and low verification complexity, so-called succinct non-interactive arguments (SNARGs) and succinct non-interactive arguments of knowledge (SNARKs). 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 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.
Type: | Proceedings paper |
---|---|
Title: | On the Size of Pairing-Based Non-interactive Arguments |
Event: | EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques |
Location: | Vienna, Austria |
Dates: | 08 May 2016 - 12 May 2016 |
ISBN-13: | 9783662498958 |
Open access status: | An open access version is available from UCL Discovery |
DOI: | 10.1007/978-3-662-49896-5_11 |
Publisher version: | http://dx.doi.org/10.1007/978-3-662-49896-5_11 |
Language: | English |
Additional information: | © International Association for Cryptologic Research 2016. The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-662-49896-5_11 |
Keywords: | SNARKs; Non-interactive zero-knowledge arguments; Linear interactive proofs; Quadratic arithmetic programs; Bilinear groups |
UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
URI: | https://discovery.ucl.ac.uk/id/eprint/1501201 |
Archive Staff Only
View Item |