Progression-free sets and sublinear pairing-based non-interactive zero-knowledge arguments. (English) Zbl 1303.94090
Cramer, Ronald (ed.), Theory of cryptography. 9th theory of cryptography conference, TCC 2012, Taormina, Sicily, Italy, March 19–21, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-28913-2/pbk). Lecture Notes in Computer Science 7194, 169-189 (2012).
Summary: In 2010, J. Groth [ASIACRYPT 2010, Lect. Notes Comput. Sci. 6477, 321–340 (2010; Zbl 1253.94049)] 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.
For the entire collection see [Zbl 1238.94002].
For the entire collection see [Zbl 1238.94002].
