Comment by 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.