Parallel mixing

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.

REFERENCES

• 1: Masayuki Abe, Mix-Networks on Permutation Networks, Proceedings of the International Conference on the Theory and Applications of Cryptology and Information Security: Advances in Cryptology, p.258-273, November 14-18, 1999
• 2: Masayuki Abe , Fumitaka Hoshino, Remarks on Mix-Network Based on Permutation Networks, Proceedings of the 4th International Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography, p.317-324, February 13-15, 2001
• 3: Christian Cachin , Klaus Kursawe , Victor Shoup, Random oracles in constantipole: practical asynchronous Byzantine agreement using cryptography (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.123-132, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.343531]
• 4: David L. Chaum, Untraceable electronic mail, return addresses, and digital pseudonyms, Communications of the ACM, v.24 n.2, p.84-90, Feb. 1981 [doi>10.1145/358549.358563]
• 5: George Danezis , Roger Dingledine , Nick Mathewson, Mixminion: Design of a Type III Anonymous Remailer Protocol, Proceedings of the 2003 IEEE Symposium on Security and Privacy, p.2, May 11-14, 2003
• 6: Y. Desmedt and K. Kurosawa. How to break a practical mix and design a new one. In EUROCRYPT'00, pages 557--572.
• 7: R. Dingledine, V. Shmatikov, and P. Syverson. Synchronous batching: From cascades to free routes. In Privacy Enhancing Technologies '04. To appear.
• 8: J. Furukawa, H. Miyauchi, K. Mori, S. Obana, and K. Sako. An implementation of a universally verifiable electronic voting scheme based on shuffling. In Financial Cryptography '02, pages 16--30.
• 9: Jun Furukawa , Kazue Sako, An Efficient Scheme for Proving a Shuffle, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.368-387, August 19-23, 2001
• 10: Dan Boneh , Philippe Golle, Almost entirely correct mixing with applications to voting, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586121]
• 11: Markus Jakobsson, Flash mixing, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.83-89, May 04-06, 1999, Atlanta, Georgia, United States [doi>10.1145/301308.301333]
• 12: M. Jakobsson. A practical mix. In EUROCRYPT '98, pages 448--461.
• 13: Markus Jakobsson , Ari Juels, An optimally robust hybrid mix network, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.284-292, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384046]
• 14: Jakobsson Markus , Juels Ari, Millimix: Mixing in Small Batches, Certer for Discrete Mathematics & Theoretical Computer Science, 1999
• 15: Markus Jakobsson , Ari Juels , Ronald L. Rivest, Making Mix Nets Robust for Electronic Voting by Randomized Partial Checking, Proceedings of the 11th USENIX Security Symposium, p.339-353, August 05-09, 2002
• 16: A. Kiayias and M. Yung. The vector-ballot e-voting approach. In Financial Cryptography '04, pages 72--89.
• 17: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 18: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 19: C. Andrew Neff, A verifiable secret shuffle and its application to e-voting, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.502000]
• 20: Wakaha Ogata , Kaoru Kurosawa , Kazue Sako , Kazunori Takatani, Fault tolerant anonymous channel, Proceedings of the First International Conference on Information and Communication Security, p.440-444, November 11-14, 1997
• 21: Miyako Ohkubo , Masayuki Abe, A Length-Invariant Hybrid Mix, Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.178-191, December 03-07, 2000
• 22: Charles Rackoff , Daniel R. Simon, Cryptographic defense against traffic analysis, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.672-681, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167260]
• 23: A. Serjantov and G. Danezis. Towards an information theoretic metric for anonymity. In Privacy Enhancing Technologies '02, pages 41--53.
• 24: Abraham Waksman, A Permutation Network, Journal of the ACM (JACM), v.15 n.1, p.159-163, Jan. 1968 [doi>10.1145/321439.321449]
• 25: M. Wright, M. Adler, B. N. Levine, and C. Shields. An analysis of the degradation of anonymous protocols. In NDSS '02, pages 39--50.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

General Terms:
Security

Keywords:
anonymity, mixnet, parallel execution, permutation, privacy