[Privacy-pass] Extending Privacy Pass: Anonymous Tokens with Public Metadata

Tjerand Silde <tjerand.silde@ntnu.no> Mon, 01 March 2021 19:03 UTC

From: Tjerand Silde <tjerand.silde@ntnu.no>
To: "privacy-pass@ietf.org" <privacy-pass@ietf.org>
CC: "Martin.Strand@ffi.no" <Martin.Strand@ffi.no>
Thread-Topic: Extending Privacy Pass: Anonymous Tokens with Public Metadata
Thread-Index: AQHXDs2NV1fwVOf6n0u1iest34qbLw==
Date: Mon, 01 Mar 2021 19:03:23 +0000
Message-ID: <D899AD8B-A877-42E8-86E7-F6E2285CD3C3@ntnu.no>
Accept-Language: nb-NO, en-US
Content-Language: en-US
Content-Type: multipart/alternative; boundary="_000_D899AD8BA87742E886E7F6E2285CD3C3ntnuno_"
MIME-Version: 1.0
Archived-At: <https://mailarchive.ietf.org/arch/msg/privacy-pass/IfCi-hGbVdGNsiGfiaeXkcH5uSU>
Subject: [Privacy-pass] Extending Privacy Pass: Anonymous Tokens with Public Metadata
Precedence: list

Dear all,

We would like to share with you our new result regarding anonymous tokens with public metadata. The paper is available at: https://eprint.iacr.org/2021/203.pdf.

To avoid the issues with key-rotation and key-transparency, one can use public metadata built into the token to determine which tokens are still valid and not, for example by using dates or time periods as metadata. We propose a direct extension of Privacy Pass with public metadata with identical communication complexity and essentially the same computation complexity.

They key insight is that we can publicly update the key-material based on the metadata in a binding way. Let G be the generator of a group with prime order p, let  K = [k] G be the public key with corresponding private key k, let d = H(md) be the hash of metadata md, and let e = inv(d+k) mod p. Then e is our new singing key. Verifiability follows from the Chaum-Pedersen proof of the relation log_G ([d] G + K) = d+k = log_W' (T’) for blinded token T’ and signature W’ = [e] T’.

Our protocol basically fits into the framework that is described in the stadardization documents today, and should be straight forward to extend by just adding metadata to the message-flow and updating the key.

Additionally:


  *   We give updated definitions for tokens with and without public and/or private metadata, and tokens with public metadata and public verifiability.
  *   We give instantiations of all types of protocols, where we use bilinear pairings for the protocols with public verifiability.
  *   Note that the combination of private and public metadata adds some overhead. We would like to improve upon this in the future.
  *   We give a comparison of Privacy Pass, Privacy Pass + Merkle-tree, PrivateStats and anonymous tokens with public metadata.
  *   Contact Tracing is an application that benefits from anonymous tokens, and here, signer and verifier are not the same server. We explain how we implemented Privacy Pass into the Norwegian contact tracing app, and how this lead to the results above.

We welcome all feedback and comments on our paper, either in this thread or by private communication.

Best,
Tjerand & Martin

[Privacy-pass] Extending Privacy Pass: Anonymous … Tjerand Silde