[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Taler] Batch RSA signature verification

From: Jeff Burdges
Subject: [Taler] Batch RSA signature verification
Date: Sun, 2 Sep 2018 14:19:39 +0200

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

A batch verification without any exponentiations is insecure:

I think the conclusions here are kinda correct, but do not quite buy the proof: 

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:
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. 

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 

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.


p.s.  Random things:

Attachment: signature.asc
Description: Message signed with OpenPGP

reply via email to

[Prev in Thread] Current Thread [Next in Thread]