CryptoDB
Shorter Pairing-Based Arguments Under Standard Assumptions
| Authors: | |
|---|---|
| Download: | |
| 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 $$\approx 4d$$ 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. |
BibTeX
@article{asiacrypt-2019-30079,
title={Shorter Pairing-Based Arguments Under Standard Assumptions},
booktitle={Advances in Cryptology – ASIACRYPT 2019},
series={Advances in Cryptology – ASIACRYPT 2019},
publisher={Springer},
volume={11923},
pages={728-757},
doi={10.1007/978-3-030-34618-8_25},
author={Alonso González and Carla Ràfols},
year=2019
}