Paper 2016/727

Improvements on the Individual Logarithm Step in Extended Tower Number Field Sieve

Yuqing Zhu, Jincheng Zhuang, Chang Lv, and Dongdai Lin

Abstract

The hardness of discrete logarithm problem over finite fields is the foundation of many cryptographic protocols. When the characteristic of the finite field is medium or large, the state-of-art algorithms for solving the corresponding problem are the number field sieve and its variants. There are mainly three steps in such algorithms: polynomial selection, factor base logarithms computation, and individual logarithm computation. Note that the former two steps can be precomputed for fixed finite field, and the database containing factor base logarithms can be used by the last step for many times. In certain application circumstances, such as Logjam attack, speeding up the individual logarithm step is vital. In this paper, we devise a method to improve the individual logarithm step by exploring subfield structures. Our method is based on the extended tower number field sieve algorithm, and achieves more significant improvement when the extension degree has a large proper factor. We also perform some experiments to illustrate our algorithm and confirm the result.

Note: In this version, we removed the second problematic algorithm in the last version.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Discrete logarithm problemextended tower number field sieveindividual logarithmsmoothing phase
Contact author(s)
zhuangjincheng @ iie ac cn
History
2016-09-02: last of 2 revisions
2016-07-27: received
See all versions
Short URL
https://ia.cr/2016/727
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/727,
      author = {Yuqing Zhu and Jincheng Zhuang and Chang Lv and Dongdai Lin},
      title = {Improvements on the Individual Logarithm Step in Extended Tower Number Field Sieve},
      howpublished = {Cryptology ePrint Archive, Paper 2016/727},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/727}},
      url = {https://eprint.iacr.org/2016/727}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.