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

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ù <lists@tumbolandia.net> 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./>
> 
> 
> Hope this helps better framing the problem, 
> --
> Michele.
> 
> -- 
> Privacy-pass mailing list
> Privacy-pass@ietf.org
> https://www.ietf.org/mailman/listinfo/privacy-pass