Paper 2019/326
Shorter Pairing-based Arguments under Standard Assumptions
Alonso Gonzalez and Carla Rafols
Abstract
This paper constructs efficient non-interactive arguments for correct evaluation of arithmetic and boolean circuits with proof size $O(d)$ group elements, where $d$ is the multiplicative depth of the circuit, under falsifiable assumptions. This is achieved by combining techniques from SNARKs and QA-NIZK arguments of membership in linear spaces. The first construction is very efficient (the proof size is $\approx4d$ group elements and the verification cost is $\approx 4d$ pairings and $O(n+n'+d)$ exponentiations, where $n$ is the size of the input and $n'$ of the output) but one type of attack can only be ruled out assuming the knowledge soundness of QA-NIZK arguments of membership in linear spaces. We give an alternative construction which replaces this assumption with a decisional assumption in bilinear groups at the cost of approximately doubling the proof size. The construction for boolean circuits can be made zero-knowledge with Groth-Sahai proofs, resulting in a NIZK argument for circuit satisfiability based on falsifiable assumptions in bilinear groups of proof size $O(n+d)$. Our main technical tool is what we call an ``argument of knowledge transfer''. Given a commitment $C_1$ and an opening $x$, such an argument allows to prove that some other commitment $C_2$ opens to $f(x)$, for some function $f$, even if $C_2$ is not extractable. We construct very short, constant-size, pairing-based arguments of knowledge transfer with constant-time verification for any linear function and also for Hadamard products. These allow to transfer the knowledge of the input to lower levels of the circuit.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- A minor revision of an IACR publication in ASIACRYPT 2019
- Keywords
- zero knowledge
- Contact author(s)
- carla rafols @ upf edu
- History
- 2019-12-19: revised
- 2019-03-29: received
- See all versions
- Short URL
- https://ia.cr/2019/326
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2019/326, author = {Alonso Gonzalez and Carla Rafols}, title = {Shorter Pairing-based Arguments under Standard Assumptions}, howpublished = {Cryptology {ePrint} Archive, Paper 2019/326}, year = {2019}, url = {https://eprint.iacr.org/2019/326} }