[Resource Topic] 2011/394: A More Efficient Computationally Sound Non-Interactive Zero-Knowledge Shuffle Argument

Welcome to the resource topic for 2011/394

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

Authors: Helger Lipmaa, Bingsheng Zhang


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.

ePrint: https://eprint.iacr.org/2011/394

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .