A. Security Analysis

ENymble preserves Nymble’s security properties: Blacklistability, Rate-limiting, Non-frameability and Anonymity, assuming the one-more RSA inversion problem is computationally intractable.

Blacklistability. An honest Pseudonym Manager will only issue one bnym per user. Thus for a coalition of c users to authenticate after all have been blacklisted, they would either have to forge a bnym, violating the assumed intractability of the one-more RSA inversion problem, or they would have to break blacklistability using only c pseudonyms, violating the blacklistability of Nymble.

Non-Frameability. Since distinct users have distinct uids, an honest PM will only refuse to grant a bnym to a user if that user has already received a bnym in that linkability window. Also, an honest NM will grant a different set of nymbles to each bnym. Thus there is no way for one user to frame another without violating the non-frameability of Nymble.

Anonymity. Anonymity in is defined with respect to SPs only (that is, assuming non-colluding PM and NM). It is easy to see that since the nymbles in ENymble are generated according to the same process, the same property holds. We also can de_ne anonymity in a much stronger sense: let the adversary control the PM, NM, and SP, and choose two users U and V . We allow the adversary to ask each user to register and acquire nymbles for any linkability window and any SP of the adversary’s choosing, for any number k of window/SP pairs. The adversary then specifies a single, new linkability window; U and V execute the user registration protocol (with the adversary), and then execute the credential acquisition protocol in a random ordering. The adversary wins if he can guess whether U or V acquired nymbles first. The protocol is anonymous if no adversary can win with probability non-negligibly greater than 1=2. (Notice that since the adversary sees the nymbles issued, this implies that for any time period, the nymbles themselves are also indistinguishable.) Because bnyms are informationtheoretically independent of both uids and bnyms from other windows, every adversary wins this game with probability exactly 1/2.

B. Efficiency

In order to compare the cost of the various TTP-based anonymous blacklisting systems, we measured the costs of the basic cryptographic operations required of the users, NM, PM, and SP in each of the systems. Table 1 shows these costs. User registration in ENymble is obviously the most expensive phase, but it is also the least executed protocol – occurring once per linkability window. Figure 1 shows how this one-time cost compares to the total cost of authentication for various linkability window sizes. At w = 288, as suggested by the total cost of authentication in ENymble is less than a factor of 2 greater than Nymble, compared to 5 orders of magnitude from Nymbler and Jack. Longer linkability windows decrease this difference further – with 5-minute time periods and a one-week linkability window (w = 2016), the difference is only 11%.

Fig1Blocking Misbehaving Users_decrypted-1
Fig. 1. Total cryptographic cost of user registration, nymble acquisition and nymble verification as a function of number of time periods per linkability window. With one week linkability windows and 5-minute time periods, the total co6t of BNymble is only 11% higher than Nymble.

table1Blocking Misbehaving Users_decrypted-2
Table 1. Cost of cryptographic operations in each “nymble-like” anonymous blacklisting system. Nymble acquisition and verification costs are per nymble. All times measured on a 2.67GHz quad-core Xeon W3520 with 12GB RAM.


We have proposed new enhancement for the original design of Nymble System. We present ENymble, a scheme which matches the anonymity guarantees of Nymbler and Jack while (nearly) maintaining the efficiency of the original Nymble. The key insight of ENymble is that we can achieve the anonymity goals of these more recent schemes by replacing only the infrequent “User Registration” protocol from Nymble with asymmetric primitives.