In a recent work, Kim and Barbulescu had extended the tower number field sieve algorithm to obtain improved asymptotic complexities in the medium prime case for the discrete logarithm problem on F_(p~n) where n is not a prime power. Their method does not work when n is a composite prime power. For this case, we obtain new asymptotic complexities, e.g., L_(p~n) (1/3, (64/9)~(1/3)) (resp. L_(p~n) (1/3,1.88) for the multiple number field variation) when n is composite and a power of 2; the previously best known complexity for this case is L_(p~n)(1/3,(96/9)~(1/3)) (resp. L_(p~n) (1/3, 2.12)). These complexities may have consequences to the selection of key sizes for pairing based cryptography. The new complexities are achieved through a general polynomial selection method. This method, which we call Algorithm-C, extends a previous polynomial selection method proposed at Eurocrypt 2016 to the tower number field case. As special cases, it is possible to obtain the generalised Joux-Lercier and the Conjugation method of polynomial selection proposed at Eurocrypt 2015 and the extension of these methods to the tower number field scenario by Kim and Barbulescu. A thorough analysis of the new algorithm is carried out in both concrete and asymptotic terms.
展开▼
