Subject: [Privacy-pass] Splitting out public verifiability

From: "Christopher Wood" <[email-masked]>
Date: Thu, 12 Aug 2021 08:48:34 -0700

TL;DR: Split out Privacy Pass into two protocols: one that supports public verifiability, and one that does not. Each one chooses the appropriate cryptographic protocol necessary to make the system work.

At IETF 111, there was discussion around the different shapes and sizes of Privacy Pass. Based on the charter, we’re currently targeting this list of features as requirements (based on the charter):

R1. Unforgeable token issuance that is unlinkable to token redemption.
R2. Support for optional public metadata bound to each token.
R3. Support for token public verifiability.

The current protocol document achieves only requirement R1. It does this by instantiating Privacy Pass with draft-irtf-cfrg-voprf [1], which will soon support optional public metadata [2].

On the public verifiability side, we have draft-irtf-cfrg-rsa-blind-signatures [3] and draft-irtf-cfrg-bls-signature [4]. (The BLS draft does not yet currently support a blind signature variant, but can be tweaked to that effect [5].) Neither of these (currently) support public metadata, though it is possible to augment BLS to support this mode, as outlined in [6]. Of course, there’s the added twist that BLS requires pairings, which is not true of other schemes. To my knowledge, we don’t yet know how to safely build a partially blind signature protocol based on elliptic curves (Schnorr or ECDSA).

Altogether, there’s a lot of choices to be made. What we choose, and how we express that choice in an abstraction, was discussed during the IETF meeting, and it’s not clear (to me) that we reached a sensible conclusion. 

To help make forward progress, perhaps it’s worth focusing on two (simple?) use cases:

1. CAPTCHA solutions (aka the original Privacy Pass [7]). In this variant, the issuer is the same as the redeemer. Metadata may be useful to help further scope the purpose of a token, but this is purely a deployment-specific choice. The tokens are only ever verified by the client and issuer. 
2. Fraud prevention for ad-click attribution [8]. In this model, tokens are issued by one party, the click source, responsible for enforcing rate limiting or other security checks, and redeem them to both the click source and click destination. Tokens must necessarily be publicly verifiable by these two parties who otherwise do not share any sort of secret key material. Metadata may also be useful here to bind (verifiable, i.e., non-tracking) information to a token, but that seems to be an application-specific detail.

Any solution for (2) would work for (1), whereas any mechanism for (1) would not work for (2). Moreover, solutions for (1) are known to be more efficient than solutions for (2). (VOPRFs are more efficient than BLS signatures for issuance and redemption.)

Beyond the performance and efficiency gap, given that the underlying cryptographic protocols dictate what features are possible, and that the protocols for (1) and (2) are disjoint, it seems best to not consider these _extensions_ of some common protocol, but rather two separate protocols entirely. Namely, one that’s publicly verifiable, and one that’s not. 

To that end, here’s what I’d like to propose to the group:

1. Keep the existing protocol document focused on the single issuer and redeemer use case, based on the POPRF construction presented at the CFRG [2].
2. Spin out a separate protocol document for the split issuer and redeemer use case, based on BLS signatures (and possibly including blind RSA). This should be written in such a way to accommodate future partially blind signature schemes should they become available.
3. Update the HTTP mapping for the publicly verifiable variant as needed.

Each protocol document then reduces to a thin wrapper around these underlying cryptographic protocols. It could be the job of that wrapper to address operational considerations, such as parameterization and key configuration, issuer verification mechanisms, and so on. Beyond that, the wrapper doesn’t seem to do much.

What do folks think? Would this be a useful path forward to get us out of the “research rut” and back onto the path towards standardization?

Best,
Chris

[1] https://datatracker.ietf.org/doc/draft-irtf-cfrg-voprf/
[2] https://github.com/cfrg/draft-irtf-cfrg-voprf/pull/258
[3] https://datatracker.ietf.org/doc/draft-irtf-cfrg-rsa-blind-signatures/
[4] https://datatracker.ietf.org/doc/draft-irtf-cfrg-bls-signature/
[5] https://github.com/cfrg/draft-irtf-cfrg-bls-signature/issues/37
[6] https://eprint.iacr.org/2021/203
[7] https://blog.cloudflare.com/supporting-the-latest-version-of-the-privacy-pass-protocol/
[8] https://github.com/privacycg/private-click-measurement/issues/27

---

From: Ben Schwartz <[email-masked]>
Date: Thu, 12 Aug 2021 12:17:24 -0400

On Thu, Aug 12, 2021 at 11:50 AM Christopher Wood <[email-masked]>
wrote:

> 2. Fraud prevention for ad-click attribution [8]. In this model, tokens
> are issued by one party, the click source, responsible for enforcing rate
> limiting or other security checks, and redeem them to both the click source
> and click destination.

I think I understand this.

> Tokens must necessarily be publicly verifiable by these two parties who
> otherwise do not share any sort of secret key material.

I don't understand this claim.  The Architecture document's
Delegated-Verifier and Asynchronous-Verifier modes seem to describe
counterexamples.  Could you clarify?

---

From: "Christopher Wood" <[email-masked]>
Date: Thu, 12 Aug 2021 09:57:27 -0700

On Thu, Aug 12, 2021, at 9:17 AM, Ben Schwartz wrote:
> On Thu, Aug 12, 2021 at 11:50 AM Christopher Wood <[email-masked]> wrote:
> > 2. Fraud prevention for ad-click attribution [8]. In this model, tokens are issued by one party, the click source, responsible for enforcing rate limiting or other security checks, and redeem them to both the click source and click destination.
> 
> > Tokens must necessarily be publicly verifiable by these two parties who otherwise do not share any sort of secret key material.
> 

The claim is simply made in the context of the described use case. Sure, there may be other "modes" that would work here.

Best,
Chris

---

From: Ben Schwartz <[email-masked]>
Date: Thu, 12 Aug 2021 13:26:11 -0400

What I don't understand is "must necessarily be publicly verifiable".  It
seems to me that the click destination can return the token to the click
source for (online) private verification, without relying on any pre-shared
secret key material.  Are you saying that this approach is somehow unsound
or operationally impractical?

I can understand why public verifiability might be "desirable" for this use
case, but I don't see how it is "necessary".

On Thu, Aug 12, 2021 at 12:57 PM Christopher Wood <[email-masked]>
wrote:

> > > 2. Fraud prevention for ad-click attribution [8]. In this model,
> tokens are issued by one party, the click source, responsible for enforcing
> rate limiting or other security checks, and redeem them to both the click
> source and click destination.
> >
> > > Tokens must necessarily be publicly verifiable by these two parties
> who otherwise do not share any sort of secret key material.
> >
> The claim is simply made in the context of the described use case. Sure,
> there may be other "modes" that would work here.
>
> Best,
> Chris
>

---

From: "Christopher Wood" <[email-masked]>
Date: Thu, 12 Aug 2021 10:33:53 -0700

On Thu, Aug 12, 2021, at 10:26 AM, Ben Schwartz wrote:
> What I don't understand is "must necessarily be publicly verifiable".  
> It seems to me that the click destination can return the token to the 
> click source for (online) private verification, without relying on any 
> pre-shared secret key material.  Are you saying that this approach is 
> somehow unsound or operationally impractical?

No, not necessarily. I'm simply relaying what is currently proposed for this use case. 

> I can understand why public verifiability might be "desirable" for this 
> use case, but I don't see how it is "necessary".

That's fair -- we can obviously relax the language, though I'm not sure if that changes the outcome of the original message.

Best,
Chris

> 
> On Thu, Aug 12, 2021 at 12:57 PM Christopher Wood <[email-masked]> wrote:
> Attachments:
> * smime.p7s