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 attacker,
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.