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

[Michele Orrù <[e-mail]>]

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.