[Resource Topic] 2005/394: How to Shuffle in Public

Welcome to the resource topic for 2005/394

How to Shuffle in Public

Authors: Ben Adida, Douglas Wikström


We show how to public-key obfuscate two commonly used shuffles:
decryption shuffles which permute and decrypt ciphertexts, and
re-encryption shuffles which permute and re-encrypt ciphertexts. Given
a trusted party that samples and obfuscates a shuffle \emph{before}
any ciphertexts are received, this reduces the problem of constructing
a mix-net to verifiable joint decryption.

We construct a decryption shuffle from any additively homomorphic
cryptosystem and show how it can be public-key obfuscated. This
construction does not allow efficient distributed verifiable
decryption. Then we show how to public-key obfuscate: a decryption
shuffle based on the Boneh-Goh-Nissim (BGN) cryptosystem, and a
re-encryption shuffle based on the Paillier cryptosystem. Both
constructions allow \emph{efficient} distributed verifiable
decryption. In the Paillier case we identify and exploit a previously
overlooked ``homomorphic’’ property of the cryptosystem.

Finally, we give a distributed protocol for sampling and obfuscating
each of the above shuffles and show how it can be used in a trivial
way to construct a universally composable mix-net. Our constructions
are practical when the number of senders N is reasonably small,
e.g. N=350 in the BGN case and N=2000 in the Paillier case.

ePrint: https://eprint.iacr.org/2005/394

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .