Subject: [Privacy-pass] External verifiability: a concrete proposal

From: Watson Ladd <[email-masked]>
Date: Thu, 9 Jul 2020 17:45:49 -0400

Dear WG members,

Recently I heard of some interesting applications of privacy pass
where external verifiability would be essential. These applications
where ones where a central server was issuing tokens that various
others could use.

My concrete proposal is blind Boneh-Lynn-Shacham signatures.
Concretely we use G1, G2, GT a type III pairing, and have the key of
the issuer be kg_2. As in vanilla privacy pass the tokens are kH(x)
where x is a string and H is a hash function into G_1. However to
verify a token (y, x) one verifies the pairing equations e(y,
g_2)=e(H(x), kg_2). One could use the BLS12-381 parameter set for
this.

Sincerely,
Watson Ladd

---

From: Ben Schwartz <[email-masked]>
Date: Thu, 9 Jul 2020 18:35:59 -0400

How would you verify double-spend protection?

On Thu, Jul 9, 2020 at 5:46 PM Watson Ladd <[email-masked]> wrote:

> --
> Privacy-pass mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/privacy-pass
>

---

From: Watson Ladd <[email-masked]>
Date: Thu, 9 Jul 2020 19:17:58 -0400

> How would you verify double-spend protection?

In the applications I've heard of double spending at different places
is fine, double spending at the same place is not.

--
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: Alex Davidson <[email-masked]>
Date: Fri, 10 Jul 2020 14:28:06 +0100

Hi Watson,

Thanks for bringing this up, I like this idea.
I’m not familiar with the Boneh-Lynn-Shacham signature scheme, but it seems what you’re proposing is only a minor modification on the redemption procedure used in the core protocol design.

When it comes to alternative designs for publicly verifiability, the only things that come to my mind are to use a different blind signature scheme, or to try a more general anonymous credential scheme such as https://eprint.iacr.org/2001/019.pdf <https://eprint.iacr.org/2001/019.pdf> (or something more recent). However, I like the simplicity of what you’re proposing, and the similarity that it enjoys with the existing versions of the protocol.

I’d be interested in hearing more opinions on this topic.

Cheers,
Alex

> On 10 Jul 2020, at 00:17, Watson Ladd <[email-masked]> wrote:
>

---

From: Ian Goldberg <[email-masked]>
Date: Fri, 10 Jul 2020 09:49:07 -0400

> I’d be interested in hearing more opinions on this topic.

In the original design, we wanted to avoid pairings because implementing
them in javascript promised to be annoying.  But nowadays with the
ability to compile different languages to WebAssembly?  Perhaps it's
more reasonable.  The protocol is probably considerably more
straightforward, actually: the ZKPs can go away entirely, and the client
can still batch-verify that a pile of tokens are generated with the same
public key.

---

From: Michele Orrù <[email-masked]>
Date: Sat, 11 Jul 2020 21:32:07 +0200

Hi,

To my understanding, Watson is proposing to use blind BLS signatures (BBLS)
as an option for public verifiability.

In section 5.1 of [Boldyreva
<https://www.cc.gatech.edu/~aboldyre/papers/bold.pdf>] they are described
with additive blinding; If you apply it multiplicatively you have Privacy
Pass (PP) with a DH oracle.

I think that's a great idea to add this as a possible publicly-verifiable
mechanism. The assumptions are more or less the same: PP is exposing a DH
oracle with the NIZK, BBLS will do so with the pairing; PP uses
chosen-target Diffie-Hellman and so will BBLS [JKK
<https://eprint.iacr.org/2014/650.pdf>]. However, I don't particularly see
the advantages w.r.t e.g. blind RSA signatures.

Ben: the double-spending protection can follow the same logic of privacy
pass.

As Ian says, the ZK proof can go away in BBLS, but the performances will
still be worse than vanilla PP.

I had run some numbers on my laptop a while back (please take them with a
pinch of salt):

blind RSA:

- signing server: 2.27ms

- signing client: <0.1ms

- verification: <1e-5 ms

This was done with RSA-2048 (sha256) and C's relic
<https://github.com/relic-toolkit/relic>.

blind BLS:

- signing server: 0.8ms

- signing client: 6ms

- verification: ~4.5 ms

This was done with BLS12-381 (sha256) and Rust's pairing.
<https://github.com/zkcrypto/bls12_381>

Clause Blind Schnorr signatures would be faster than BBLS just as well, for
instance. Just for comparison, on my implementation of PP I have:

PP:

- signing server: ~4ms

- signing client: 3ms

- verification: ~1 ms

This was done with curve25519 (sha512) and curve25519-dalek.

Hope this helps better framing the problem,

--

Michele.

---

From: Alex Davidson <[email-masked]>
Date: Tue, 14 Jul 2020 16:15:23 +0100

Hi Michele,

Thanks, this is really informative. Is the verification time for the blind BLS construction for only a single token? Or is it batched for multiple tokens?
Do you have a link for the Clause Blind Schnorr signature scheme? Is there a reason why we would not consider this scheme instead, if it is more efficient?

Best,
Alex

> On 11 Jul 2020, at 20:32, Michele Orrù <[email-masked]> wrote:
> 
> Hi, 
> 
> To my understanding, Watson is proposing to use blind BLS signatures (BBLS) as an option for public verifiability. 
> In section 5.1 of [Boldyreva <https://www.cc.gatech.edu/~aboldyre/papers/bold.pdf>] they are described with additive blinding; If you apply it multiplicatively you have Privacy Pass (PP) with a DH oracle. 
> 
> I think that's a great idea to add this as a possible publicly-verifiable mechanism. The assumptions are more or less the same: PP is exposing a DH oracle with the NIZK, BBLS will do so with the pairing; PP uses chosen-target Diffie-Hellman and so will BBLS [JKK <https://eprint.iacr.org/2014/650.pdf>]. However, I don't particularly see the advantages w.r.t e.g. blind RSA signatures.
> 
> Ben: the double-spending protection can follow the same logic of privacy pass.
> As Ian says, the ZK proof can go away in BBLS, but the performances will still be worse than vanilla PP.
> I had run some numbers on my laptop a while back (please take them with a pinch of salt): 
> 
> blind RSA: 
> - signing server: 2.27ms
> - signing client: <0.1ms
> - verification: <1e-5 ms
> This was done with RSA-2048 (sha256) and C's relic <https://github.com/relic-toolkit/relic>.
> 
> blind BLS:
> - signing server: 0.8ms
> - signing client: 6ms
> - verification: ~4.5 ms
> This was done with BLS12-381 (sha256) and Rust's pairing. <https://github.com/zkcrypto/bls12_381>
> 
> Clause Blind Schnorr signatures would be faster than BBLS just as well, for instance. Just for comparison, on my implementation of PP I have:
> 
> PP:
> - signing server: ~4ms
> - signing client: 3ms
> - verification: ~1 ms
> This was done with curve25519 (sha512) and curve25519-dalek. <http://curve25519-dalek./>
> 
>

---

From: Michele Orrù <[email-masked]>
Date: Thu, 16 Jul 2020 17:13:14 +0200

Hi Alex,

right, thanks for bringing this up! I had measured *verification for a
single token* (in all schemes).
Batched verification in blind BLS could be done at the amortized cost of
one scalar multiplication for each element, using the same trick for
batched tokens in privacy pass [2008/015
<https://eprint.iacr.org/2008/015.pdf>, Fig. 6].

You can find a link for clause blind Schnorr here: [2019/877
<https://eprint.iacr.org/2019/877.pdf>, section 5]; Antoine also made a
nice presentation <https://www.youtube.com/watch?v=W-uwVdGeUUs> to explain
it.
I'm not sure we should consider their adoption yet; perhaps the protocol
and the assumption are just too new?

On Tue, Jul 14, 2020 at 5:15 PM Alex Davidson <[email-masked]>
wrote:

> Hi Michele,
>
> Thanks, this is really informative. Is the verification time for the blind
> BLS construction for only a single token? Or is it batched for multiple
> tokens?
> Do you have a link for the Clause Blind Schnorr signature scheme? Is there
> a reason why we would not consider this scheme instead, if it is more
> efficient?
>
> Best,
> Alex
>
> To my understanding, Watson is proposing to use blind BLS signatures
> (BBLS) as an option for public verifiability.
> <https://eprint.iacr.org/2014/650.pdf>]. However, I don't particularly
> see the advantages w.r.t e.g. blind RSA signatures.
>
> Clause Blind Schnorr signatures would be faster than BBLS just as well,
> for instance. Just for comparison, on my implementation of PP I have:
>
> PP:
> - signing server: ~4ms
> - signing client: 3ms
> - verification: ~1 ms