Anonymity networks like Tor and JonDo allow users to access online services while concealing the parties to any particular communication, by relaying this information through several intermediaries. While these networks are an important tool for circumventing online censorship and protecting freedom of speech, they are also a \mixed blessing” for the providers of online services. In particular, while anonymous access can expand the range of users that are able or willing to contribute to an online service, it can also allow misbehaving users to abuse the online service in a way that makes it di_cult to hold them account- able. As a result, several service providers including Wikipedia and Slashdot have chosen to block contributions from known anonymity providers, despite the potential loss of interesting contributions.

An Overview of Nymble

Suppose a user Alice wishes to connect anonymously to a Service Provider (SP), such as a website, while the SP will allow connections only if it can ban a misbehaving user by IP address. To facilitate this, the Nymble system introduces two TTPs, the Pseudonym Manager (PM) and the Nymble Manager (NM). Before connecting to the SP, Alice connects directly to the PM, thus proving she has control over the specified IP address. The PM then issues Alice a pseudonym called a Nym, which is deterministically generated from her IP in such a way that the NM is able to verify that the pseudonym was in fact issued to Alice by the PM, but learns no information about Alice’s IP.

Alice then connects to the NM over an anonymous channel and presents her Nym along with the name of the SP to which she wishes to connect.

Using the pair (Nym; SP), the NM computes and issues to Alice a set of nymbles | one for each time period left in the current linkability window. Within a linkability window, each successive nymble is generated from the previous one using a one way function (a hash function) and two secrets; one secret is known only to the NM, while the other is shared by the NM and the SP. In order to connect to the SP, Alice presents the nymble which corresponds to the current time period. The shared secret allows the SP to verify the validity of Alice’s nymble but not learn her IP address, nor compute or identify any of her other nymbles. Therefore, Alice’s connections within a time period are linkable, while her accesses across different time periods are not. The SP records the nymble used during a session; if it is later found that Alice misbehaved, the SP can complain to the NM by presenting it with a copy of the recorded nymble. The NM then issues the SP a linking token, which is essentially a trapdoor that allows the SP to compute all of Alice’s subsequent nymbles starting from the time period in which the complaint was made (up until the end of the linkability window). The one-way nature of hash functions guarantees that the trapdoor provides no way for the SP to compute previous nymbles; thus, backwards anonymity is preserved, while further connections from a misbehaving user can be detected and blocked.

Problems with the Nymble system

Although this idea might seem to be completely practical at first glance there are many problems in the construction of the current Nymble design. The major problem is that the security of this system greatly depends on the assumption that nvolved participants are honest and they are not going to collude to identify a user and link his connections. Another problem is that this system is neither scalable nor robust since there is only one Nymble Manager (NM) that has to be involved in nymble ticket generation and complaining mechanisms. On the other hand, this Nymble Manager is actually a single point of failure in this design. Finally this system should be tailored according to the preference of servers. In other words, servers might have different blocking policies; therefore, it is great improvement if Nymble system supports both server specific linkability length window and dynamic length linkability window.

Our Contributions

We start with a key insight: the attack that Nymbler and Jack prevent is collusion between the Pseudonym Manager and the SP or NM. Fortunately, the protocols involving the PM are the least frequently invoked, so their cost can be increased with comparatively little effect on the overall cost of authentication. We replace the Nymble PM’s linkable pseudorandom function with an information-theoretically unlinkable blind signature, while leaving the rest of Nymble unchanged. The resulting scheme, which we call ENymble, provides the same anonymity guarantees as Jack and Nymbler while preserving the lower cost of authentication and linking from Nymble. We report on experiments with a prototype implementation of ENymble, showing that the total cost of authentication increases by as little as 11% over Nymble, and compare this with the higher costs of Nymbler and Jack.