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

[Christopher Patton <[e-mail]>]

Watson,

It would be great to see a presentation on this at 120. In lieu of a
draft(s), could you slap together a proof-of-concept? No need to plug it
into Privacy Pass, but it would at least be useful to see what each party
does and how the proof system works.

Chris P.

On Tue, Jun 25, 2024 at 3:48 PM Watson Ladd <[e-mail]> wrote:

> 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
>
> --
> Privacy-pass mailing list -- [e-mail]
> To unsubscribe send an email to [e-mail]
>