A protocol is given that allows a set of n servers to cooperate and produce an ElGamal ciphertext encrypted under one key from an ElGamal ciphertext encrypted under another, but without plaintext ever becoming available. The protocol is resilient to floor(n-1)/3 of the servers being compromised and requires no assumptions about execution speeds or message delivery delays. Two new building blocks employed---a distributed blinding protocol and verifiable dual encryption proofs---could have uses beyond re-encryption protocols.