Cryptology ePrint Archive: Report 2005/394

Obfuscated Ciphertext Mixing

Ben Adida and Douglas Wikström

Abstract. Mixnets are a type of anonymous channel composed of a handful of trustees that, each in turn, shuffle and rerandomize a batch ciphertexts. For applications that require verifiability, each trustee provides a proof of correct mixing. Though mixnets have recently been made quite efficient, they still require secret computation and proof generation after the mixing process. We introduce and implement Obfuscated Ciphertext Mixing, the obfuscation of a mixnet program. Using this technique, all proofs can be performed before the mixing process, even before the inputs are available. In addition, the mixing program does not need to be secret: anyone can publicly compute the shuffle (though not the decryption). We frame this functionality in the strongest obfuscation setting proposed by Barak et. al., tweaked for the public-key setting. For applications where the secrecy of the shuffle permutation is particularly important (e.g. voting), we also consider the Distributed Obfuscation of a Mixer, where multiple trustees cooperate to generate an obfuscated mixer program such that no single trustee knows the composed shuffle permutation.

Category / Keywords. mixnet, program obfuscation

Publication Info. in submission

Date: received 2 Nov 2005, last revised 21 Nov 2005

Contact author: ben at mit edu

Available formats: PDF | BibTeX Citation

Comment. revised with formalized security definitions, framing in the obfuscation model, and more detailed proofs. (Added author names, which were missing briefly from second revision.)