Batch exponentiation
David M’Raïhi, David Naccache · 1996
The signature generation phase of most DLP-based signature schemes (for instance Schnorr[10], El-Gamal[4] or the newly standardized D.S.A.[3]) includes the timeconsuming computation of r = g K mod p where k is random.This paper introduces a new computational strategy that can apply in this particular context :A batch exponentiation technique which allows the generation of large sets of exponentials without introducing any bias between the ks (that is, the signer can batch-compute the exponentials corresponding to arbitrarily imposed powers -for instance by an external random number generator).Our method offers real improvements over the prior art with various time and memory trade-offs.