Paper 2005/394

How to Shuffle in Public

Ben Adida and Douglas Wikström

Abstract

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.

Note: new formalization in the public-key obfuscation model, with a UC proof, and numerous corrections.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. paper in submission
Keywords
mixnetobfuscation
Contact author(s)
ben @ mit edu
History
2006-08-18: last of 6 revisions
2005-11-02: received
See all versions
Short URL
https://ia.cr/2005/394
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2005/394,
      author = {Ben Adida and Douglas Wikström},
      title = {How to Shuffle in Public},
      howpublished = {Cryptology ePrint Archive, Paper 2005/394},
      year = {2005},
      note = {\url{https://eprint.iacr.org/2005/394}},
      url = {https://eprint.iacr.org/2005/394}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.