A General Polynomial Selection Method and New Asymptotic Complexities for the Tower Number Field Sieve Algorithm
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 \(\mathbb {F}_{p^{n}}\) where n is not a prime power. Their
- PDF / 2,067,557 Bytes
- 26 Pages / 439.37 x 666.142 pts Page_size
- 31 Downloads / 191 Views
Abstract. 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 Fpn 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., Lpn (1/3, (64/9)1/3 ) (resp. Lpn (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 Lpn (1/3, (96/9)1/3 ) (resp. Lpn (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.
1
Introduction
The discrete logarithm problem (DLP) over the multiplicative group of a finite field is a basic problem in cryptography. Two general approaches are known for tackling the DLP on such groups. These are the function field sieve (FFS) [1,2, 12,14] algorithm and the number field sieve (NFS) [8,13,15] algorithm. Let p be a prime, n ≥ 1 be an integer and Q = pn . Suppose that p = LQ (a, cp ) where LQ (a, cp ) = exp (cp + o(1))(ln Q)a (ln ln Q)1−a . Depending on the value of a, fields FQ are classified into the following types: small characteristic, if a ≤ 1/3; medium characteristic, if 1/3 < a < 2/3; boundary, if a = 2/3; and large characteristic, if a > 2/3. For fields of small characteristic, there has been tremendous progress in the FFS algorithm leading to a quasi-polynomial time algorithm [4]. Based on the FFS algorithms given in [4,11], a record computation of discrete log in the binary c International Association for Cryptologic Research 2016 J.H. Cheon and T. Takagi (Eds.): ASIACRYPT 2016, Part I, LNCS 10031, pp. 37–62, 2016. DOI: 10.1007/978-3-662-53887-6 2
38
P. Sarkar and S. Singh
extension field F29234 was reported by Granger et al. [9]. Applications of the FFS algorithm to the medium prime case have been reported in [10,14,19]. For medium to large characteristic finite fields, the NFS algorithm is generally considered to be the state-of-the-art. NFS was initially proposed for solving the factoring problem. Its application to DLP was first proposed by Gordon [8] for prime order fields. Application to composite order fields was shown by Schirokauer [21]. Important improvements to the NFS for prime order fields was given by Joux and Lercier [13]. A major step in the application of NFS was by Joux, Lercier, Smart and Vercauteren [15] who showed that the NFS algorithm is ap
Data Loading...
