Reusable anonymous return channels

ABSTRACT

Mix networks are used to deliver messages anonymously to recipients, but do not straightforwardly allow the recipient of an anonymous message to reply to its sender. Yet the ability to reply one or more times, and to further reply to replies, is essential to a complete anonymous conversation. We propose a protocol that allows a sender of anonymous messages to establish a reusable anonymous return channel. This channel enables any recipient of one of these anonymous messages to send back one or more anonymous replies. Recipients who reply to different messages can not test whether two return channels are the same, and there-fore can not learn whether they are replying to the same person. Yet the fact that multiple recipients may send multiple replies through the same return channel helps defend against the counting attacks that defeated earlier proposals for return channels. In these attacks, an adversary traces the origin of a message by sending a specific number of replies and observing who collects the same number of messages. Our scheme resists these attacks because the replies sent by an attacker are mixed with other replies submitted by other recipients through the same return channel. Moreover, our protocol straightforwardly allows for replies to replies, etc. Our protocol is based upon a re-encryption mix network, and requires four times the amount of computation and communication of a basic mixnet.

REFERENCES

• 1: 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]
• 2: L. Cottrell. Mixmaster & remailer attacks. http://www.obscura.com/~loki/remailer/remailer-essay.html, 1995.
• 3: 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
• 4: 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
• 5: R. Gennaro, S. Jarecki, H. Krawczyk and T. Rabin. Secure Distributed Key Generation for Discrete-Log Based Cryptosystems. In Proc. of Eurocrypt '99, pp. 295--310. Springer-Verlag, 1999. LNCS 1592.
• 6: 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]
• 7: 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
• 8: M. Jakobsson. A practical mix. In Proc. of Eurocrypt '98, pp. 448--461. Springer-Verlag, 1998. LNCS 1403.
• 9: Markus Jakobsson, On Quorum Controlled Asymmetric Proxy Re-encryption, Proceedings of the Second International Workshop on Practice and Theory in Public Key Cryptography, p.112-121, March 01-03, 1999
• 10: 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
• 11: 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
• 12: 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]
• 13: 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
• 14: T. Pedersen. A Threshold cryptosystem without a trusted party. In Proc. of Eurocrypt'91, pp. 522--526, 1991.
• 15: S. Parekh. Prospects for remailers. First Monday, 1(2), August 1996. On the web at http://www.firstmonday.dk/issues/issue2/remailers/
• 16: Brent R. Waters , Edward W. Felten , Amit Sahai, Receiver anonymity via incomparable public keys, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948127]

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

General Terms:
Security

Keywords:
anonymity, mix networks, privacy, return address