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.
Category / Keywords: Zero-Knowledge, Shuffle Argument Original Publication (in the same form): IACR-PKC-2021 Date: received 28 Feb 2021 Contact author: simkin at cs au dk, mail at nilsfleischhacker de Available format(s): PDF | BibTeX Citation Version: 20210302:203004 (All versions of this report) Short URL: ia.cr/2021/228