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

Helger Lipmaa. Progression-Free Sets and Sublinear Pairing-Based Non-Interactive Zero-Knowledge Arguments. In Ronald Cramer, editor, *TCC 2012*, volume 7194 of *Lecture Notes in Computer Science*, pages 169--189, Taormina, Italy, March 18--21, 2012. Springer, Heidelberg.

**File:**
[.pdf (452 KB)] __pdf recommended__.

**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..

**Keywords:** Additive combinatorics, bilinear pairings, circuit satisfiability, non-interactive zero-knowledge, progression-free sets.

**Comment:**
Conference version misses several proofs, etc. Full version
available from http://eprint.iacr.org/2011/009.

Known typos: in description of Groth's argument (third paragraph of Section
3, it is written that $B$ is a commitment on the generator set $(g_1,
\ldots, g_n)$ and $C$ is a commitment on the generator set $(g_{n + 1},
\ldots, g_{n (n + 1)})$. It should be the other way around. (Thanks to
Ananth Raghunathan for noticing it) It is also written that $C$ is a
commitment to $\mathbf{b}$ --- instead it is a commitment to
$\mathbf{c}$.

**More information:** Publisher Webpage.

**Authors:**

Page by Helger Lipmaa. Send your inqueries to `<helger.lipmaa>gmail.com`.