Cryptology ePrint Archive: Report 2021/588

A Novel Proof of Shuffle: Exponentially Secure Cut-and-Choose

Thomas Haines and Johannes Mueller

Abstract: Shuffling is one of the most important techniques for privacy-preserving protocols. Its applications are manifold, including, for example, e-voting, anonymous broadcast, or privacy-preserving machine-learning. For many applications, such as secure e-voting, it is crucial that the correctness of the shuffling operation be (publicly) verifiable. To this end, numerous proofs of shuffle have been proposed in the literature. Several of these proofs are actually employed in the real world.

In this work, we propose a generic compiler which can transform any "shuffle-compatible" Sigma-protocol (including, among others, Sigma-protocols for re-randomization, decryption, or key shifting) into a Sigma-protocol for permutations of the underlying relation. The resulting proof of shuffle is black-box, easily implementable, simple to explain, and comes with an acceptable computational overhead over the state-of-the-art. Because we machine-checked our compiler in Coq, the new proof of shuffle is particularly suitable for applications that require a superior level of security assurance (e.g., high-stake elections).

Category / Keywords: cryptographic protocols / zero knowledge

Original Publication (with minor differences): 26th Australasian Conference on Information Security and Privacy

Date: received 4 May 2021

Contact author: thomas haines at ntnu no

Available format(s): PDF | BibTeX Citation

Version: 20210510:082554 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]