Paper 2011/009 Original: eprint.iacr.org/2011/009 ↗
Progression-Free Sets and Sublinear Pairing-Based Non-Interactive Zero-Knowledge Arguments
Abstract
In 2010, Groth constructed the only previously known sublinear-communication NIZK circuit satisfiability argument in the common reference string model. We optimize Groth's argument by, in particular, reducing both the CRS length and the prover's computational complexity from quadratic to quasilinear in the circuit size. We also use a (presumably) weaker security assumption, and have tighter security reductions. Our main contribution is to show that the complexity of Groth's basic arguments is dominated by the quadratic number of monomials in certain polynomials. We collapse the number of monomials to quasilinear by using a recent construction of progression-free sets.
Metadata
- Available format(s)
PDF- Publication info
- Preprint.
- History
- 2012-01-05: last updated
- 2011-01-05: published
- Short URL
- https://ia.cr/2011/009
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2011/009,
author = {Helger Lipmaa},
title = {Progression-Free Sets and Sublinear Pairing-Based Non-Interactive Zero-Knowledge Arguments},
howpublished = {Cryptology {ePrint} Archive, Paper 2011/009},
year = {2011},
url = {https://eprint.iacr.org/2011/009}
}