The complication of discrete logarithms in fields of characteristic 2

Valerij M. Maksimov, Eduard A. Primenko

Abstract


In real practical problems relating to the issue of information security calculations are frequently carried out in the fields of characteristic 2. In modern computing technologies, particularly, the usage of supercomputers, allow us to conduct calculations for quite large values . By developing computer technology and exploitation of new methods for analysis of information security systems, the parameter  should be increased.

In order to construct a cyclical group of a large order, which is widely used in the synthesis of cryptographic protocols, it is proposed to construct towers of quadratic extensions fields in characteristic 2. The complexity of constructing such extensions depending on the degree of the field is established. The paper provides a method for constructing a quadratic extension field  with the complexity of constructing an order  ,where it does not depend on  . The method is based on the construction of a two-dimensional algebra with one over the field. This process of doubling the degree of the field can be proceeded and construct the field every time, 2 times greater. In addition, It is not required to construct irreducible polynomials of higher degrees.

Full Text:

PDF (Russian)

References


A. S. Kuz'min, V. T. Markov, A. A. Mihalev, A. V. Mihalev, A. A. Nechaev. Kriptograficheskie algoritmy na gruppah i algebrah. Fundamental'naja i prikladnaja matematika, 2015, tom 20, #1, s. 205–222.

N. Moldovyan, A. Moldovyan. Vector Finite Groups on Primitives for Fast Digital Signature Algorithms. Information Fusion and Geographic Information Systems. Lecture Notes in Geo–information and Cartography, Springer–Verlag Berlin, Heidlberg, 2009, p. 317-330.

N. Koblic. Kurs teorii chisel i kriptografii. — M.: Nauchnoe izdatel'stvo ЋTVPL, 2001.

L. Adleman and J. DeMarrais. A subexponential algorithm for discrete logarithms over all finite fields. In D. Stinson, editor, Proceedings of CRYPTO’93, volime 773 of Lecture Notes in Comput. Sci., pages 147-158. Springer, 1993.

Gashkov S. B., Sergeev I. S. O slozhnosti i glubine bulevyh shem dlja umnozhenija i invertirovanija v konechnyh poljah harakteristiki 2. Diskretnaja matematika, tom 25, vyp. 1, 2013.

Cryptology ePrint Archive: Report 2013/095. A new index calculus algorithm with complexity L(1/4+o(1)) in very small characteristic. Antoine Joux

Herlestam T., Johannesson R. On computing logarithms over GF(2p) // BIT. 1981. V. 21. P. 326—336

ElGamal T. On computing logarithm over finite fields // Advances in cryptology — CRYPTO’85 (Santa Barbara, Calif., 1985). 1986. (Lect. Notes in Comput. Sci.; V. 218). P. 396—402.

Coppersmith D. Fast evaluation of discrete logarithms in fields of characteristic two. IEEE Trans // Inform. Theory. 1984. V. 30 (4). P. 587—594.

ThomDe E. Computation of discrete logarithms in GF(2607) // Advances in Cryptology — AsiaCrypt’2001. 2001. (Lect. Notes in Comput. Sci.; V. 2248). P. 107—124.

ThomDe E. Discrete logarithms in GF(2607). e-mail to the NMBRTHRY mailing list, February 2002. http://listserv.nodak.edu/archives/nmbrthry.html

Petit C., Quisquater JJ. (2012) On Polynomial Systems Arising from a Weil Descent. In: Wang X., Sako K. (eds) Advances in Cryptology – ASIACRYPT 2012. ASIACRYPT 2012. Lecture Notes in Computer Science, vol 7658. Springer, Berlin, Heidelberg

I. Semaev. New algorithm for the discrete logarithm problem on elliptic curves. Report 2015/310.

C. Petit and J.-J. Quisquater. On Polynomial Systems Arising from a Weil Descent. In: Wang X., Sako K. (eds) Advances in Cryptology – ASIACRYPT 2012. ASIACRYPT 2012. Lecture Notes in Computer Science, vol 7658. Springer, Berlin, Heidelberg


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность IT Congress 2024

ISSN: 2307-8162