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 attacker, by simply looking at the communication patterns, cannot determine the intended recipient of a message with probability greater than 1/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 stands in contrast to the fully anonymous case, where all provably secure protocols in such a strong adversarial model are prohibitively inefficient.