Cryptology ePrint Archive: Report 2019/148
On the efficiency of pairing-based proofs under the d-PKE
Ariel Gabizon
Abstract: We investigate the minimal number of group elements and prover running time in a zk-SNARK when using only a symmetric ``linear'' knowledge assumption, like the $d$-Power Knowledge of Exponent assumption, rather than a ``quadratic'' one as implicitly happens in the most efficient known construction by Groth [Groth16]. The proofs of
[Groth16] contain only 3 group elements.
We present 4 element proofs for quadratic arithmetic programs/rank 1 constraint systems under the $d$-PKE with very similar prover running time to [Groth16]. Central to our construction is a simple lemma for ``batching'' knowledge checks, which allows us to save one proof element.
Category / Keywords: cryptographic protocols / zk-SNARKs, Knowledge Assumptions
Date: received 12 Feb 2019, last revised 18 Mar 2019
Contact author: ariel gabizon at gmail com
Available format(s): PDF | BibTeX Citation
Version: 20190318:144432 (All versions of this report)
Short URL: ia.cr/2019/148
[ Cryptology ePrint archive ]