Paper 2019/326
Shorter Pairingbased Arguments under Standard Assumptions
Alonso Gonzalez and Carla Rafols
Abstract
This paper constructs efficient noninteractive 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 QANIZK 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 QANIZK 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 zeroknowledge with GrothSahai 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, constantsize, pairingbased arguments of knowledge transfer with constanttime 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
 20191219: revised
 20190329: 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 Pairingbased Arguments under Standard Assumptions}, howpublished = {Cryptology ePrint Archive, Paper 2019/326}, year = {2019}, note = {\url{https://eprint.iacr.org/2019/326}}, url = {https://eprint.iacr.org/2019/326} }