Cryptogenography: Anonymity without trust

Abstract

The usual methods of getting anonymity, such as using a VPN or the Tor network, requires some amount of trust: You have to either trust a particular server or trust that not too many servers in a network have been corrupted. In this thesis, we will explore how much we can do without this assumption. Throughout the thesis we will assume that there is an adversary who can see all messages sent, that no two people have access to shared randomness and for much of the thesis we further assume that the adversary has unbounded computational power. In this case, it is impossible for one or more leakers to send any information without revealing some information about who they are. We defi ne a measure of suspicion, which captures the anonymity loss of revealing information in this model: to reveal one bit of information, you will, in expectation, have to become one bit more suspicious. This measure is used to compute the exact amount of information a group of leakers can reveal if they want to keep reasonable doubt about who the leakers are. We also get exact results for the case where some people, censors, are trying to obstruct the leakage by sending misleading messages. The main result in these models is that (even without censors) the leakers can only reveal a very small amount of information. However, the protocols shown to exists might still be a useful alternative to warrant canaries. We also consider the case where the adversary has bounded computational power. In this model, we show that it is still impossible for one leaker to reveal information without losing some anonymity. However, if we give the leaker access to a small anonymous channel, she can use this, combined with steganography, to reveal a large amount of information anonymously.