Skip to Main content Skip to Navigation
Conference papers

Shorter Pairing-based Arguments under Standard Assumptions

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 ≈ 4d group elements and the verification cost is ≈ 4d pairings and O(n + n + d) exponentia-tions, 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 satis-fiability 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 C1 and an opening x, such an argument allows to prove that some other commitment C2 opens to f (x), for some function f , even if C2 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [37 references]  Display  Hide  Download

https://hal.inria.fr/hal-02401556
Contributor : Alonso González <>
Submitted on : Tuesday, December 10, 2019 - 9:40:59 AM
Last modification on : Friday, June 25, 2021 - 3:40:05 PM
Long-term archiving on: : Wednesday, March 11, 2020 - 3:19:28 PM

File

main-circuitdepth.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Alonso González, Carla Ràfols. Shorter Pairing-based Arguments under Standard Assumptions. ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Dec 2019, Kobe, Japan. pp.728-757, ⟨10.1007/978-3-030-34618-8_25⟩. ⟨hal-02401556⟩

Share

Metrics

Record views

116

Files downloads

487