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.
Category / Keywords: mixnet, obfuscation Publication Info: paper in submission Date: received 2 Nov 2005, last revised 18 Aug 2006 Contact author: ben at mit edu Available formats: PDF | BibTeX Citation Note: new formalization in the public-key obfuscation model, with a UC proof, and numerous corrections. Version: 20060818:124305 (All versions of this report) Discussion forum: Show discussion | Start new discussion