标题: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(jjwen@sdu.edu.cn)
通讯作者地址:[Wen, J] Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong UniversityChina;
来源:Theoretical Computer Science
出版年:2020
DOI:10.1016/j.tcs.2020.01.010
关键词: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.
收录类别:SCOPUS
资源类型:期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-85078735006&doi=10.1016%2fj.tcs.2020.01.010&partnerID=40&md5=b5f8053010a4e312c577114290b94b2e
TOP