Cryptology ePrint Archive: Report 2011/168
A Commitment-Consistent Proof of a Shuffle
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 format(s): PDF | BibTeX Citation
Version: 20110404:085433 (All versions of this report)
Short URL: ia.cr/2011/168
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]