[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:
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
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Taler] Batch RSA signature verification,
Jeff Burdges <=