Paper 2011/009

Progression-Free Sets and Sublinear Pairing-Based Non-Interactive Zero-Knowledge Arguments

Helger Lipmaa


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.

Note: 19.06.2011 update: Includes many readability updates. The most noteworthy new result: the prover's computational complexity in the new SAT argument is $\Theta (n^2)$ additions (not $\Theta (n^2)$ multiplications, as claimed before).

Available format(s)
Publication info
Published elsewhere. TCC 2012. This is the corresponding full version.
Additive combinatoricsbilinear pairingscircuit satisfiabilitynon-interactive zero-knowledgeprogression-free sets
Contact author(s)
helger lipmaa @ gmail com
2012-01-05: last of 6 revisions
2011-01-05: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.