Welcome to the resource topic for 2019/326
Title:
Shorter Pairing-based Arguments under Standard Assumptions
Authors: Alonso Gonzalez, 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.
ePrint: https://eprint.iacr.org/2019/326
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .