Re: [Taler] [CFRG] RSA blind signatures

[Jeff Burdges]

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