www.freehaven.net

• This paper argues that entropist metrics for anonymity aren’t appropriate to widely shared and deployed anonymity networks.
  • The entropist conception of anonymous communication means indistinguishability within a set (i.e. there’s a set of possible senders, and the adversary can’t adequately distinguish amongst the members of that set).
    • This entropist conception is highly related to the size of anonymity set. But, if we cannot know when the attack occurs, we cannot give at least a lower bound on the anonymity set size during any reasonable candidate attack period.
      • The entropist conception is useful in controlled settings (like elections) where we can control or predict the number of participants, but it’s not appropriate for general communication on large diversely shared networks like the internet.
  • For general internet use, mixnets are overkill against almost every adversary except unrealistic ones like the GPA or incredibly strong ones like The Man (i.e. active adversary who can manipulate traffic in big chunks of the network).
    • GPA is too strong to be realistic because it can observe every link regardless of network size.
    • GPA is also much too weak because it cannot manipulate traffic.
    • Mixnet designs require complicated features (e.g. delays) in order to defend against the GPA, but these features decrease the usability of mixnet. Thus, users and nodes for mixnets are unlikely to be increased adequately to exceed the resources of an adversary because of its limitations of usability (i.e. high latency) and incentive.
  • If probability of node compromise could be assumed to be roughly uniform, the network size (anonymity set size) would be a primary determiner of anonymity protection. But that’s not a realistic view of how large, widely used anonymity networks work.
    • Large anonymity networks are comprised of dynamic and diverse collections of users communicating over nodes that are diversely trusted by diverse parties/platforms. And, these nodes are connected over diversely trusted links based on ASes, ISPs, geography, etc.
• This paper doesn’t provide any definitive answer on what to replace the entropist conception is, but offers some hints and suggestions.
• Entropy isn’t useless for characterizing anonymity, but it’s just not the primary resource of a practical anonymity network’s security. Instead, the primary measure of anonymity should be how hard it is for an adversary to observe or own parts of the network that allow him to conduct attacks.
  • More precisely,
    • To be useful, security metrics should reflect the difficultly an adversary has in overcoming them.
    • To be meaningful, security metrics shouldn’t depend on the values of variables for which we can’t make adequate relevant determinations or predictions.
  • In other words, what the entropist conception gets right is that anonymity protection is determined by the amount of work an adversary needs to do to overcome it. What is gets wrong is the kinds of work the adversary needs to do.