Examination and implementation of the fast method for computing the order of elliptic curve

Authors

DOI:

https://doi.org/10.15587/1729-4061.2017.95194

Keywords:

Satoh method, Harley method, order of elliptic curves, binary field, trace of Frobenius

Abstract

Present study provides detailed analysis of the theoretical and experimental complexity of methods for canonical lift of elliptic curves that are defined over the binary field. The SST, MSST and Harley methods were used in the research. Results of theoretical studies revealed that the fastest (by execution time) algorithm for computing the order of the curve is the Harley method. Present work gives the substantiation (approximately 10 seconds for 1024 bits) of this method and the possibility of its application for binary fields. By the data obtained, we constructed a program model of the examined methods for canonical lift of elliptic curves and computing the norm. The software model allowed us to conduct experimental analysis of the algorithms for canonical lift of elliptic curves. In present article we experimentally confirmed a quasi quadratic dependence of the field size, over which curve is defined, and the time required for its canonical lift. Based on the results received, it is possible to argue that at present the fastest method for canonical lift is the Harley method. Our work demonstrated that the given method might be employed to modify the Ukrainian standard of electronic digital signature.

The relevance of research is related to the emergence of threats to the protection of information from the quantum cryptoanalysis for most modern asymmetric cryptosystems. However, modern cryptosystems should exist over the time that is necessary to find the candidates to replace them from the post-quantum cryptosystems. During such "transition period", classical cryptosystems should provide for the necessary level of stability, even under condition of constant extension of size in the system-wide parameters. The Ukrainian standard DSTU 4145–2002 has limitations on the size of system-wide parameters (up to 431 bits) and may not be able to account for a large reserve of stability. In addition, given the adoption of new standards for encryption and hash functions, in order to ensure the same level of security with the apparatus of elliptic curves, the latter must have parameters of size to 1024 bits. 

Author Biographies

Ivan Gorbenko, V. N. Karazin Kharkiv National University Svobody sq., 4, Kharkiv, Ukraine, 61022

Doctor of Technical Sciences, Professor

Department of Security of Information Systems and Technologies

Roman Hanzia, Kharkiv National University of Radio Electronics Nauky ave., 14, Kharkiv, Ukraine, 61166

Postgraduate student

Department of Information Security Technologies

References

  1. Horbenko, Yu. I., Hanzia, R. S. (2014). Analysis of the possibility of quantum computers and quantum computings for cryptanalysis of modern cryptosystems. Eastern-European Journal of Enterprise Technologies, 1 (9 (67)), 8–16. Available at: http://journals.uran.ua/eejet/article/view/19897/18759
  2. Hanzia, R. S., Horbenko, Yu. I. (2014). Analiz shlyakhiv rozvytku kryptohrafiyi pislya poyavy kvantovykh kompyuteriv. Visnyk Natsional'noho universytetu “L'vivs'ka politekhnika”: Kompyuterni systemy ta merezhi, 806, 40–48.
  3. Shor, P. W. (1997). Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Computing, 26 (5), 1484–1509. doi: 10.1137/s0097539795293172
  4. Horbenko, I. D., Horbenko, Yu. I. (2012). Prykladna kryptolohiya. Kharkiv: Fort, 868.
  5. Schoof, R. (1995). Counting points on an elliptic curve over finite fields. Proc. Journees Arithmetiques, 93, 219–252.
  6. Skjernaa, B. (2003). Satoh’s algorithm in characteristic 2. Mathematics of Computation, 72 (241), 477–488. doi: 10.1090/s0025-5718-02-01434-5
  7. Cohen, H., Frey, G., Avanzi, R., Doche, C., Lange, T., Nguyen, K., Vercauteren, F. (Eds.) (2005). Handbook of Elliptic and Hyperelliptic Curve Cryptography. NW.: Chapman & Hall/CRC, 807. doi: 10.1201/9781420034981
  8. Vercauteren, F. (2003). Computing zeta functions of curves over finite fields. Katholieke Universiteit Leuven, 195.
  9. Satoh, T. (2000). The Canonical Lift of an Ordinary Elliptic Curve over a Finite Field and its Point Counting. J. Ramanujan Math. Soc., 15 (4), 247–270.
  10. Satoh, T., Skjernaa, B., Taguchi, Y. (2003). Fast computation of canonical lifts of elliptic curves and its application to point counting. Finite Fields and Their Applications, 9 (1), 89–101. doi: 10.1016/s1071-5797(02)00013-8
  11. Harley, R. (2002). Asymptotically optimal p-adic point-counting. E-mail to NMBRTHRY list. Available at: https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0212&L=NMBRTHRY&F=&S=&P=7824
  12. Gaudry, P. (2002). A Comparison and a Combination of SST and AGM Algorithms for Counting Points of Elliptic Curves in Characteristic 2. Lecture Notes in Computer Science, 311–327. doi: 10.1007/3-540-36178-2_20
  13. Lercier, R., Lubicz, D. (2003). Counting Points on Elliptic Curves over Finite Fields of Small Characteristic in Quasi Quadratic Time. Lecture Notes In Computer Science, 360–373. doi: 10.1007/3-540-39200-9_22
  14. Hanzia, R. S. (2016). Otsinka obchyslyuval'noyi skladnosti metodiv pidrakhunku kil'kosti tochok na eliptychniy kryviy. Systemy obrobky informatsiyi, 8, 92–99.
  15. Satoh, T. (2001). Asymptotically fast algorithm for computing the Frobenius substitution and norms over unramied extension of p-adic number fields. Department of Mathematics, Faculty of Science, Saitame University, 1–21.

Downloads

Published

2017-04-21

How to Cite

Gorbenko, I., & Hanzia, R. (2017). Examination and implementation of the fast method for computing the order of elliptic curve. Eastern-European Journal of Enterprise Technologies, 2(9 (86), 11–21. https://doi.org/10.15587/1729-4061.2017.95194

Issue

Vol. 2 No. 9 (86) (2017): Information and controlling system

Section

Information and controlling system

License

Copyright (c) 2017 Ivan Horbenko, Roman Hanzia

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.

A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.