标题：Refined analysis to the extended tower number field sieve
作者：Zhu Y.; Wen J.; Zhuang J.; Lv C.; Lin D.
作者机构：[Zhu, Y] Beijing Key Laboratory of Security and Privacy in Intelligent Transportation, Beijing Jiaotong University, Beijing, 100044, China, School of 更多
通讯作者地址：[Wen, J] Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong UniversityChina;
来源：Theoretical Computer Science
关键词：Complexity analysis; Descent phase; Discrete logarithm problem; Extended tower number field sieve; Smoothing phase
摘要：The hardness of discrete logarithm problem over finite fields is the security 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. In 2016, Kim and Barbulescu presented the extended tower number field sieve, which achieves a new complexity in the medium prime case and imposes a new estimation of the security of concrete parameters in certain cryptosystems such as pairing-based cryptosystems. In this paper, a refined analysis to this algorithm is given as follows. – Firstly, a uniform formula is given for the total complexity of the extended tower number field sieve. For a given polynomial selection method, this formula can directly give the complexity in this case. – Then, a method is proposed to improve the computation in the smoothing phase by exploring subfield structures when the extension degree is composite. – At last, the complexity of the descent phase is analyzed when sieving over degree-one polynomials and high-degree polynomials respectively and it is shown still negligible compared to the improved smoothing phase. © 2020 Elsevier B.V.