Design of Elliptic Curves with Controllable Lower Boundary of Extension Degree for Reduction Attacks

  • Jinhui Chao
  • Kazuo Tanada
  • Shigeo Tsujii
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 839)


In this paper, we present a design strategy of elliptic curves whose extension degrees needed for reduction attacks have a controllable lower boundary, based on the complex multiplication fields method of Atkin and Morain over prime fields.


Elliptic Curve Elliptic Curf Discrete Logarithm Problem Ground Field Elliptic Curve Cryptosystems 
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.
    Miller, V. S.: Use of elliptic curves in cryptography. Advances in Cryptology-CRYPTO’85, Lecture Notes in Computer Science, 218 (1986) 417–426Google Scholar
  2. 2.
    Koblitz, N.: Elliptic Curve Cryptosystems. Math. Comp. 48 (1987) 203–209zbMATHCrossRefMathSciNetGoogle Scholar
  3. 3.
    Menezes, A. J.: Elliptic Curve Public Key Cryptosystems Kluwer Academic Publishers (1993)Google Scholar
  4. 4.
    Knuth, D. E.: The art of computer programming, Sorting and searching. vol. 3, Addison Wesley (1973)Google Scholar
  5. 5.
    Menezes, A. J., Vanstone, S., Okamoto T.: Reducing elliptic curve logarithms to logarithms in a finite field. Proc. of STOC’91 (1991) 80–89Google Scholar
  6. 6.
    Pohlig, S. C., Hellman, M. E.: An improved algorithm for computing logarithm over GF(p) and its cryptographic significance. IEEE Trans. Information Theory, IT-24,1 (1978) 106–110CrossRefMathSciNetGoogle Scholar
  7. 7.
    Adleman, L. M.: A subexponential algorithm for the discrete logarithm problem with applications to cryptography. Proc. of IEEE 20th Symp. on Foundations of Comp. Sci. (1979) 55–60Google Scholar
  8. 8.
    Koblitz, N.: Elliptic curve implementation of zero-knowledge blobs. Journal of Cryptology, vol. 4, No. 3 (1991) 207–213zbMATHCrossRefMathSciNetGoogle Scholar
  9. 9.
    Atkin, A. O. L., Morain F.: Elliptic curves and primality proving. Research Report 1256, INRIA, June (1990)Google Scholar
  10. 10.
    Morain, F., Building cyclic elliptic curves modulo large primes. Advances in Cryptology-EUROCRYPT’91, Lecture Notes in Computer Science, 547 (1991) 328–336Google Scholar
  11. 11.
    Chao, J., Tanada, K., Tsujii S.: On secure elliptic curves against the “reduction attack” and their design strategy. Proc. of SCIS’94 (1994) 10A, IEICE Tech. Report, ISEC93-100, 29–37Google Scholar
  12. 12.
    Schoof, R.: Elliptic curves over finite fields and the computation of square roots mod p. Math. Comp. 44 (1985) 483–494zbMATHCrossRefMathSciNetGoogle Scholar
  13. 13.
    Berlekamp, E. R.: Algebraic coding theory. MacGraw-Hill (1968)Google Scholar
  14. 14.
    Robin, M. O.: Probabilistic algorithm in finite fields. SIAM J. on Comput., Vol.9, No.2 (1980) 273–280CrossRefGoogle Scholar
  15. 15.
    Miyaji, A.: On ordinary elliptic curve cryptosystems. Advances in Cryptology-ASIACRYPT’91, Lecture Notes on Computer Science 739 (1991) 460–469Google Scholar
  16. 16.
    Miyaji, A.: Fast elliptic curve cryptosystems, Technical Report of IEICE (1993) COMP93–25Google Scholar
  17. 17.
    Chao, J., Ikemoto, H., Tanada, K., Tsujii, S.: On Discrete Logarithm Problems over elliptic curves with p-divisible groups. Proc. of Joint Workshop on Information Security and Cryptography, JW-ISC93 (1993) 99–104Google Scholar
  18. 18.
    Koblitz, N.: Constructing elliptic curve cryptosystems in characteristic 2. Advances in Cryptology-CRYPTO’90, Lecture Notes in Computer Science, 537 (1990) 156–167Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 1994

Authors and Affiliations

  • Jinhui Chao
    • 1
  • Kazuo Tanada
    • 2
  • Shigeo Tsujii
    • 1
  1. 1.Chuo UniversityTokyoJapan
  2. 2.Tokyo Institute of TechnologyTokyoJapan

Personalised recommendations