How to Shuffle in Public

Ben Adida and Douglas Wikström

Theory of Cryptography Conference — TCC 2007, Lecture Notes in Computer Science, Springer-Verlag, vol. 4392, 2007.

We show how to obfuscate a secret shuffle of ciphertexts: shuffling becomes a public operation. Given a trusted party that samples and obfuscates a shuffle before any ciphertexts are received, this reduces the problem of constructing a mix-net to verifiable joint decryption.

We construct public-key obfuscations of a decryption shuffle based on the Boneh-Goh-Nissim (BGN) cryptosystem and a re-encryption shuffle based on the Paillier cryptosystem. Both allow efficient distributed verifiable decryption.

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 small, yet large enough to handle a number of practical cases, e.g. $N=350$ in the BGN case and $N=2000$ in the Paillier case.

BibTeX Citation

@inproceedings{AdWi07,
    author       = {Ben Adida and Douglas Wikström},
    title        = {How to Shuffle in Public},
    booktitle    = {Theory of Cryptography Conference --- TCC 2007},
    series       = {Lecture Notes in Computer Science},
    volume       = 4392,
    year         = 2007,
    publisher    = {Springer-Verlag},
}

Files and Links

There are currently no associated files available.