A Commitment-Consistent Proof of a Shuffle

Douglas Wikström

Paper 2011/168

A Commitment-Consistent Proof of a Shuffle

Douglas Wikström

Abstract

We introduce a pre-computation technique that drastically reduces the online computational complexity of mix-nets based on homomorphic cryptosystems. More precisely, we show that there is a permutation commitment scheme that allows a mix-server to: (1) commit to a permutation and efficiently prove knowledge of doing so correctly in the offline phase, and (2) shuffle its input and give an extremely efficient commitment-consistent proof of a shuffle in the online phase. We prove our result for a general class of shuffle maps that generalize all known types of shuffles, and even allows shuffling ciphertexts of different cryptosystems in parallel.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Conference version of this paper was presented at ACISP 2009.
Keywords: proof of a shuffle mix-net
Contact author(s): dog @ csc kth se
History: 2011-04-04: received
Short URL: https://ia.cr/2011/168
License: CC BY

BibTeX

@misc{cryptoeprint:2011/168,
      author = {Douglas Wikström},
      title = {A Commitment-Consistent Proof of a Shuffle},
      howpublished = {Cryptology {ePrint} Archive, Paper 2011/168},
      year = {2011},
      url = {https://eprint.iacr.org/2011/168}
}