Abstract
A new precomputation method is presented for computing g R for a fixed element g and a randomly chosen exponent R in a given group. Our method is more efficient and flexible than the previously proposed methods, especially in the case where the amount of storage available is very small or quite large. It is also very efficient in computing g R y E for a small size E and variable number y, which occurs in the verification of Schnorr’s identification scheme or its variants. Finally it is shown that our method is well-suited for parallel processing as well.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
D.E. Knuth, The art of computer programming, Vol.2: Seminumerical algorithms, second Edition, Addison-Wesley (1981).
J. Jedwab and C.J. Mitchell, “Minimum weight modified signed-digit representations and fast exponentiation,” Elect. Let. 25(17), 1171–1172 (1989).
C.N. Zhang, “An improved binary algorithm for RSA,” Computers Math. Applic. 25(6), 15–24 (1993).
J. Bos and M. Coster, “Addition chain heuristics,” In Advances in Cryptoloy-Crypto’89, Lecture Notes in Computer Science 435, (edited by G. Brassard), pp.400–407, Springer-Verlag (1990).
J. Sauerbrey and A. Dietel, “Resource requirements for the application of addition chains modulo exponentiation,” In Proc. Eurocrypt’92, Balatonfured, Hungary (1992).
P. Downey, B. Leony and R. Sethi, “Computing sequences with addition chains,” Siam J. Comput. 3, 638–696 (1981).
R.L. Rivest, A. Shamir and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems,” Commun. ACM, 21(2), 120–126 (1978).
T. ElGmal, “A public key cryptosystem and a signature scheme based on the discrete logarithm,” IEEE Trans. Inform. Theory 31(4), 469–472 (1985).
E.F. Brickell, D.M. Gordon, K.S. McCurley and D. Wilson, “Fast exponentiation with precomputation,” In Proc. Eurocrypt’92, Balatonfured, Hungary (1992).
C.P. Schnorr, “Efficient signature generation by smart cards,” J. Cryptology 4(3), 161–174 (1991).
E.F. Brickell and K.S. McCurley, “An interactive identification scheme based on discrete logarithms and factoring,” J. Cryptology 5(1) 29–39, (1992).
T. Okamoto, “Provably secure and practical identification schemes and corresponding signature schemes,” In Proc. Crypto’92, Santa Barbara, CA (1992).
D.W. Matula, “Basic digit sets for radix representation,” J. ACM 29, 1131–1143 (1982).
A proposed Federal information processing standard for digital signature standard (DSS), Federal Register 56(169), 42980–42982 (1991).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lim, C.H., Lee, P.J. (1994). More Flexible Exponentiation with Precomputation. In: Desmedt, Y.G. (eds) Advances in Cryptology — CRYPTO ’94. CRYPTO 1994. Lecture Notes in Computer Science, vol 839. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48658-5_11
Download citation
DOI: https://doi.org/10.1007/3-540-48658-5_11
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-58333-2
Online ISBN: 978-3-540-48658-9
eBook Packages: Springer Book Archive