Paper 2021/228

On Publicly-Accountable Zero-Knowledge and Small Shuffle Arguments

Nils Fleischhacker and Mark Simkin


Constructing interactive zero-knowledge arguments from simple assumptions with small communication complexity and good computational efficiency is an important, but difficult problem. In this work, we study interactive arguments with noticeable soundness error in their full generality and for the specific purpose of constructing concretely efficient shuffle arguments. To counterbalance the effects of a larger soundness error, we show how to transform such three-move arguments into publicly-accountable ones which allow the verifier to convince third parties of detected misbehavior by a cheating prover. This may be particularly interesting for applications where a malicious prover has to balance the profits it can make from cheating successfully and the losses it suffers from being caught. %In contrast to standard sequential repetition, our transformation increases the round and communication complexity by only a small additive factor. We construct interactive, public-coin, zero-knowledge arguments with noticeable soundness error for proving that a target vector of commitments is a pseudorandom permutation of a source vector. Our arguments do not rely on any trusted setup and only require the existence of collision-resistant hash functions. The communication complexity of our arguments is \emph{independent} of the length of the shuffled vector. For a soundness error of $2^{-5}=1/32$, the communication cost is $153$ bytes without and $992$ bytes with public accountability, meaning that our arguments are shorter than shuffle arguments realized using Bulletproofs (IEEE S\&P 2018) and even competitive in size with SNARKs, despite only relying on simple assumptions.

Available format(s)
Publication info
Published by the IACR in Pkc 2021
Zero-KnowledgeShuffle Argument
Contact author(s)
simkin @ cs au dk
mail @ nilsfleischhacker de
2021-03-02: received
Short URL
Creative Commons Attribution


      author = {Nils Fleischhacker and Mark Simkin},
      title = {On Publicly-Accountable Zero-Knowledge and Small Shuffle Arguments},
      howpublished = {Cryptology ePrint Archive, Paper 2021/228},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.