A unified polynomial selection method for the (tower) number field sieve algorithm

Palash Sarkar; Shashank Singh

doi:10.3934/amc.2019028

Article Contents

2019, Volume 13, Issue 3: 435-455. Doi: 10.3934/amc.2019028

This issue Previous Article New non-binary quantum codes from constacyclic codes over

$ \mathbb{F}_q[u,v]/\langle u^{2}-1, v^{2}-v, uv-vu\rangle $

Next Article A subspace code of size

$ \bf{333} $

in the setting of a binary

$ \bf{q} $

-analog of the Fano plane

A unified polynomial selection method for the (tower) number field sieve algorithm

Palash Sarkar^1, and
Shashank Singh^2, ,

1.
Indian Statistical Institute, Kolkata 700108, West Bengal, India
2.
Indian Institute of Science Education and Research Bhopal, Bhopal 462066, Madhya Pradesh, India

^* Corresponding author: Shashank Singh
^* Corresponding author: Shashank Singh

Received: July 2018

Revised: January 2019

Published: August 2019

Abstract / Introduction Full Text(HTML) Figure(5) / Table(1) Related Papers Cited by

Abstract

At Eurocrypt 2015, Barbulescu et al. introduced two new methods of polynomial selection, namely the Conjugation and the Generalised Joux-Lercier methods, for the number field sieve (NFS) algorithm as applied to the discrete logarithm problem over finite fields. A sequence of subsequent works have developed and applied these methods to the multiple and the (extended) tower number field sieve algorithms. This line of work has led to new asymptotic complexities for various cases of the discrete logarithm problem over finite fields. The current work presents a unified polynomial selection method which we call Algorithm $ \mathcal{D} $. Starting from the Barbulescu et al. paper, all the subsequent polynomial selection methods can be seen as special cases of Algorithm $ \mathcal{D} $. Moreover, for the extended tower number field sieve (exTNFS) and the multiple extended TNFS (MexTNFS), there are finite fields for which using the polynomials selected by Algorithm $ \mathcal{D} $ provides the best asymptotic complexity. Suppose $ Q = p^n $ for a prime $ p $ and further suppose that $ n = \eta\kappa $ such that there is a $ c_{\theta}>0 $ for which $ p^{\eta} = L_Q(2/3, c_{\theta}) $. For $ c_{\theta}>3.39 $, the complexity of exTNFS-$ \mathcal{D} $ is lower than the complexities of all previous algorithms; for $ c_{\theta}\notin (0, 1.12)\cup[1.45, 3.15] $, the complexity of MexTNFS-$ \mathcal{D} $ is lower than that of all previous methods.

Keywords:

Mathematics Subject Classification: Primary: 11Y16; Secondary: 94A60.

Citation:

Full Text(HTML)

Figure 1. Tower of Number Fields

Download: Full-size image PowerPoint slide

Figure 2. Commutative diagram for TNFS

Download: Full-size image PowerPoint slide

Figure 3. Product of norms for various polynomial selection methods

Download: Full-size image PowerPoint slide

Figure 4. Complexity plot for medium characteristic finite fields

Download: Full-size image PowerPoint slide

Figure 5. Complexity plot for medium characteristic finite fields

Download: Full-size image PowerPoint slide

Table 1. Parameterised efficiency estimates for NFS obtained from the different polynomial selection methods

Method	Norms Product	Conditions
NFS-JLSV1[21]	$E^{\frac{4n}{t}}Q^{\frac{t-1}{n}}$
NFS-GJL[4]	$E^{\frac{2(2r+1)}{t}}Q^{\frac{t-1}{r+1}}$	$r\geq n$
NFS-Conj[4]	$E^{\frac{6n}{t}}Q^{\frac{t-1}{2n}}$
NFS-$\mathcal{A}$[31]	$E^{\frac{2d(2r+1)}{t}}Q^{\frac{t-1}{d(r+1)}}$	$d\|n$, $r\geq n/d$
exTNFS-JLSV1[24]	$E^{\frac{4\kappa}{t}}Q^{\frac{t-1}{\kappa}}$	$n=\eta\kappa$, $\gcd(\eta, \kappa)=1$
exTNFS-GJL[24]	$E^{\frac{2(2r+1)}{t}}Q^{\frac{t-1}{r+1}}$	$n=\eta\kappa$, $\gcd(\eta, \kappa)=1$, $r\geq\kappa$
exTNFS-$\mathcal{C}$[30]	$E^{\frac{2d(2r+1)}{t}}Q^{\frac{(t-1)(r(\lambda-1)+k)}{\kappa(r\lambda+1)}}$	$n=\eta\kappa$, $k=\kappa/d$, $r\geq k$, $\lambda\in\{1, \eta\}$
exTNFS-gConj [25]	$E^{\frac{6\kappa}{t}}Q^{\frac{t-1}{2\kappa}}$	$n=\eta\kappa$
exTNFS-$\mathcal{D}$	$E^{\frac{2d(2r+1)}{t}}Q^{\frac{(t-1)}{d(r+1)}}$	$n=\eta\kappa$, $d\|\kappa$, $\gcd(\eta, \kappa/d)=1$, $r\geq \kappa/d$
exTNFS-$\mathcal{D}$	$E^{\frac{2d(2r+1)}{t}}Q^{\frac{(t-1)}{d(r+1)}}$	NFS-GJL:$\eta=d=1$ NFS-Conj:$\eta=1$, $d=\kappa=n$, $r=1$ NFS-$\mathcal{A}$:$\eta=1$, $\kappa=n$, $d\|n$, $r\geq n/d$ exTNFS-GJL:$d=1$ exTNFS-gConj:$d=\kappa$, $r=1$

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	L. M. Adleman, The function field sieve, In Leonard M. Adleman and Ming-Deh A. Huang, editors, ANTS, volume 877 of Lecture Notes in Computer Science, pages 108–121. Springer, 1994. doi: 10.1007/3-540-58691-1_48.
[2]	L. M. Adleman and M.-D. A. Huang, Function field sieve method for discrete logarithms over finite fields, Inf. Comput., 151 (1999), 5-16. doi: 10.1006/inco.1998.2761.
[3]	R. Barbulescu and S. Duquesne, Updating key size estimations for pairings, Journal of Cryptology, 2018, 1–39. https://link.springer.com/article/10.1007/s00145-018-9280-5. doi: 10.1007/s00145-018-9280-5.
[4]	R. Barbulescu, P. Gaudry, A. Guillevic and F. Morain, Improving NFS for the discrete logarithm problem in non-prime finite fields, In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology – EUROCRYPT 2015, volume 9056 of Lecture Notes in Computer Science, pages 129–155. Springer Berlin Heidelberg, 2015. doi: 10.1007/978-3-662-46800-5_6.
[5]	R. Barbulescu, P. Gaudry, A. Joux and E. Thomé, A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic, In Phong Q. Nguyen and Elisabeth Oswald, editors, Advances in Cryptology - EUROCRYPT 2014 - 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, May 11-15, 2014. Proceedings, volume 8441 of Lecture Notes in Computer Science, pages 1–16. Springer, 2014. doi: 10.1007/978-3-642-55220-5_1.
[6]	R. Barbulescu, P. Gaudry and T. Kleinjung, The tower number field sieve, In Tetsu Iwata and Jung Hee Cheon, editors, Advances in Cryptology - ASIACRYPT 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29 - December 3, 2015, Proceedings, Part II, volume 9453 of Lecture Notes in Computer Science, pages 31–55. Springer, 2015. doi: 10.1007/978-3-662-48800-3_2.
[7]	R. Barbulescu and C. Pierrot, The multiple number field sieve for medium and high characteristic finite fields, LMS Journal of Computation and Mathematics, 17 (2014), 230-246. doi: 10.1112/S1461157014000369.
[8]	Y. Bistritz and A. Lifshitz, Bounds for resultants of univariate and bivariate polynomials, Linear Algebra and its Applications, 432 (2010), 1995–2005. Special issue devoted to the 15th ILAS Conference at Cancun, Mexico, June 16-20, 2008. doi: 10.1016/j.laa.2009.08.012.
[9]	N. Gama and P. Q. Nguyen, Predicting lattice reduction, In Nigel Smart, editor, Advances in Cryptology – EUROCRYPT 2008, 31–51, Lecture Notes in Comput. Sci., 4965, Springer, Berlin, 2008. doi: 10.1007/978-3-540-78967-3_3.
[10]	P. Gaudry, L. Grémy and M. Videau, Collecting relations for the number field sieve in GF(p⁶), LMS Journal of Computation and Mathematics, 19 (2016), 332-350. doi: 10.1112/S1461157016000164.
[11]	D. M. Gordon, Discrete logarithms in GF(p) using the number field sieve, SIAM J. Discrete Math., 6 (1993), 124-138. doi: 10.1137/0406010.
[12]	R. Granger, T. Kleinjung and J. Zumbrägel, Discrete logarithms in GF(2⁹²³⁴), NMBRTHRY list, January 2014.
[13]	A. Guillevic, Computing individual discrete logarithms faster in GF(pⁿ) with the NFS-DL algorithm, Advances in cryptology–ASIACRYPT 2015. Part I, 149–173, Lecture Notes in Comput. Sci., 9452, Springer, Heidelberg, 2015, http://eprint.iacr.org/. doi: 10.1007/978-3-662-48797-6_7.
[14]	A. Guillevic, F. Morain and E. Thomé, Solving discrete logarithms on a 170-bit MNT curve by pairing reduction, Selected Areas in Cryptography – SAC 2016, 2017,559–578. http://eprint.iacr.org/. doi: 10.1007/978-3-319-69453-5_30.
[15]	K. Hayasaka, K. Aoki, T. Kobayashi and T. Takagi, A construction of 3-dimensional lattice sieve for number field sieve over $ \mathbb{F}_{p^n} $, JSIAM Lett., 6 (2014), 53-56. doi: 10.14495/jsiaml.6.53.
[16]	A. Joux, Faster index calculus for the medium prime case: Application to 1175-bit and 1425-bit finite fields, In Thomas Johansson and Phong Q. Nguyen, editors, EUROCRYPT, volume 7881 of Lecture Notes in Computer Science, pages 177–193. Springer, 2013. doi: 10.1007/978-3-642-38348-9_11.
[17]	A. Joux, A new index calculus algorithm with complexity $ L(1/4+o(1)) $ in small characteristic, In Tanja Lange, Kristin E. Lauter, and Petr Lisonek, editors, Selected Areas in Cryptography - SAC 2013 - 20th International Conference, Burnaby, BC, Canada, August 14-16, 2013, Revised Selected Papers, volume 8282 of Lecture Notes in Computer Science, pages 355–379. Springer, 2014. doi: 10.1007/978-3-662-43414-7_18.
[18]	A. Joux and R. Lercier, The function field sieve is quite special, In Claus Fieker and David R. Kohel, editors, ANTS, volume 2369 of Lecture Notes in Computer Science, pages 431–445. Springer, 2002. doi: 10.1007/3-540-45455-1_34.
[19]	A. Joux and R. Lercier, Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the Gaussian integer method, Math. Comput., 72 (2003), 953-967. doi: 10.1090/S0025-5718-02-01482-5.
[20]	A. Joux and R. Lercier, The function field sieve in the medium prime case, In Serge Vaudenay, editor, EUROCRYPT, volume 4004 of Lecture Notes in Computer Science, pages 254–270. Springer, 2006. doi: 10.1007/11761679_16.
[21]	A. Joux, R. Lercier, N. P. Smart and F. Vercauteren, The number field sieve in the medium prime case, In Cynthia Dwork, editor, Advances in Cryptology - CRYPTO 2006, 26th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 2006, Proceedings, volume 4117 of Lecture Notes in Computer Science, pages 326–344. Springer Berlin Heidelberg, 2006. doi: 10.1007/11818175_19.
[22]	A. Joux and C. Pierrot, The special number field sieve in $ \mathbb{F}_{p^n} $ - Application to pairing-friendly constructions, In Zhenfu Cao and Fangguo Zhang, editors, Pairing-Based Cryptography - Pairing 2013 - 6th International Conference, Beijing, China, November 22-24, 2013, Revised Selected Papers, volume 8365 of Lecture Notes in Computer Science, pages 45–61. Springer, 2013. doi: 10.1007/978-3-319-04873-4_3.
[23]	A. Joux and C. Pierrot, Improving the polynomial time precomputation of Frobenius representation discrete logarithm algorithms - simplified setting for small characteristic finite fields, In Palash Sarkar and Tetsu Iwata, editors, Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7-11, 2014. Proceedings, Part I, volume 8873 of Lecture Notes in Computer Science, pages 378–397. Springer, 2014. doi: 10.1007/978-3-662-45611-8_20.
[24]	T. Kim and R. Barbulescu, Extended tower number field sieve: A new complexity for the medium prime case, In Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part I, volume 9814 of Lecture Notes in Computer Science, pages 543–571. Springer, 2016. doi: 10.1007/978-3-662-53018-4_20.
[25]	T. Kim and J. Jeong, Extended tower number field sieve with application to finite fields of arbitrary composite extension degree, In Serge Fehr, editor, Public-Key Cryptography - PKC 2017 - 20th IACR International Conference on Practice and Theory in Public-Key Cryptography, Amsterdam, The Netherlands, March 28-31, 2017, Proceedings, Part I, volume 10174 of Lecture Notes in Computer Science, pages 388–408. Springer, 2017.
[26]	A. K. Lenstra, H. W. Lenstra and L. Lovász, Factoring polynomials with rational coefficients, Mathematische Annalen, 261 (1982), 515-534. doi: 10.1007/BF01457454.
[27]	A. Menezes, P. Sarkar and S. Singh, Challenges with assessing the impact of NFS advances on the security of pairing-based cryptography, In Mycrypt, volume 10311 of Lecture Notes in Computer Science, pages 83–108. Springer, 2016. doi: 10.1007/978-3-319-61273-7_5.
[28]	C. Pierrot, The multiple number field sieve with conjugation and generalized Joux-Lercier methods, In Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part I, pages 156–170, Lecture Notes in Comput. Sci., 9056, Springer, Heidelberg, 2015. doi: 10.1007/978-3-662-46800-5_7.
[29]	P. Sarkar and S. Singh, Fine tuning the function field sieve algorithm for the medium prime case, IEEE Transactions on Information Theory, 62 (2016), 2233–2253. http://ieeexplore.ieee.org/xpl/articleDetails.jsp?reload=true&arnumber=7405328. doi: 10.1109/TIT.2016.2528996.
[30]	P. Sarkar and S. Singh, A general polynomial selection method and new asymptotic complexities for the tower number field sieve algorithm, In Jung Hee Cheon and Tsuyoshi Takagi, editors, Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4-8, 2016, Proceedings, Part I, volume 10031 of Lecture Notes in Computer Science, pages 37–62, 2016. doi: 10.1007/978-3-662-53887-6_2.
[31]	P. Sarkar and S. Singh, New complexity trade-offs for the (multiple) number field sieve algorithm in non-prime fields, In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part I, volume 9665 of Lecture Notes in Computer Science, pages 429–458, Springer, 2016. doi: 10.1007/978-3-662-49890-3_17.
[32]	O. Schirokauer, Discrete logarithms and local units, Philosophical Transactions: Physical Sciences and Engineering, 345 91993), 409–423. doi: 10.1098/rsta.1993.0139.
[33]	O. Schirokauer, Using number fields to compute logarithms in finite fields, Math. Comp., 69 (2000), 1267-1283. doi: 10.1090/S0025-5718-99-01137-0.
[34]	O. Schirokauer, Virtual logarithms, J. Algorithms, 57 (2005), 140-147. doi: 10.1016/j.jalgor.2004.11.004.
[35]	D. H. Wiedemann, Solving sparse linear equations over finite fields, IEEE Trans. Information Theory, 32 (1986), 54–62. doi: 10.1109/TIT.1986.1057137.
[36]	P. Zajac, On the use of the lattice sieve in the 3d NFS, Tatra Mountains Mathematical Publications, 45 (2010), 161-172. doi: 10.2478/v10127-010-0012-y.