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

Faruk  Göloğlu; Antoine Joux

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: 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},
      url = {https://eprint.iacr.org/2018/430}
}