Provable Anonymity Against Traffic Analysis ∗

With the advent of peer to peer networks, anonymity is grasped as a desired property of any well designed system for exchanging information between parties. Previous work dealing with anonymity and privacy is mostly application driven and intuitively based, paying more attention to implementation details than to rigorous security analysis. This work focuses on unlinkability, which is one of the possible types of anonymity. We study the unlinkability of an efficient variant of David Chaum’s classic protocol for anonymous data communication and we prove that it is secure against adaptive adversaries even having prior information. Prior to our work, most attempts to make a rigorous analysis were either inefficient or were based on ad-hoc assumptions. Our technique heavily relies on information theory. We use information theory both in formalizing the intuitive definitions and in proving the security properties of our protocol.