Cryptology ePrint Archive: Report 2015/859

Factor Base Discrete Logarithms in Kummer Extensions

Dianyan Xiao and Jincheng Zhuang and Qi Cheng

Abstract: The discrete logarithm over finite fields of small characteristic can be solved much more efficiently than previously thought. This algorithmic breakthrough is based on heuristic polynomial time algorithms to compute the factor base discrete logarithm. In this paper, we concentrate on the Kummer extension $ \F_{q^{2(q-1)}}. $ We design a new heuristic algorithm with an improved bit complexity $ \tilde{O}(q^{1+ \theta} ) $ (or algebraic complexity $\tilde{O}(q^{\theta} )$) to compute the discrete logarithms of elements in a factor base of cardinality $q^2$, where $ \theta < 2.373 $ is the matrix multiplication exponent. We reduce the correctness of the algorithm to a conjecture concerning the determinant of a simple $ (q+1)-$dimensional lattice, rather than to elusive smoothness assumptions. We verify the conjecture numerically for all $ q $'s such that $ \log_2(q^{2(q-1)}) \leq 5000 $, and provide theoretical supporting evidences.

Category / Keywords: public-key cryptography / Discrete logarithm, Finite fields, Kummer extension

Date: received 5 Sep 2015, last revised 5 Sep 2015

Contact author: zhuangjincheng at iie ac cn

Available format(s): PDF | BibTeX Citation

Version: 20150906:213655 (All versions of this report)

Short URL: ia.cr/2015/859

Discussion forum: Show discussion | Start new discussion