Paper 2011/168 Original: eprint.iacr.org/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.
Metadata
- Available format(s)
PDF- Category
- Cryptographic protocols
- Publication info
- Preprint.
- History
- 2011-04-04: last updated
- 2011-04-04: published
- Short URL
- https://ia.cr/2011/168
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}