Date: 17/05/2012 Location: J. Liivi 2, room 315
Speaker: Helger Lipmaa
Title: Progression-Free Sets and Sublinear Pairing-Based Non-Interactive Zero-Knowledge Arguments
Abstract:
In Asiacrypt 2010, Groth constructed the only previously known sublinear-communication NIZK argument for circuit satisfiability in the common reference string model. We propose a more efficient NIZK argument. In particular, we reduce both the CRS length and the prover’s computational complexity from quadratic to quasilinear. We also use a (presumably) weaker security assumption than Groth, and have tighter security reductions. From a theoretical perspective, we achieve the mentioned efficiency gain by using a (seemingly natural, but at the end quite non-trivial) connection with the theory of progression-free sets and with additive combinatorics in general. While bilinear protocols seem to be specifically suited for using methods from additive combinatorics, we are not aware of any previous work that has made this connection. We hope that more applications of this connection will be found in the future.