Nymble was the first anonymous blacklisting scheme to appear in the literature. In Nymble, in addition to the SP and the user, there are two Trusted Parties, the Pseudonym Manager (PM) and the Nymble Manager (NM). Nymble uses an authenticated symmetric encryption scheme E, a pseudorandom function F, a message authentication code MAC and two cryptographic hash functions (modeled as random oracles), f and g; there are two secret keys KP and KN known to the PM and NM, respectively, additionally, the MAC key kpn is shared by the PM and NM and MAC Key kns is shared by the NM and SP.
Nymble divides time into “linkability windows,” during which a user’s actions can be linked together and these are then divided further into w “time periods”. Each user is assumed to have some unique identity, uid. Tsanget al. suggest 24-hour windows, 5-minute periods, and IP address uids. At the beginning of each linkability window d, the user connects directly to the PM to request a pseudonym p = FKP (d; uid); т = MACkpn(p). The user then connects anonymously to the NM, sending p, т; if the tag т is correct, the NM forms a sequence of w +1 seeds s0 = FKN(p, d), si = f(si-1); tokens ti = g(si); and ciphertexts ci = EKN(t0; si). The NM gives the user nymbles Vi = (i, ti, ci,MACkns(I, ti, ci)). Then at the i-th time period, the user connects anonymously to the SP, checks that t0 is not blacklisted, and provides Vi; the SP grants access if the MAC tag is correct and ti is not blacklisted. To complain, the SP sends Vi to the NM, who decrypts ci to get t0; si, and computes
ti+1,…………..,tw and sends these and the\canonical nymble” t0 to the SP to add to the blacklist.
A. Collusion of TTPs
There are four possible collusive scenarios between a PM, NM and SP. First, the PM and NM can collude to learn which users connect to which SPs. Second, the NM and SP can collude to link all of a user’s actions within a single linkability window. Third, the PM, NM, and SP can all collude together to deanonymize all of the user’s activities, across linkability windows. The final scenario, involving the PM and SP, is not a privacy threat in Nymble.
In Nymbler, the PM is replaced by a Credential Manager (CM), who issues an anonymous credential on a secret xuid to each user. The user then uses this credential to create his own series of seeds and tokens, with s0 = hxuid using f(x) = x2 mod n, and g(x) = x over a trapdoor discrete logarithm group chosen by the NM. The user obtains blind signatures 1 □ ,…….., W □ on the tokens
t1,………….,tw from the NM, using efficient zeroknowledge proofs to show
that they are correctly formed. The SP, on receiving Vi= (ti, i □ ) can check the signature, and the NM can extract a seed from ti = si by computing the discrete logarithm (a costly but feasible computation using the trapdoor). The use of blind signatures prevents the NM and CM from colluding to link users to SPs; the use of anonymous credentials prevents the NM, CM, and SP from colluding to de-anonymize users.
Jack follows Nymbler in replacing the PM with a CM that issues credentials on a secret xuid. The user creates her own nymbles by encrypting a pseudonym hxuid under the NM’s public key; the SP maintains a cryptographic accumulator of blacklisted pseudonyms. When the user connects to the SP, she presents her encrypted pseudonym along with a proof of correctness the pseudonym corresponds to the xuid in her credential, is encrypted correctly, and is not in the accumulator. To block a user, the NM decrypts the pseudonym and the SP adds it to the accumulator. As in Nymbler, the use of anonymous credentials prevents deanonymization or linking across linkability windows, and since the user creates nymbles noninteractively, the NM and CM cannot collaborate to link users to SPs.