RSA Laboratories

Parallel Mixing

P. Golle and A. Juels

Citation: P. Golle and A. Juels. Parallel Mixing. In B. Pfitzmann, ed., ACM CCS, pp.220-225. 2004.

Efforts to design faster mix networks have focused on reducing the computational cost of mixing per server. We propose a different approach: our 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 mixnet produces output in time at most 2n -- and only around n assuming a majority of honest servers. In contrast, a traditional, sequential mixnet requires time Mn.

Parallel mixnets offer security guarantees comparable to those of sequential mixnets, and in many cases only a slightly weaker guarantee of privacy. Our proposed construction is applicable to many recently proposed mixnets, such as those of Furukawa and Sako, Neff, Jakobsson et al., and Golle and Boneh -- and even to the original design of Chaum (without robustness). In practice, parallel mixnets promise a potentially substantial time saving in applications such as anonymous electronic elections.

Click here for paper

Full Publication List