Paper 2021/588

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

Thomas Haines and Johannes Mueller


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).

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. 26th Australasian Conference on Information Security and Privacy
zero knowledge
Contact author(s)
thomas haines @ ntnu no
2021-05-10: received
Short URL
Creative Commons Attribution


      author = {Thomas Haines and Johannes Mueller},
      title = {A Novel Proof of Shuffle: Exponentially Secure Cut-and-Choose},
      howpublished = {Cryptology ePrint Archive, Paper 2021/588},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.