An optimally robust hybrid mix network

ABSTRACT

We present a mix network that achieves efficient integration of public-key and symmetric-key operations. This hybrid mix network is capable of natural processing of arbitrarily long input elements, and is fast in both practical and asymptotic senses. While the overhead in the size of input elements is linear in the number of mix servers, it is quite small in practice. In contrast to previous hybrid constructions, ours has optimal robustness, that is, robustness against any minority coalition of malicious servers.

REFERENCES

• 1: M. Abe. Universally verifiable mix-net with verification work independent of the number of mix-servers. In K. Nyberg, editor, EUROCRYPT '98, pages 437- 447. Springer-Verlag, 1998. LNCS No. 1403.
• 2: 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
• 3: 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]
• 4: David Chaum , Torben P. Pedersen, Wallet Databases with Observers, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.89-105, August 16-20, 1992
• 5: Ronald Cramer , Ivan Damgård , Berry Schoenmakers, Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols, Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, p.174-187, August 21-25, 1994
• 6: A. de Santis, G. di Crescenzo, G. Pemiano, and M. Ytmg. On monotone formula closure of SZK. In FOCS '9, pages 454-465. IEEE Press, 1994.
• 7: Y. Desmedt and K. Kurosawa. How to break a practical mix and design a new one. In B. Preneel, editor, EU- ROURYPT '00, pages 557-572. Springer-Verlag, 2000. LNCS no. 1807.
• 8: Amos Fiat , Adi Shamir, How to prove yourself: practical solutions to identification and signature problems, Proceedings on Advances in cryptology---CRYPTO '86, p.186-194, January 1987, Santa Barbara, California, United States
• 9: Eran Gabber , Phillip B. Gibbons , Yossi Matias , Alain J. Mayer, How to Make Personalized Web Browising Simple, Secure, and Anonymous, Proceedings of the First International Conference on Financial Cryptography, p.17-32, February 24-28, 1997
• 10: R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin. Robust threshold DSS signatures. In U. Maurer, editor, EUROCRYPT '96, pages 354-371. Springer- Verlag, 1996. LNCS no. 1070.
• 11: R. Gennaro, S. Jarecki, H. Krawczyk, and T. R- bin. The (in)security of distributed key generation in dlog-based cryptosystems. In J. Stern, editor, EU- ROCRYPT "99, pages 295-310. Springer-Verlag, 1999. LNCS no. 1592.
• 12: S. Goldwasser and S. Micali. Probabilistic encryption. J. Comp. Sys. Sci, 28(1):270-299, 1984.
• 13: M. Rirt and K. Sako. Efficient receipt-free voting based on homomorphic encryption. In B. Preneel, editor, EU- ROCRYPT '00, pages 539-556. Springer-Verlag, 2000. LNCS no. 1807.
• 14: M. Jakobsson. Personal homepage. http://www.markus-jakobsson.com.
• 15: M. Jakobsson. A practical mix. In K. Nyberg, editor, EUROCRYPT '98, pages 448-461. Springer-Verlag, 1998. LNCS No. 1403.
• 16: 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]
• 17: Jakobsson Markus , Juels Ari, Millimix: Mixing in Small Batches, Certer for Discrete Mathematics & Theoretical Computer Science, 1999
• 18: Markus Jakobsson , Ari Juels, Mix and Match: Secure Function Evaluation via Ciphertexts, Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.162-177, December 03-07, 2000
• 19: Markus Jakobsson , David M'Raïhi, Mix-Based Electronic Payments, Proceedings of the Selected Areas in Cryptography, p.157-173, August 17-18, 1998
• 20: A. Juels. Personal homepage. http://www.ari-j uels.com.
• 21: Ari Juels, Targeted Advertising ... And Privacy Too, Proceedings of the 2001 Conference on Topics in Cryptology: The Cryptographer's Track at RSA, p.408-424, April 08-12, 2001
• 22: Michael George Luby , Luby Michael, Pseudorandomness and Cryptographic Applications, Princeton University Press, Princeton, NJ, 1994
• 23: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 24: Masashi Mitomo , Kaoru Kurosawa, Attack for Flash MIX, Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.192-204, December 03-07, 2000
• 25: 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
• 26: 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
• 27: Choonsik Park , Kazutomo Itoh , Kaoru Kurosawa, Efficient anonymous channel and all/nothing election scheme, Workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.248-259, January 1994, Lofthus, Norway
• 28: Birgit Pfitzmann , Andreas Pfizmann, How to break the direct RSA-implementation of mixes, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.373-381, November 1990, Houthalen, Belgium
• 29: A. Pfitzmann, B. Pfitzmann, and M. Waidner. ISDN-MIXes: Untraceable communication with very small bandwidth overhead. In Info. Security, Proc. IFIP/Sec'91, pages 245-258, 1991.
• 30: K. Sako and J. Kilian. Receipt-free mix-type voting scheme - a practical solution to the implementation of a voting booth. In L.C. Guillou and J.-J. Quisquater, editors, EUROCRYPT '95. Springer-Verlag, 1995. LNCS No. 921.
• 31: Paul F. Syverson , David M. Goldschlag , Michael G. Reed, Anonymous Connections and Onion Routing, Proceedings of the 1997 IEEE Symposium on Security and Privacy, p.44, May 04-07, 1997

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

General Terms:
Design, Experimentation, Performance