Traps to the BGJT-Algorithm for Discrete Logarithms

Qi Cheng; Daqing Wan; Jincheng Zhuang

Paper 2013/673

Traps to the BGJT-Algorithm for Discrete Logarithms

Qi Cheng, Daqing Wan, and Jincheng Zhuang

Abstract

In the recent breakthrough paper by Barbulescu, Gaudry, Joux and Thomë, a quasi-polynomial time algorithm (QPA) is proposed for the discrete logarithm problem over finite fields of small characteristic. The time complexity analysis of the algorithm is based on several heuristics presented in their paper. We show that some of the heuristics are problematic in their original forms, in particular, when the field is not a Kummer extension. We believe that the basic idea behind the new approach should still work, and propose a fix to the algorithm in non-Kummer cases, without altering the quasi-polynomial time complexity. The modified algorithm is also heuristic. Further study is required in order to fully understand the effectiveness of the new approach.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: discrete logarithm problem
Contact author(s): qcheng @ cs ou edu
History: 2013-10-24: received
Short URL: https://ia.cr/2013/673
License: CC BY

BibTeX

@misc{cryptoeprint:2013/673,
      author = {Qi Cheng and Daqing Wan and Jincheng Zhuang},
      title = {Traps to the {BGJT}-Algorithm for Discrete Logarithms},
      howpublished = {Cryptology {ePrint} Archive, Paper 2013/673},
      year = {2013},
      url = {https://eprint.iacr.org/2013/673}
}