UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

On the Size of Pairing-Based Non-interactive Arguments

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 Green open access

[thumbnail of Groth_SNARK9.pdf]
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
Downloads since deposit
585Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item