[ghayes]

Privacy Pass docs [0] cover this, but it is mostly referenced deeper in the paper. I believe the idea is that the tokens returned by the server are "unlinkable" to the (modified) tokens passed back by the client. So the server knows it passed back tokens A, B and C to some users, and later receives tokens X, Y and Z. It knows that X, Y and Z are valid, but not their correspondance to the tokens it issued. It uses elliptic curve cryptography for this.

[0] https://privacypass.github.io/

[codethief]

After reading your comment I still didn't quite understand how the server couldn't just simply log the tokens A, B, C issued to user X. So I had a look at the website you linked: IIUC the key is that the tokens are actually generated by the user and the server never sees them (unblinded) before their first usage:

> When an internet challenge is solved correctly by a user, Privacy Pass will generate a number of random nonces that will be used as tokens. These tokens will be cryptographically blinded and then sent to the challenge provider. If the solution is valid, the provider will sign the blinded tokens and return them to the client. Privacy Pass will unblind the tokens and store them for future use.

> Privacy Pass will detect when an internet challenge is required in the future for the same provider. In these cases, an unblinded, signed token will be embedded into a privacy pass that will be sent to the challenge provider. The provider will verify the signature on the unblinded token, if this check passes the challenge will not be invoked.

[catalypso]

> the tokens are actually generated by the user and the server never sees them (unblinded) before their first usage

Here is how I see it:

  1. The user generates a token/nonce => T

  2. The user blinds the token with secret blinding factor b => Blinded token TB = T*b

  3. The user sends the blinded token for signing. The server signs it and returns it to the user => Signed blinded token TBS = Sign(TB)

  4. The user unblinds the token (this does not break the signature) => Signed Unblinded token TS = TBS/b

  5. The user sends TS for its search query.

The server signed TB, then received TS. Even if it logged that TB = user, it cannot link TS to TB, because it does not know the blinding factor b. Thus, it cannot link the search query with TS to the user.

[Eji1700]

Ah thank you. That's the part I was missing. I know this example is wrong in 100 different ways, but something like "yeah we know a key with prime factor X is valid, and this has one", but there's thousands of those out there, so it can't tie out to whom.