Flash mixing

Abstract

By introducing novel methods for robust protocol design, to substitute for costly zero-knowledge schemes, we are able to produce a mixing scheme with significantly lower costs of operation than all previously known such schemes. The scheme takes a list of ElGamal encrypted messages, and produces as output a permuted list of encryptions of the same plaintext messages, such that corresponding items of the input and output cannot be correlated. For reasonably large inputs, the cost per participating server and element to be mixed is less than 200 modular multiplications, which is almost two orders of magnitude faster than the most efficient previously known method. The scheme has the novel feature of not requiring the knowledge of a secret key corresponding to the public key used to encrypt the messages constituting the input to the mix-network.