See equation 3 of the naive algoritm, because the curve point multiplication with base point P is done only once per batch of signatures it offers at least about 2x the speedup in any case.
Sorry to go back to this point...looking at Eq (3), it refers to the situation in which addresses are re-used, a behavior we recently had a thread about (it is discouraged). THis makes me suspicious
Relevant part of the introduction:
' In this paper, we propose three algorithms to verify original ECDSA signatures in batches. Our algorithms apply to all cases of ECDSA signatures sharing the same curve parameters, although we obtain good speedup figures when all the signatures in the batch come from the same signer.
Our algorithms are effective only for small batch sizes'
So am I understanding the speedup is by recognition of signatures by a particular key within a single block?