Parallel Mixing. Golle, P. & Juels, A. October 2004.
Parallel Mixing [link]Paper  doi  abstract   bibtex   
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.
@conference {golle:ccs2004,
	title = {Parallel Mixing},
	booktitle = {Proceedings of the 11th ACM Conference on Computer and Communications Security (CCS 2004)},
	year = {2004},
	month = {October},
	publisher = {ACM Press},
	organization = {ACM Press},
	address = {Washington DC, USA},
	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 = {anonymity, privacy},
	isbn = {1-58113-961-6},
	doi = {10.1145/1030083.1030113},
	url = {http://portal.acm.org/citation.cfm?id=1030113},
	author = {Philippe Golle and Ari Juels}
}
Downloads: 0