Paper 2011/394

A More Efficient Computationally Sound Non-Interactive Zero-Knowledge Shuffle Argument

Helger Lipmaa and Bingsheng Zhang

Abstract

We propose a new non-interactive (perfect) zero-knowledge (NIZK) shuffle argument that, when compared the only previously known efficient NIZK shuffle argument by Groth and Lu, has a small constant factor times smaller computation and communication, and is based on more standard computational assumptions. Differently from Groth and Lu who only prove the co-soundness of their argument under purely computational assumptions, we prove computational soundness under a necessary knowledge assumption. We also present a general transformation that results in a shuffle argument that has a quadratically smaller common reference string (CRS) and a small constant factor times times longer argument than the original shuffle. 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.

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.