Parallel mixing
Authors:
Open Access
- 25 October 2004
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 220-226
Abstract
Efforts to design faster synchronous mix networks have focused on reducing the computational cost of mixing per server. We propose a different approach: our reencryption mixnet allows servers to mix inputs in parallel. The result is a dramatic reduction in overall mixing time for moderate-to-large numbers of servers. As measured in the model we describe, for n inputs and $M$ servers our parallel re encryption mixnet produces output in time at most 2n -- and only around n assuming a majority of honest servers. In contrast, a traditional, sequential, synchronous re-encryption mixnet requires time Mn. Parallel re-encryption mixnets offer security guarantees comparable to those of synchronous mixnets, and in many cases only a slightly weaker guarantee of privacy. Our proposed construction is applicable to many recently proposed re-encryption mixnets, such as those of Furukawa and Sako, Neff, Jakobsson et al., and Golle and Boneh. In practice, parallel mixnets promise a potentially substantial time saving in applications such as anonymous electronic elections.
Keywords
This publication has 9 references indexed in Scilit:
- Synchronous Batching: From Cascades to Free RoutesLecture Notes in Computer Science, 2005
- Almost entirely correct mixing with applications to voting2002
- A verifiable secret shuffle and its application to e-voting2001
- An optimally robust hybrid mix network2001
- Random oracles in constantipole2000
- Flash mixing1999
- Cryptographic defense against traffic analysis1993
- Untraceable electronic mail, return addresses, and digital pseudonymsCommunications of the ACM, 1981
- A Permutation NetworkJournal of the ACM, 1968