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 re-encryption 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.