Private Access Tokens (PATs) standard define a web protocol where a service (the origin) requests users to prove certain properties about themselves prior to concede access to their online services. The protocol defines an anonymous access control flow that define how users obtain and use proofs to access services on the web without having to disclose their full identity or other personal information. PATs allow designing systems where the origin only learn that anonymous clients can access the service because they meet a certain pre-defined access rules and requirements, without leaning anything else. For example, an origin may want to grant service access if the user is from a certain country. The request provenance can be achieved by checking the user's IP address, for example. However, if relying on the IP address to check the request provenance, the origin needs to i) make sure that the client is not behind a VPN or anonymous proxy; and ii) learn about the user's IP address. The PATs protocol allows the user to obtain a proof of provenance from third parties that can be redeemed when accessing the origin's service. The service provider does not need to necessarily run the request provenance logic or inspect the user's IP. In addition, by delegating the request provenance logic to a third party, the origin does not need to implement and maintain the logic IP-based provenance logic that can be brittle to maintain. In sum, the PATs protocol allow service providers to delegate access control checks and proof generation to third parties and a flexible anonymous access control system which contains user data leakage on the web.

The PATs protocol defines i) a protocol where different parties (client, origin, mediator and issuer – more on these parties later) interact to generate and verify proofs based on properties of web user; and ii) the token scheme that is used to encode the proofs so that the token leaks as few information about the user's data and behavior as possible.

PATs in the context of anonymous rate limiting. Servers rely on IP addresses and user's behavioral data/profile to identify clients across the web. The identification is used for rate-limiting and other stateful logic based on static identifiers from the user. This approach has several privacy issues, is brittle, and incentivizes users to use anonymous proxies, which often breaks or makes it hard for the server to implement the per-client stateful logic. Private Access Tokens provide a mechanism that enables stateful and anonymous access control on the web – first, a client obtains access tokens from an issuer, upon proving that their rate limit hasn't been hit for a particular service. Then, the user uses the access tokens to access the service. Through this scheme, the origin can grant access to clients that are behind anonymous proxies without relying on a stable client identifier such as their IP address or having to maintain and update rate limiter logic locally.

PATs in the context of anti-fraud and Sybil attacks on the web. Anti-fraud on the web is a hard problem to solve and it is becoming increasingly difficult for web services to filter traffic that is fraudulent, specially in an anonymous setting where users wish to reduce personal data leakeage. As a result, web services end up i) casting a wide net and require a lot of personal and behavioral data from the users in order to grant service access; and ii) having to implement and constantly update anti-fraud logic. PATs can help delegating the anti-fraud logic to a trusted services that check the legitimacy of users, without learning which service the users want to access. In addition, webs services are able to delegate the anti-fraud logic to specialized services and to verify the access tokens locally without having to learn any extra information about the user and their behavioral patterns. In this setting, users "mint" access tokens from an issuer by presenting proofs of humanity (i.e. WebAuth logins, etc). The issuer then verifies those proofs and issues access tokens to the user. The tokens can be then spent when anonymously accessing services online.

Protocol overview. The bird's eye view of the protocol is as follows:

1. The client (client) requests access to the Origin server (origin);
2. The origin answers with a HTTP401 and provides instructions about how the user can request/generate the access tokens that will provide access to its services. The instructions contain a pointer to a trusted issuer and what's the required proof of access;
3. The user requests for access tokens to the trusted issuer appointed by the origin. The request is done through a mediator which, similar to the oblivious DNS over HTTPS protocol, proxies the requests between the user and the issuer so that i) the issuer does not learn about the user IP address; and ii) the mediator does not learn the content of the proof request (i.e. user data, origin, etc);
4. The issuer checks the request payload sent by the user, which contains the origin identifier. The issuer issues a batch private access tokens to the user iif the user's token request matches the policy defined by the origin they are trying to access.
5. The client repeats point 1. and attaches to the request the access tokens received from the issuer;
6. The origin verifies the tokens and grants access to their services if the tokens are valid and as per expected policy.

Fig 1. Private Access Tokens protocol flow (from [1])

Do we really need the mediator role in PATs? The mediator's role in PATs is to decouple user's stable identifiers and other stateful data from the user with the origin identifier required in the token issuance. This is implemented similarly to the oblivious HTTP design [3], where a party (the mediator) sees a share of the data sent by the user and another party (the issuer) has access to another share of the data. Assuming both parties do not collude, they maintain a disjoint view of the user behavior and data which improves the overall user privacy. In the context of PATs, the mediator learns about the client's identifiers, keeps stateful data of the user across multiple token access requests, and it implements logic to decide whether users should receive the access tokens. On the other hand, the issuer learns about the origin that is an anonymous user is trying to access to and issues the private access tokens at the mediator's request.

The problem with this approach is twofold:

• If the mediator and issuer collude, they'll be able to link user's data and stable identifiers with the services being accessed; and
• Requiring one extra party adds complexity and one extra point of failure e.g. if either the issuer/mediator is down, the clients will not be able to request new access tokens and thus not being able to access the desired service.

One options to remove the need for the mediator role is to remove the need for the client to disclose the ORIGIN_ID/ANON_ORIGIN_ID when requesting for new access tokens and aggregate the roles of issuer and mediator together.

Another idea: In the case of the rate limiting, why not keeping the rate limiting state in a black box accumulator as in [4]? This construction would allow:

• User to keeps the state of the service usage (usage budget) in a cryptographic accumulator;
• The accumulator is issued by the service (permission to access the service);
• Issuer verifies the state of accumulator, updates it and issues privacy pass tokens depending on the rate limiting budget;
• BBA (ie. state) issuance and updates are unlikeable;
• Access tokens are only issued if the state of the accumulator allows (i.e. rate limit hasn't been reached for a specific period);
• Only the origin can issue new BBAs and only the issuer can update BBAs;

The cryptography behind PATs

Privacy Pass with public verifiability

References and further reading

1. Private Access Tokens IETF draft
2. Private Access Tokens presentation deck
3. Oblivious DNS over HTTPS
4. Privacy-Preserving Incentive Systems with Highly Efficient Point-Collection