Re: [CFRG] RSA blind signatures

As a rule, there are relatively few keys in an RSA blind signature deployment, so you could batch verify all messages with the same public key.  I suppose someone who knows the secret p and q might construct FDH with interesting summations, ala https://eprint.iacr.org/2020/945  I’d expect some common RSA assumption forbids this for anyone who does not know the secret key though, so RSA batch verification should turn out secure.

I think RSA batch verification does not improve performance for one spend operation *if* your public keys represent denominations in powers of two, but batch verification does help RSA if you’ve less dense denominations.  In this setting, an RSA blind signature would likely be checked twice, first at a merchant, and second at the exchange/bank/mint.  I suppose exchanges could quickly return “no double spend” to merchants, and then aggregate RSA verification across thousands of spends.  

You'll never benefit from common message aggregation for BLS blind signatures, so every denomination requires another 1500 microsecond Miller loop, which  sounds slower than RSA, no?

Jeff

> On 24 Feb 2021, at 09:17, Michele Orrù <lists@tumbolandia.net> wrote:
> 
> For those cases needing Privacy Pass but with public verifiability, I would kindly ask CFRG to also take a second to evaluate blind BLS signatures.
> 
> It is true that verification would be much slower than RSA;  however, they have efficient batching algorithms (for which the amortized cost is ~2 scalar multiplications) and the issuance protocol is literally the same as a Privacy Pass.
> Additionally, they have the same number of rounds and same number of messages.  
> 
> This would avoid perhaps creating an entire new standard and having just a new section on the privacy pass draft?
> Hoping to help,
> --
> Michele.
> _______________________________________________
> CFRG mailing list
> CFRG@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg