Cryptology ePrint Archive: Report 2011/168

A Commitment-Consistent Proof of a Shuffle

Douglas Wikstr{\"o}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.

Category / Keywords: cryptographic protocols / proof of a shuffle, mix-net

Publication Info: Conference version of this paper was presented at ACISP 2009.

Date: received 2 Apr 2011

Contact author: dog at csc kth se

Available formats: PDF | BibTeX Citation

Version: 20110404:085433 (All versions of this report)

Discussion forum: Show discussion | Start new discussion