A k-anonymous communication protocol for overlay networks

ABSTRACT

Anonymity is increasingly important for network applications concerning about censorship and privacy. The existing anonymous communication protocols generally stem from mixnet and DC-net. They either cannot provide provable anonymity or suffer from transmission collision. In this paper, we introduce a novel approach which takes advantage of hierarchical ring structure and mix technique. This proposed protocol is collision free and provides provable k-anonymity for both the sender and the recipient, even if a polynomial time adversary can eavesdrop all network traffic and control a fraction of participants. Furthermore, it can hide the sender and the recipient from each other and thus can be used for anonymous file sharing. The analysis shows the proposed protocol is secure against various attacks. Measurements further demonstrate it is practical.

REFERENCES

• 1: Openssl. http://www.openssl.org.
• 2: Planetlab. http://www.planet-lab.org.
• 3: The homepage of Gnutella. http://gnutella.wego.com.
• 4: The homepage of KaZaa. http://www.kazza.com.
• 5: Luis von Ahn , Andrew Bortz , Nicholas J. Hopper, k-anonymous message transmission, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948128]
• 6: Adam Back , Ulf Möller , Anton Stiglic, Traffic Analysis Attacks and Trade-Offs in Anonymity Providing Systems, Proceedings of the 4th International Workshop on Information Hiding, p.245-257, April 25-27, 2001
• 7: A. Beimel and S. Dolev. Buses for Anonymous Message Delivery. J. Cryptology, 16:25--39, 2003.
• 8: Oliver Berthold , Hannes Federrath , Stefan Köpsell, Web MIXes: a system for anonymous and unobservable Internet access, International workshop on Designing privacy enhancing technologies: design issues in anonymity and unobservability, p.115-129, January 2001, Berkeley, California, United States
• 9: P. Boucher, A. Shostack, and I. Goldberg. Freedom systems 2.0 architecture. White paper, Zero Knowledge Systems, Inc., December 2000.
• 10: Miguel Castro , Barbara Liskov, Practical byzantine fault tolerance and proactive recovery, ACM Transactions on Computer Systems (TOCS), v.20 n.4, p.398-461, November 2002 [doi>10.1145/571637.571640]
• 11: 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]
• 12: D. Chaum, The dining cryptographers problem: unconditional sender and recipient untraceability, Journal of Cryptology, v.1 n.1, p.65-75, 1988
• 13: D. Coppersmith and M. Jakobsson. Almost Optimal Hash Sequence Traversal. In Proceedings of International Conference on Financial Cryptography, Southampton, Bermuda, 2002.
• 14: 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
• 15: Michael J. Freedman , Robert Morris, Tarzan: a peer-to-peer anonymizing network layer, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586137]
• 16: S. Goel, M. Robson, M. Polte, and E. Sirer. Herbivore: A Scalable and Efficient Protocol for Anonymous Communication. Technical Report 2003-1890, Cornell University, Ithaca, NY, February 2003.
• 17: Philippe Golle , Ari Juels, Parallel mixing, Proceedings of the 11th ACM conference on Computer and communications security, October 25-29, 2004, Washington DC, USA [doi>10.1145/1030083.1030113]
• 18: Ceki Gulcu , Gene Tsudik, Mixing Email with Babel, Proceedings of the 1996 Symposium on Network and Distributed System Security (SNDSS '96), p.2, February 22-23, 1996
• 19: M. Jakobsson. Fractal Hash Sequence Representation and Traversal. In Proceedings of the IEEE International Symposium on Information Theory, Lausanne, Switzerland, 2002.
• 20: S. Kent , R. Atkinson, IP Authentication Header, RFC Editor, 1998
• 21: S. Kent , R. Atkinson, IP Encapsulating Security Payload (ESP), RFC Editor, 1998
• 22: S. Kent , R. Atkinson, Security Architecture for the Internet Protocol, RFC Editor, 1998
• 23: Dogan Kesdogan , Jan Egner , Roland Büschkes, Stop-and-Go-MIXes Providing Probabilistic Anonymity in an Open System, Proceedings of the Second International Workshop on Information Hiding, p.83-98, April 14-17, 1998
• 24: Leslie Lamport, Password authentication with insecure communication, Communications of the ACM, v.24 n.11, p.770-772, Nov. 1981 [doi>10.1145/358790.358797]
• 25: Virginia Lo , Dayi Zhou , Yuhong Liu , Chris GauthierDickey , Jun Li, Scalable Supernode Selection in Peer-to-Peer Overlay Networks, Proceedings of the Second International Workshop on Hot Topics in Peer-to-Peer Systems, p.18-27, July 21-21, 2005 [doi>10.1109/HOT-P2P.2005.17]
• 26: B. Möller. Provably Secure Public-Key Encryption for Length-Preserving Chaumian Mixes. Proceedings of CT-RSA 2003, LNCS 2612:244--262, April 2003.
• 27: U. Möller, L. Cottrell, P. Palfrader, and L. Sassaman. Mixmaster Protocol --- Version 2, July 2003.
• 28: Andreas Pfitzmann , Marit Köhntopp, Anonymity, unobservability, and pseudeonymity — a proposal for terminology, International workshop on Designing privacy enhancing technologies: design issues in anonymity and unobservability, p.1-9, January 2001, Berkeley, California, United States
• 29: Andreas Pfitzmann , Birgit Pfitzmann , Michael Waidner, ISDN-MIXes: Untraceable Communication with Small Bandwidth Overhead, Kommunikation in Verteilten Systemen, Grundlagen, Anwendungen, Betrieb, GI/ITG-Fachtagung, p.451-463, February 20-22, 1991
• 30: A Pfitzmann , M Waidner, Networks without user observability, Computers and Security, v.6 n.2, p.158-166, April 1987 [doi>10.1016/0167-4048(87)90087-3]
• 31: Jean-François Raymond, Traffic analysis: protocols, attacks, design issues, and open problems, International workshop on Designing privacy enhancing technologies: design issues in anonymity and unobservability, p.10-29, January 2001, Berkeley, California, United States
• 32: M. Reed, P. Syverson, and D. Goldschlag. Anonymous Connections and Onion Routing. IEEE J. on Selected Areas in Coomunications, Special Issue on Copyright and Privacy Protection, 16(4):482--494, 1998.
• 33: Michael K. Reiter , Aviel D. Rubin, Crowds: anonymity for Web transactions, ACM Transactions on Information and System Security (TISSEC), v.1 n.1, p.66-92, Nov. 1998 [doi>10.1145/290163.290168]
• 34: Rodrigo Rodrigues , Barbara Liskov , Liuba Shrira, The design of a robust peer-to-peer system, Proceedings of the 10th workshop on ACM SIGOPS European workshop: beyond the PC, July 01-01, 2002, Saint-Emilion, France [doi>10.1145/1133373.1133396]
• 35: Clay Shields , Brian Neil Levine, A protocol for anonymous communication over the Internet, Proceedings of the 7th ACM conference on Computer and communications security, p.33-42, November 01-04, 2000, Athens, Greece [doi>10.1145/352600.352607]
• 36: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 37: Michael Waidner, Unconditional sender and recipient untraceability in spite of active attacks, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.302-319, November 1990, Houthalen, Belgium
• 38: M. Wright, M. Adler, B. Levine, and C. Shields. An Analysis of the Degradation of Anonymous Protocols. In Proceedings of the Network and Distributed Security Symposium, San Diego, CA, 2002.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

General Terms:
Security

Keywords:
anonymity, overlay networks, security