Introduction to Privacy Pass

Privacy Pass was introduced by Alex Davidson, Ian Goldberg, Nick Sullivan, George Tankersley, and Filippo Valsorda in 2018 in order to reduce the number of CAPTCHA challenges human users would meet online. The basic idea is to allow the user to submit a number of tokes to a server ahead of time. The server will sign these, equivalent to issuing notes with the text "The holder of this token should be considered a human, not a bot". Every time the user visits a website that would otherwise have asked for a CAPTCHA, the browser can hand over one of the tokes instead, hence not bothering the user with reading garbled letters or clicking on images of road signs.

However, if each of these notes had a serial number (which we should assume; otherwise one could just make several copies and hand out to the bot friend), those serial numbers could be used to track users across the internet, which is obviously a privacy issue. The authors of Privacy Pass have therefore come up with an elegant solution to this. In order to gently introduce notation, we formulate the protocol using points on an elliptic curve.

1. First, the server side generates an elliptic curve E with a distinguished point G, secret key k and a public key K = kG.
2. The browser chooses a random number t, and generates a point T on the curve from t using a hash function. It then creates a masked point P = rT, which it submits to the token issuer.
3. The token issuer signs the token by computing a new point Q = kP. It also provides a Chaum-Pedersen zero-knowledge proof to prove that it was indeed k what was used to sign P, but without revealing k.
4. The original point T is now masked by both r and k. The browser can remove r, so that it is left with the token W = kT.
5. In order to redeem the token, the browser can submit (t, W) to the website the user wants to visit. The website generates T from t, computes kT, and verifies that it equals W. The seed t is stored in order to prevent the token being used twice.

We refer to the original paper for a detailed security proof. What follows is a intuition-based argument for why this protocol achieves its goals:

1. In order to manufacture tokens that could be used more than once, the browser would need to generate values t, t' such that they both generated the point T. Hence, the hash function needs to be collision resistant and second preimage resistant. The SHA2 family of hash functions is believed to satisfy these requirements.
2. Since r is chosen uniformly at random, the point P = rT carries no meaningful information. Likewise, if the discrete log problem is hard on the chosen elliptic curve, then it is infeasible to extract the secret key k from the point kT. The Chaum-Pedersen proof guarantees that Q is well-formed. The browser is therefore none the wiser regarding generating tokens.
3. Since the points P and Q are masked with r, and W is independent of these points, the issuing service and the verification service will not be able to trace when a specific token was used, and so the anonymity of the user is guaranteed.