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 shufflemix-net
Contact author(s)
dog @ csc kth se
History
2011-04-04: received
Short URL
https://ia.cr/2011/168
License
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2011/168}},
      url = {https://eprint.iacr.org/2011/168}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.