More Flexible Exponentiation with Precomputation

  • Chae Hoon Lim
  • Pil Joong Lee
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 839)


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.


Smart Card Signature Scheme Discrete Logarithm Problem Binary Method Signature Verification 
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.


  1. 1.
    D.E. Knuth, The art of computer programming, Vol.2: Seminumerical algorithms, second Edition, Addison-Wesley (1981).Google Scholar
  2. 2.
    J. Jedwab and C.J. Mitchell, “Minimum weight modified signed-digit representations and fast exponentiation,” Elect. Let. 25(17), 1171–1172 (1989).zbMATHCrossRefGoogle Scholar
  3. 3.
    C.N. Zhang, “An improved binary algorithm for RSA,” Computers Math. Applic. 25(6), 15–24 (1993).zbMATHCrossRefGoogle Scholar
  4. 4.
    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).Google Scholar
  5. 5.
    J. Sauerbrey and A. Dietel, “Resource requirements for the application of addition chains modulo exponentiation,” In Proc. Eurocrypt’92, Balatonfured, Hungary (1992).Google Scholar
  6. 6.
    P. Downey, B. Leony and R. Sethi, “Computing sequences with addition chains,” Siam J. Comput. 3, 638–696 (1981).CrossRefGoogle Scholar
  7. 7.
    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).zbMATHCrossRefMathSciNetGoogle Scholar
  8. 8.
    T. ElGmal, “A public key cryptosystem and a signature scheme based on the discrete logarithm,” IEEE Trans. Inform. Theory 31(4), 469–472 (1985).CrossRefMathSciNetGoogle Scholar
  9. 9.
    E.F. Brickell, D.M. Gordon, K.S. McCurley and D. Wilson, “Fast exponentiation with precomputation,” In Proc. Eurocrypt’92, Balatonfured, Hungary (1992).Google Scholar
  10. 10.
    C.P. Schnorr, “Efficient signature generation by smart cards,” J. Cryptology 4(3), 161–174 (1991).zbMATHCrossRefMathSciNetGoogle Scholar
  11. 11.
    E.F. Brickell and K.S. McCurley, “An interactive identification scheme based on discrete logarithms and factoring,” J. Cryptology 5(1) 29–39, (1992).zbMATHCrossRefGoogle Scholar
  12. 12.
    T. Okamoto, “Provably secure and practical identification schemes and corresponding signature schemes,” In Proc. Crypto’92, Santa Barbara, CA (1992).Google Scholar
  13. 13.
    D.W. Matula, “Basic digit sets for radix representation,” J. ACM 29, 1131–1143 (1982).zbMATHCrossRefMathSciNetGoogle Scholar
  14. 14.
    A proposed Federal information processing standard for digital signature standard (DSS), Federal Register 56(169), 42980–42982 (1991).Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 1994

Authors and Affiliations

  • Chae Hoon Lim
    • 1
  • Pil Joong Lee
    • 1
  1. 1.Department of Electrical EngineeringPohang University of Science and Technology (POSTECH)PohangKorea

Personalised recommendations