Tjerand Silde

March 5, 2021

Anonymous Tokens with Public Metadata

Together with Martin Strand we recently published a pre-print of our new paper "Anonymous Tokens with Public Metadata and Applications to Private Contact Tracing", making it available at

Anonymous tokens can be used to authorise access to a system, but at the same time prevent tracking the actions performed by the authorised person within the system. This ensures the privacy of the users, even when they have to identify themselves to get access in the first place. Anonymous tokens has applications to private browsing, logging, storage, advertising, click measurements, and more. We show how to use anonymous tokens to improve the user's privacy in contact tracing, wrote an implementation in C#, and integrated it with the Norwegian app.

We improved upon the Privacy Pass protocol, which works as following:

1. A user samples a random token seed t and a randomisation factor r and computes a pre-token T'. He sends T' to the server.
2. The server signs T' with his secret key k and produces a signature W'. He also proves that W' is computed correctly with respect to T' and the corresponding public key K, and produces a proof P. Then, W' and P are sent to the user.
3. The user verifies that P is valid, and then computes the token point W from W' and r. The final token is the tuple ( t, W ).
4. When the user wants to redeem the token, he sends ( t, W ) to the server, which uses k to check its validity.

The token is unforgeable, which means that the user is not able to produce his own tokens. It is also unlinkable, which means that the server cannot link any pre-token T' to any token ( t, W ). We note that the round-complexity, the communication complexity and the computational complexity of the protocol is relatively small, and it follows that the protocol can be very efficient in practice.

One challenge in the above setting is that the server needs to change his private-public key-pair to be able to revoke unspent tokens. This might be necessary to stop users from hoarding tokens (e.g., to perform DoS attacks) or holding onto tokens (and redeem after it is supposed to be used). Then the server needs to frequently publish new public keys and make them available to the users in a transparent way (so that every user uses the same public key to prevent tagging of single users). This might be challenging to implement in a good way, and the best solutions today are to either 1) publish many public keys at once, 2) use a Merkle-tree to commit to all keys and then extend the proof to include the correct path, or 3) use a attribute-based verifiable oblivious PRF to generate keys on the fly.

We propose an extension of Privacy Pass that includes public metadata, e.g., for user-groups, time-periods, end-dates etc. This allows the server and the users to publicly update the key-pair based on the public metadata before signing, such that each new token has a tag embedded saying when it is valid. This avoids the issues of rotating key mentioned above, and are much more efficient in practice.

In the paper, we also give the following:

1. New definitions for anonymous tokens with public metadata, also combined with either private metadata or public verifiability (based on pairings).
2. Concrete and efficient instantiations of all protocols mentioned above.
3. Comparison with other protocols within the different categories, showing that our protocols are more efficient in terms of computation and communication.
4. Concrete comparison for anonymous logging in WhatsApp, showing that our protocol gives a saving of up to 90 % in communication compared to today.

Privacy Pass is being standardised by the IETF and Trust Tokens is being standardised by the W3C, and we are currently working to include our extension into the standardisation documents.