Proofs for Inner Pairing Products and Applications

Benedikt Bünz, Mary Maller, Pratyush Mishra, Nirvan Tyagi, Psi Vesely

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We present a generalized inner product argument and demonstrate its applications to pairing-based languages. We apply our generalized argument to prove that an inner pairing product is correctly evaluated with respect to committed vectors of n source group elements. With a structured reference string (SRS), we achieve a logarithmic-time verifier whose work is dominated by 6 log n target group exponentiations. Proofs are of size 6 log n target group elements, computed using 6n pairings and 4n exponentiations in each source group. We apply our inner product arguments to build the first polynomial commitment scheme with succinct (logarithmic) verification, O(d) prover complexity for degree d polynomials (not including the cost to evaluate the polynomial), and a SRS of size O(d). Concretely, this means that for d= 228, producing an evaluation proof in our protocol is 76 × faster than doing so in the KZG commitment scheme, and the CRS in our protocol is 1000 × smaller: 13 MB vs 13 GB for KZG. As a second application, we introduce an argument for aggregating n Groth16 zkSNARKs into an O(log n) sized proof. Our protocol is significantly faster (> 1000 × ) than aggregating SNARKs via recursive composition: we aggregate ∼ 130, 000 proofs in 25 min, versus 90 proofs via recursive composition. Finally, we further apply our aggregation protocol to construct a low-memory SNARK for machine computations that does not rely on recursive composition. For a computation that requires time T and space S, our SNARK produces proofs in space O~ (S+ T), which is significantly more space efficient than a monolithic SNARK, which requires space O~ (S· T).

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – ASIACRYPT 2021 - 27th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Part 3
EditorsMehdi Tibouchi, Huaxiong Wang
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages33
ISBN (Print)9783030920777
StatePublished - 2021
Event27th International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2021 - Virtual, Online
Duration: Dec 6 2021Dec 10 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13092 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference27th International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2021
CityVirtual, Online

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Proofs for Inner Pairing Products and Applications'. Together they form a unique fingerprint.

Cite this