k-Anonymous message transmission

Luis Von Ahn, Andrew Bortz, Nicholas J. Hopper

Research output: Contribution to journalConference articlepeer-review

89 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)122-130
Number of pages9
JournalProceedings of the ACM Conference on Computer and Communications Security
StatePublished - 2003
EventProceedings of the 10th ACM Conference on Computer and Communications Security, CCS 2003 - Washington, DC, United States
Duration: Oct 27 2003Oct 31 2003


  • Anonymity
  • Anonymous Communication
  • Cryptographic Protocols
  • Multiparty Computation
  • Privacy
  • Untraceable Communication


Dive into the research topics of 'k-Anonymous message transmission'. Together they form a unique fingerprint.

Cite this