k-anonymous message transmission

ABSTRACT

Informally, a communication protocol is sender k - anonymous if it can guarantee that an adversary, trying to determine the sender of a particular message, can only narrow down its search to a set of k suspects. Receiver k-anonymity places a similar guarantee on the receiver: an adversary, at best, can only narrow down the possible receivers to a set of size k. In this paper we introduce the notions of sender and receiver k-anonymity and consider their applications. We show that there exist simple and efficient protocols which are k-anonymous for both the sender and the receiver in a model where a polynomial time adversary can see all traffic in the network and can control up to a constant fraction of the participants. Our protocol is provably secure, practical, and does not require the existence of trusted third parties. This paper also provides a conceptually simple augmentation to Chaum's DC-Nets that adds robustness against adversaries who attempt to disrupt the protocol through perpetual transmission or selective non-participation.

REFERENCES

• 1: Adam Back. Hashcash. Unpublished manuscript, May 1997. Available electronically at http://www.cypherspace.org/hashcash/.
• 2: Mihir Bellare , Phillip Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, Proceedings of the 1st ACM conference on Computer and communications security, p.62-73, November 03-05, 1993, Fairfax, Virginia, United States [doi>10.1145/168588.168596]
• 3: Ted Bridis. Verizon Loses Suit Over Music Downloading. Associated Press, April 24, 2003.
• 4: D. Chaum, The dining cryptographers problem: unconditional sender and recipient untraceability, Journal of Cryptology, v.1 n.1, p.65-75, 1988
• 5: 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]
• 6: David Chaum , Jan-Hendrik Evertse , Jeroen van de Graaf , René Peralta, Demonstrating possession of a discrete logarithm without revealing it, Proceedings on Advances in cryptology---CRYPTO '86, p.200-212, January 1987, Santa Barbara, California, United States
• 7: Danny Dolev , Cynthia Dwork , Orli Waarts , Moti Yung, Perfectly secure message transmission, Journal of the ACM (JACM), v.40 n.1, p.17-47, Jan. 1993 [doi>10.1145/138027.138036]
• 8: Cynthia Dwork , Moni Naor, Pricing via Processing or Combatting Junk Mail, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.139-147, August 16-20, 1992
• 9: The GNUnet website. http://www.ovmj.org/GNUnet/.
• 10: Oded Goldreich , Amit Sahai , Salil Vadhan, Honest-verifier statistical zero-knowledge equals general statistical zero-knowledge, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.399-408, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276852]
• 11: S Goldwasser , S Micali , C Rackoff, The knowledge complexity of interactive proof-systems, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.291-304, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22178]
• 12: David Mazières , M. Frans Kaashoek, The design, implementation and operation of an email pseudonym server, Proceedings of the 5th ACM conference on Computer and communications security, p.27-36, November 02-05, 1998, San Francisco, California, United States [doi>10.1145/288090.288098]
• 13: Torben P. Pedersen, Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.129-140, August 11-15, 1991
• 14: A Pfitzmann , M Waidner, Networks without user observability—design options, Proc. of a workshop on the theory and application of cryptographic techniques on Advances in cryptology---EUROCRYPT '85, p.245-253, January 1986, Linz, Austria
• 15: Michael K. Reiter, A Secure Group Membership Protocol, IEEE Transactions on Software Engineering, v.22 n.1, p.31-42, January 1996 [doi>10.1109/32.481515]
• 16: 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]
• 17: Emin Gün Sirer, Milo Polte, and Mark Robson. CliqueNet: A Self-Organizing, Scalable, Peer-to-Peer Anonymous Communication Substrate. Unpublished manuscript, December 2001. Available electronically at http://www.cs.cornell.edu/People/egs/papers/cliquenet-iptp.pdf.
• 18: Latanya Sweeney, k-anonymity: a model for protecting privacy, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, v.10 n.5, p.557-570, October 2002 [doi>10.1142/S0218488502001648]
• 19: 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
• 20: M. Wright, M. Adler, B. Levine, and C. Shields. An analysis of the degradation of anonymous protocols. Proceedings of ISOC Symposium on Network and Distributed System Security, 2002.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Data communications

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

  E. Data
  E.4 CODING AND INFORMATION THEORY

General Terms:
Design, Performance, Reliability, Security

Keywords:
anonymity, anonymous communication, cryptographic protocols, multiparty computation, privacy, untraceable communication