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

[Kosei Akama <[e-mail]>]

Dear Mr. Watson,

Hello, I am sending this email to follow up.

Do you have any plans to discuss this?
It might be a better alternative to BBS proof for rate-limiting.

If it is not sufficient, could you tell me your concern?

Best regards,


/**
  * Kosei Akama
  * @email [e-mail]
  * @tel [phone]
  * @twitter _akakou
  **/

On Thu, Jun 27, 2024, 10:55 AM Kosei Akama <[e-mail]> wrote:

> Dear Watson,
>
>
> Hello! I am Kosei Akama,
>
> a master course student at Keio University.
>
>
> This discussion is very interesting and important,
>
> and I would like to share an idea that may help.
>
>
> The following proof might be sufficient for rate-limiting:
>
> SPK{(x): K = H(origin || t)^x}
>
> where:
>
> - x is the prover's secret key,
>
> - origin is the verifier's identifier,
>
> - t is the time window,
>
> - H is the hash function.
>
> - || is concatenation
>
>
> In this scheme, the verifier can check if the prover has not sent proof in
> the same time window. Specifically, if the prover generates K in the same
> window t again, the K will be the same as the previous one; thus, the
> verifier can recognize them. This is because K is computed
> deterministically from t (and x).
>
>
> This proof is simple and efficient because it is constructed from one
> Schnorr proof.
>
>
>
> References:
>
>    -
>    https://www.ndss-symposium.org/ndss-paper/scrappy-secure-rate-assuring-protocol-with-privacy/
>    (base paper)
>    -
>    https://speakerdeck.com/akakou/scrappy-secure-rate-assuring-protocol-with-privacy
>    (slide)
>
>
> Thank you so much for reading this email.
>
> Please do not hesitate to ask me if you have any questions.
>
>
> Best regard.
>
>
>
> /**
>   * Kosei Akama
>   * @email [e-mail]
>   * @twitter _akakou
>   **/
>
>
> 2024年6月27日(木) 8:30 <[e-mail]>:
>
>> Send Privacy-pass mailing list submissions to
>>         [e-mail]
>>
>> To subscribe or unsubscribe via email, send a message with subject or
>> body 'help' to
>>         [e-mail]
>>
>> You can reach the person managing the list at
>>         [e-mail]
>>
>> When replying, please edit your Subject line so it is more specific
>> than "Re: Contents of Privacy-pass digest..."Today's Topics:
>>
>>    1. Re: Where we are with BBS and a true rate limiting alternative
>>       (Watson Ladd)
>>
>>
>>
>> ---------- Forwarded message ----------
>> From: Watson Ladd <[e-mail]>
>> To: Christopher Wood <[e-mail]>
>> Cc: [e-mail]
>> Bcc:
>> Date: Wed, 26 Jun 2024 16:29:30 -0700
>> Subject: [Privacy-pass] Re: Where we are with BBS and a true rate
>> limiting alternative
>>
>>
>>
>> On Wed, Jun 26, 2024 at 3:40 PM Christopher Wood <[e-mail]>
>> wrote:
>>
>>>
>>> On Jun 26, 2024, at 5:11 PM, Watson Ladd <[e-mail]> wrote:
>>>
>>> On Wed, Jun 26, 2024 at 12:27 PM Christopher Wood <[e-mail]>
>>> wrote:
>>>
>>>
>>> Hi Watson,
>>>
>>> Thanks for writing this up! Please see inline below.
>>>
>>> On Jun 25, 2024, at 6: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.
>>>
>>>
>>> Can you clarify what the origin requirements are for this to work? It
>>> seems like the origin would have to (1) verify the showing via a pairing
>>> computation, (2) verify the rate limit proof, (3) and then check for double
>>> spend of the Y value. Did I get that right? If so, what are you envisioning
>>> for range proofs? Bulletproof or something?
>>>
>>>
>>> That's morally correct, assuming the showing reveals a commitment to
>>> k. Bulletproofs would work as is for the range proof.
>>>
>>> To expand a little: a BBS showing is the demonstration of a
>>> rerandomized signed commitment, and then demonstrating the commitment
>>> opens in certain ways via a statement that's of the kind
>>> Camenish-Stadler discuss. Discussions of BBS often don't note this
>>> explicitly. This can be extended to show the equation between Y, k, x
>>> and H(g) holds as well, as it's another equation of the same type.
>>> Separately a Bulletproof can show the commitment to k is well formed
>>> and has the right range, but there's some subtlety about properly
>>> composing sigma protocols here.
>>>
>>> There's a slight complication in that currently the proofs of the
>>> properties we want out of tokens rely on straightline extractability
>>> for composition. For Bulletproofs this is not a problem, but it does
>>> increase cost of the BBS showing as I think Fischlin's transform is
>>> needed rather than Fiat-Shamir. Work in progress but I should get a
>>> prototype hopefully soon so we can all see it work.
>>>
>>>
>>> OK, thanks. How would you compare this work to what’s required for
>>> origins in Privacy Pass today? Do you see this as being easy to deploy?
>>>
>>
>> Properly bottled up it is: it would be similar (but more expensive:
>> somewhere between 0.5-2 milliseconds per request, although I haven't
>> implemented to get a solid number) to what origins need to do for privacy
>> pass today. Namely verify an opaque token and store an identifier they
>> throw out when seen again. One fact worth mentioning is that the origin has
>> an easier time enforcing and changing rate limits as its now a local
>> operation. The duration of the token issuance keys has to be longer, but
>> that was I think always the case.
>>
>>
>>>
>>> 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.
>>>
>>>
>>> This feels incompatible with the current HTTP authentication scheme,
>>> where the origin explicitly asks for a token (or showing) from a specific
>>> issuer. Are you envisioning a separate HTTP authentication scheme for this
>>> to work?
>>>
>>>
>>> This is geared more towards the Web platform enabled parts like
>>> Google's private state tokens.
>>>
>>>
>>> This is definitely a limitation of the other rate limiting proposal, so
>>> I’m glad to see this work being done.
>>>
>>> There the limitation is imposed that
>>> sites can only ask for two issuers. Unfortunately this creates an
>>> artificial winner take all dynamic. If we want an RFC 9577 compatible
>>> system, I think it's an entry creating a new token challenge
>>> structure. This part is very tentative for now.
>>>
>>>
>>> Thanks for clarifying. Out of curiosity, where does this two issuer
>>> limitation come into play?
>>>
>>
>> It's part of the Privacy Sandbox documentation. As I understand it the
>> two issuer limitation comes into play because if a site could probe for
>> every potential issuer it would learn a lot of information about a client.
>> To reduce this it learns just two bits by querying for two issuers.
>>
>>>
>>>
>>> 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.
>>>
>>>
>>> Can you elaborate on what new cryptographic dependencies would be needed
>>> over type 2 or 3 tokens today, from the client and origin perspective?
>>> Moreover, are those dependencies standardized yet, or is that new work the
>>> CFRG would need to do?
>>>
>>>
>>> What is token type 3? I only see 1 and 2 in the registry. CFRG would
>>> need to do some new work, or modify the already existing BBS draft to
>>> fit.
>>>
>>>
>>> Type 3 is the rate limited version. I’m asking to quantify the work
>>> required because it seems like this is quite far from being ready. This is
>>> fine, but I wanted to get a sense for the amount of work required to make
>>> this alternative work.
>>>
>>
>> The new work is more flexible BBS+Bulletproofs. There is ongoing work in
>> zkproofs.org to do some of the flexibile proofs stuff, but who knows
>> when it will be ready. So a bunch of work needed to standardize, but the
>> difference from the existing BBS draft for Issuance is not much, the
>> difference is really a "toss in a statement here" for proving and that's
>> well understood just not standardized AFAIK. Then Bulletproofs I think a
>> lot of work has happened in the blockchain world to write text that
>> describes it enough for interop. But obviously still a big chunk of work to
>> get through the IETF.
>>
>> It is definitely far from ready, but it's definitely in the realm of
>> doable in a reasonable amount of time and effort.
>>
>>
>>> Best,
>>> Chris
>>>
>>
>> Sincerely,
>> Watson
>>
> /**
>   * 赤間 滉星
>   * @email [e-mail]
>   * @tel [phone]
>   * @twitter _akakou
>   **/
>