Universal Re-encryption for Mixnets
December 6, 2002
Markus Jakobsson, RSA Laboratories
We introduce a new cryptographic technique that we call universal re-encryption. A conventional cryptosystem that permits re-encryption, such as ElGamal, does so only for a player with knowledge of the public key corresponding to a given ciphertext. In contrast, universal re-encryption may be performed without knowledge of public keys. We demonstrate an asymmetric cryptosystem with universal re-encryption that is half as efficient as standard ElGamal in terms of both computation and storage.
While technically and conceptually simple, universal re-encryption leads to new types of functionality in mixnet architectures. Conventional mixnets are often called upon to enable players to communicate with one another through channels that are externally anonymous, i.e., that hide information permitting traffic-analysis. Universal re-encryption permits a mixnet of this kind to be constructed in which servers hold no public or private keying material, and may therefore dispense with the cumbersome requirements of key generation, key distribution, and private-key management.
We describe two highly practical mixnet constructions, one involving asymmetric input ciphertexts, and another for hybrid-ciphertext inputs.
This is joint work with Philippe Golle, Ari Juels, and Paul Syverson The paper will be made available on www.markus-jakobsson.com.
Co-Sponsored by Laboratory for Secure Systems and New Jersey Institute for Trustworthy Enterprise Software.