Receiver anonymity via incomparable public keys

ABSTRACT

We describe a new method for protecting the anonymity of message receivers in an untrusted network. Surprisingly, existing methods fail to provide the required level of anonymity for receivers (although those methods do protect sender anonymity). Our method relies on the use of multicast, along with a novel cryptographic primitive that we call an Incomparable Public Key cryptosystem, which allows a receiver to efficiently create many anonymous "identities" for itself without divulging that these separate "identities" actually refer to the same receiver, and without increasing the receiver's workload as the number of identities increases. We describe the details of our method, along with a prototype implementation.

REFERENCES

• 1: Mihir Bellare , Alexandra Boldyreva , Anand Desai , David Pointcheval, Key-Privacy in Public-Key Encryption, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.566-582, December 09-13, 2001
• 2: Mihir Bellare , Chanathip Namprempre, Authenticated Encryption: Relations among Notions and Analysis of the Generic Composition Paradigm, Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.531-545, December 03-07, 2000
• 3: Jon Callas, Lutz Donnerhacke, Hal Finney, and Rodney Thayer. RFC 2440: OpenPGP message format, November 1998. Status: PROPOSED STANDARD.
• 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: D. Chaum, The dining cryptographers problem: unconditional sender and recipient untraceability, Journal of Cryptology, v.1 n.1, p.65-75, 1988
• 6: Wei Dai. Crypto++ 4.0 benchmarks. http://www.eskimo.com/~weidai/benchmarks.html.
• 7: George Danezis, Roger Dingledine, David Hopwood, and Nick Mathewson. Mixminion: Design of a type III anonymous remailer protocol, 2002. http://mixminion.net.
• 8: Taher El Gamal, A public key cryptosystem and a signature scheme based on discrete logarithms, Proceedings of CRYPTO 84 on Advances in cryptology, p.10-18, August 1985, Santa Barbara, California, United States
• 9: David Goldschlag , Michael Reed , Paul Syverson, Onion routing, Communications of the ACM, v.42 n.2, p.39-41, Feb. 1999 [doi>10.1145/293411.293443]
• 10: Philippe Golle, Markus Jakobsson, Ari Juels, and Paul Syverson. Universal Re-encryption for Mixnets, 2003. http://crypto.stanford.edu/~pgolle/papers/univrenc.html.
• 11: H. Krawczyk, SKEME: a versatile secure key exchange mechanism for Internet, Proceedings of the 1996 Symposium on Network and Distributed System Security (SNDSS '96), p.114, February 22-23, 1996
• 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: M. Naor , M. Yung, Public-key cryptosystems provably secure against chosen ciphertext attacks, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.427-437, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100273]
• 14: Andreas Pfitzmann and Michael Waidner. Networks without user observability. Lecture Notes in Computer Science, 219:245--253, 1986.
• 15: Charles Rackoff , Daniel R. Simon, Non-Interactive Zero-Knowledge Proof of Knowledge and Chosen Ciphertext Attack, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.433-444, August 11-15, 1991
• 16: Josyula R. Rao and Pankaj Rohatgi. Can pseudonymity really guarantee privacy? In Proceedings of the Ninth USENIX Security Symposium, pages 85--96. USENIX, August 2000.
• 17: 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]
• 18: Rob Sherwood , Bobby Bhattacharjee , Aravind Srinivasan, P5: A Protocol for Scalable Anonymous Communication, Proceedings of the 2002 IEEE Symposium on Security and Privacy, p.58, May 12-15, 2002
• 19: 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]
• 20: 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
• 21: The GNU Privacy Guard. http://www.gnupg.org.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

General Terms:
Security

Keywords:
PGP, anonymity, privacy, public key cryptography