Our main technical result is a ``$1$-sparsity'' argument that has linear CRS length and prover's communication. This should be compared to the basic arguments of Groth (Asiacrypt 2010) and Lipmaa (TCC 2012), where the prover's computational complexity is quadratic. This gives a new insight to the NIZK arguments of Groth and Lipmaa, and we hope that the $1$-sparsity argument (and possible related future basic arguments) can be used to build NIZK arguments for other interesting languages.Category / Keywords: Bilinear pairings, cryptographic shuffle, non-interactive zero-knowledge, progression-free sets Publication Info: Published at SCN 2012 Date: received 21 Jul 2011, last revised 30 Jun 2012 Contact author: helger lipmaa at gmail com Available formats: PDF | BibTeX Citation Note: First eprint version was published on July 21, 2011.
Second eprint version from August 20, 2011, includes proper discussion of culpable soundness.
Third eprint version from May 3, 2012, includes a description of a version with quadratically shorter version of the CRS.
Fourth eprint version from June 30, 2012, is a full version corresponding to a paper published at SCN 2012.Version: 20120630:102857 (All versions of this report) Discussion forum: Show discussion | Start new discussion