[Privacy-pass] Where we are with BBS and a true rate limiting alternative

[Watson Ladd <[e-mail]>]

Dear privacy pass,

Over the past few months a group of us have been discussing some of
the desiderata for privacy pass, and trying to ensure we have a
flexible, well-considered cryptographic foundation for deployments.

Currently what we have is a number of extensions, but each extension
has to be examined anew and they don't compose: if you want both
public metadata and rate limiting, it takes a new document to make
them work. Instead we can make sure that the single token format
supports a bunch of features.

Foundationally we use a blind issuing variant of BBS, where the user
proves that they have asked for the right fields. Some can be hidden,
and others revealed to the issuer, and then a different set shown to
origins. In addition it's possible to do zero-knowledge proofs
efficiently over equations for the secret values.

For rate limiting one of the fields is a secret key x. On showing the
user computes Y=(x+k)^{-1}H(origin), and proves with a range proof
that k is small and transmits Y to the origin. There are some very
short range proofs available. The origin blocks repeated use of Y.
This has some big benefits: origins can set the rate limit without
cooperation from the issuer. The issuer no longer needs to be split.

The origin could also use a nym by having k=0 and using Y as a user identifier.

We also have a way to do issuer blindness where the origin learns only
that an issuer they trust issued the credential. This resolves a
number of the challenges for the web environment of existing
solutions.

We do need to write this all up, and there's significant modifications
to CFRG drafts (or new ones) needed to make it all work, and there are
some subtleties that lead to needing particular kinds of ZKP that
complicate the efficency story somewhat. However, we're extremely
optimistic that these are not showstopers and the time and space
consumption is moderate enough to make it practical.

Sincerely,
Watson

--
Astra mortemque praestare gradatim