In ENymble, we modify the User Registration protocol and the Nymble Acquisition protocol. In each linkability window, a user Alice first connects directly to the PM and demonstrates control over her IP address or other limited resource. She also chooses a random “blind nym” (bnym) and blinds it for signing. The PM records her uid (IP address) and if a signature has not already been issued for that uid in that linkability window, the PM signs and returns her bnym. Alice then unblinds her bnym. In the nymble acquisition phase, she opens an anonymous connection to the NM and presents her signed bnym.

If the signature is valid, the NM computes seed s0 = FKN(bnym) and proceeds as before. We now describe this procedure in more detail.

A. System Setup

In addition to the setup in Nymble, at the beginning of each linkability window i the PM chooses an RSA modulus N for signing bnyms and transmits (i,N) to the NM via an authenticated channel. For each linkability window, the PM clears the set of used IP addresses. The system includes a cryptographic hash function H: M-> *N Z , modeled as a random oracle.

B. User Registration

Alice obtains a blind nym as follows: 1. Alice downloads the PM’s public key for the current linkability window, N, and prepares a bnym for signing by choosing a random message x R □ Mand a blinding factor r R □ * N Z and then computing p = H(x)r3 mod N. 2. Alice connects directly to the PM and transmits P for signing. The PM verifies that her IP address has not previously been used this window, and then responds with £=□ 1/ 3 mod N= H(x)1/ 3 mod N. 3. Alice unblinds the signature by computing p= ^/r = H(x)1/ 3 mod N.

C. Credential Acquisition

Alice obtains nymbles for window d as follows:
1. Alice connects anonymously to the NM and presents her bnym (x, о = H(x)1/3 mod N).
2. The NM verifies that o= H (x)1/ 3 mod N. The NM computes the sequence of w +1 seeds s0 = FKN(x, о , d), si = f(si-1); tokens ti = g(si); and ciphertexts ci = EKN(t0;si).
3. The NM gives the user nymbles Vi = (I, ti, ci,MACkns(I, ti, ci)).