[Taler] Batch RSA signature verification

[Jeff Burdges]

Is there a way to speed up Taler by batching RSA signature verification?

A batch verification without any exponentiations is insecure:
https://www.mii.lt/Informatica/pdf/INFO197.pdf

I think the conclusions here are kinda correct, but do not quite buy the proof: 
 http://h.web.umkc.edu/harnl//papers/1998%20J2.pdf

In other words, one could batch verify signatures sigma_i with messages m_i by 
checking that
   sum_i FDH_N(m_i)^{c_i} mod N = (sum_i sigma_i^{c_j})^e mod N
except the c_i are random 64 bit numbers, while e is maybe as small as 16 bits, 
so this make everything slower!

I wonder however if using 8 bit c_i but checking this equation 8 times might be 
secure.  Again that’s slower, but we can parallelize to do doublings only once, 
which might improve performance when checking say 16+ coins.

In this article, Fiat suggests using different (e,d) pairs for each message:
https://link.springer.com/content/pdf/10.1007%2F0-387-34805-0_17.pdf
We cannot do this exactly because it’d break anonymity.

We can however have denomination public keys (e_i,N) and private keys (d_i,p,q) 
where N = p q is constant for all denominations and only the e_i d_i = 1 mod 
(p-1)(q-1) differ between denominations.

Could we then aggregate verifications for coins with different denominations?
  sum_i FDH_{N,e_i}(m_i) mod N = sum_i sigma_i^{e_i} mod N
I’ve not quite found any good security proof for this aggregation scheme.

It likely break anonymity if wallets do this because the exchange can surely 
issue sigma_i that verify when aggregated but not when checked individually.

It may however be secure for the exchange to verify signatures in this way, and 
maybe even for the merchant, but remember our security rests on the RSA known 
target inversion assumption.  i have not found any security proof I really 
believe even under standard RSA assumptions.

I do not quite understand “sequential” aggregation but they happen at signing 
time so maybe they’d work for wallets, but more likely they break blinding too. 
 See:
  https://eprint.iacr.org/2018/082.pdf
  https://crypto.stanford.edu/~dabo/papers/aggsurvey.pdf

There are better batch verification schemes for Schnorr and ECDSA signatures, 
but those are much faster than RSA already.  See page 10 of 
https://cr.yp.to/badbatch/badbatch-20120919.pdf via 
https://crypto.stackexchange.com/a/58302

It’s possible aggregation gives a big advantage to blind BLS signatures over 
blind RSA signatures, but we could look for security proofs for the two RSA 
aggregation strategies I gave, and maybe try to understand others better.

Jeff

p.s.  Random things:
https://www.iacr.org/archive/pkc2010/60560484/60560484.pdf
http://www.sci.ccny.cuny.edu/~shpil/multiple-exp.pdf

signature.asc
Description: Message signed with OpenPGP