Paper 2018/430

A Simplified Approach to Rigorous Degree 2 Elimination in Discrete Logarithm Algorithms

Faruk Göloğlu and Antoine Joux

Abstract

In this paper, we revisit the ZigZag strategy of Granger, Kleinjung and Zumbrägel. In particular, we provide a new algorithm and proof for the so-called degree 2 elimination step. This allows us to provide a stronger theorem concerning discrete logarithm computations in small characteristic fields $\mathbb{F}_{q^{k_0k}}$ with $k$ close to $q$ and $k_0$ a small integer. As in the aforementioned paper, we rely on the existence of two polynomials $h_0$ and $h_1$ of degree $2$ providing a convenient representation of the finite field $\mathbb{F}_{q^{k_0k}}$.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
discrete logarithm problem
Contact author(s)
farukgologlu @ gmail com
History
2018-05-11: received
Short URL
https://ia.cr/2018/430
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/430,
      author = {Faruk  Göloğlu and Antoine Joux},
      title = {A Simplified Approach to Rigorous Degree 2 Elimination in Discrete Logarithm Algorithms},
      howpublished = {Cryptology ePrint Archive, Paper 2018/430},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/430}},
      url = {https://eprint.iacr.org/2018/430}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.