Formalizing Anonymity: A Review

作者:Joss Wright, Susan Stepney, John A. Clark, Jeremy Jacob



In order to avoid discrimination against, or abuse of, users of communicating systems it may sometimes be necessary to prevent their activities from being made public. In many cases this may be achieved by robust encryption protocols for transactions, however in a number of important cases it is necessary for the content of transactions to be publicly available.

In other situations the very use of a particular system may be incriminating. Certain websites may be censored, or simply viewed unfavourably by parties with access to web browsing logs. The use of peer-to-peer file sharing networks, while legal in itself, can cause suspicion due to the high volume of illegal content. In these situations, the legitimate user may well desire privacy to prevent the assumption of guilt that others may associate with these uses.

Alternatively, a user may simply not wish their participation in an online system to be noted or traceable. Online discussion mailing lists and newsgroups are frequently archived in publicly accessible locations. The senders of spam email are known to harvest these locations for email addresses to populate spam databases. Users taking part in such lists may wish to avoid having their participation logged to avoid an increase of unsolicited email to their accounts.

In all of these cases, a useful and effective method for protection of the user
is to sever the link between a user’s identity and their observable behaviour in the
system. In short: to make the user anonymous.

Several methods to achieve this goal have been proposed and, at least partially, implemented. Yet, despite some formal foundations in the literature, there has been very little rigorous design or verification work in the systems that have emerged. Indeed, there have been almost no proposed formal specifications of anonymity properties that are of utility in modelling anything more than academic or toy systems. As a result of this, nearly every system that has been released has
imperfectly protected the identity of its users.