Top

Published in:

2016 | OriginalPaper | Chapter

Extended Tower Number Field Sieve: A New Complexity for the Medium Prime Case

Authors : Taechan Kim, Razvan Barbulescu

Published in: Advances in Cryptology – CRYPTO 2016

Publisher: Springer Berlin Heidelberg

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We introduce a new variant of the number field sieve algorithm for discrete logarithms in \(\mathbb {F}_{p^n}\) called exTNFS. The most important modification is done in the polynomial selection step, which determines the cost of the whole algorithm: if one knows how to select good polynomials to tackle discrete logarithms in \(\mathbb {F}_{p^\kappa }\), exTNFS allows to use this method when tackling \(\mathbb {F}_{p^{\eta \kappa }}\) whenever \(\gcd (\eta ,\kappa )=1\). This simple fact has consequences on the asymptotic complexity of NFS in the medium prime case, where the complexity is reduced from \(L_Q(1/3,\root 3 \of {96/9})\) to \(L_Q(1/3,\root 3 \of {48/9})\), \(Q=p^n\), respectively from \(L_Q(1/3,2.15)\) to \(L_Q(1/3,1.71)\) if multiple number fields are used. On the practical side, exTNFS can be used when \(n=6\) and \(n=12\) and this requires to updating the keysizes used for the associated pairing-based cryptosystems.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Breaking the Circuit Size Barrier for Secure Computation Under DDH

next chapter Efficient Algorithms for Supersingular Isogeny Diffie-Hellman

Available only for authorised users

Aoki, K., Franke, J., Kleinjung, T., Lenstra, A.K., Osvik, D.A.: A kilobit special number field sieve factorization. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 1–12. Springer, Heidelberg (2007)CrossRef

Aranha, D.F., Fuentes-Castañeda, L., Knapp, E., Menezes, A., Rodríguez-Henríquez, F.: Implementing pairings at the 192-bit security level. In: Abdalla, M., Lange, T. (eds.) Pairing 2012. LNCS, vol. 7708, pp. 177–195. Springer, Heidelberg (2013)CrossRef

Barbulescu, R.: Algorithms of discrete logarithm in finite fields. Ph.D. thesis, Université de Lorraine, December 2013

Barbulescu, R.: An appendix for a recent paper of Kim. IACR Cryptology ePrint Archive 2015:1076 (2015)

Barbulescu, R., Gaudry, P., Guillevic, A., Morain, F.: Improving NFS for the discrete logarithm problem in non-prime finite fields. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 129–155. Springer, Heidelberg (2015)

Barbulescu, R., Gaudry, P., Joux, A., Thomé, E.: A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 1–16. Springer, Heidelberg (2014)CrossRef

Barbulescu, R., Gaudry, P., Kleinjung, T.: The towed number field sieve. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9453, pp. 31–55. Springer, Heidelberg (2015). doi:10.1007/978-3-662-48800-3_2 CrossRef

Barbulescu, R., Pierrot, C.: The multiple number field sieve for medium- and high-characteristic finite fields. LMS J. Comput. Math. 17, 230–246 (2014). The published version contains an error which is corrected in https://hal.inria.fr/hal-00952610 MathSciNetCrossRefMATH

Barreto, P.S.L.M., Naehrig, M.: Pairing-friendly elliptic curves of prime order. In: Preneel, B., Tavares, S. (eds.) SAC 2005. LNCS, vol. 3897, pp. 319–331. Springer, Heidelberg (2006)CrossRef

10.

Beuchat, J.-L., González-Díaz, J.E., Mitsunari, S., Okamoto, E., Rodríguez-Henríquez, F., Teruya, T.: High-speed software implementation of the optimal ate pairing over Barreto–Naehrig curves. In: Joye, M., Miyaji, A., Otsuka, A. (eds.) Pairing 2010. LNCS, vol. 6487, pp. 21–39. Springer, Heidelberg (2010)CrossRef

11.

Bistritz, Y., Lifshitz, A.: Bounds for resultants of univariate, bivariate polynomials. Linear Algebra Appl. 432(8), 1995–2005 (2010). Special Issue Devoted to the 15th ILAS Conference at Cancun, Mexico, 16–20 June 2008MathSciNetCrossRefMATH

12.

Bouvier, C., Gaudry, P., Imbert, L., Jeljeli, H., Thom, E.: Discrete logarithms in GF(p) – 180 digits. Announcement available at the NMBRTHRY Archives, item 004703 (2014)

13.

Chatterjee, S., Menezes, A., Rodriguez-Henriquez, F.: On implementing pairing-based protocols with elliptic curves of embedding degree one. Cryptology ePrint Archive, Report 2016/403 (2016). http://eprint.iacr.org/2016/403

14.

Chillotti, I., Gama, N., Georgieva, M., Izabachène, M.: A homomorphic LWE based E-voting scheme. In: Takagi, T., et al. (eds.) PQCrypto 2016. LNCS, vol. 9606, pp. 245–265. Springer, Heidelberg (2016). doi:10.1007/978-3-319-29360-8_16 CrossRef

15.

Commeine, A., Semaev, I.A.: An algorithm to solve the discrete logarithm problem with the number field sieve. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds.) PKC 2006. LNCS, vol. 3958, pp. 174–190. Springer, Heidelberg (2006)CrossRef

16.

Danilov, S., Popovyan, I.: Factorization of RSA-180 (2010). http://eprint.iacr.org/2010/270

17.

European Union Agency of Network and Information Security (ENISA): Algorithms, key sizes and parameters report, 2013 recommandations, version 1.0, October 2013. Publucation https://www.enisa.europa.eu/publications/algorithms-key-sizes-and-parameters-report

18.

Freeman, D.: Constructing pairing-friendly elliptic curves with embedding degree 10. In: Hess, F., Pauli, S., Pohst, M. (eds.) ANTS 2006. LNCS, vol. 4076, pp. 452–465. Springer, Heidelberg (2006)CrossRef

19.

Freeman, D., Scott, M., Teske, E.: A taxonomy of pairing-friendly elliptic curves. J. Cryptol. 23(2), 224–280 (2010)MathSciNetCrossRefMATH

20.

Gordon, D.M.: Discrete logarithms in \({GF}(p)\) using the number field sieve. SIAM J. Discret. Math. 6(1), 124–138 (1993)MathSciNetCrossRefMATH

21.

Granger, R., Kleinjung, T., Zumbrägel, J.: On the powers of 2. Cryptology ePrint Archive, Report 2014/300 (2014). http://eprint.iacr.org/2014/300

22.

Joux, A., Lercier, R., Smart, N.P., Vercauteren, F.: The number field sieve in the medium prime case. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 326–344. Springer, Heidelberg (2006)CrossRef

23.

Joux, A., Pierrot, C.: The special number field sieve in \(\mathbb{F}_{p^{n}}\). In: Cao, Z., Zhang, F. (eds.) Pairing 2013. LNCS, vol. 8365, pp. 45–61. Springer, Heidelberg (2014)CrossRef

24.

Kim, T.: Extended tower number field sieve: a new complexity for medium prime case. IACR Cryptology ePrint Archive 2015:1027 (2015)

25.

Lenstra, A.K.: Unbelievable security. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, p. 67. Springer, Heidelberg (2001)CrossRef

26.

Lenstra Jr., H.W.: Factoring integers with elliptic curves. Ann. Math. 126, 649–673 (1987)MathSciNetCrossRefMATH

27.

Matyukhin, D.V.: Effective version of the number field sieve for discrete logarithm in a field \({{GF}}(p^{k})\). Trudy po Diskretnoi Matematike 9, 121–151 (2006)

28.

National Institute of Standards and Technology (NIST): NIST Special Publication 800–57 Part 1 (Revised): Recommendation for Key Management, Part 1: General (Revised), July 2012. Publication http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57-Part1-revised2_Mar08-2007.pdf

29.

Odlyzko, A.M.: The future of integer factorization. CryptoBytes (Tech. Newsl. RSA Lab.) 1(2), 5–12 (1995)

30.

Pierrot, C.: The multiple number field sieve with conjugation and generalized Joux-Lercier methods. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 156–170. Springer, Heidelberg (2015)

31.

Sarkar, P., Singh, S.: New complexity trade-offs for the (multiple) number field sieve algorithm in non-prime fields. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 429–458. Springer, Heidelberg (2016). doi:10.1007/978-3-662-49890-3_17 CrossRef

32.

Schirokauer, O.: Discrete logarithms and local units. Philos. Trans. Roy. Soc. Lond. A: Math. Phys. Eng. Sci. 345(1676), 409–423 (1993)MathSciNetCrossRefMATH

33.

Schirokauer, O.: Using number fields to compute logarithms in finite fields. Math. Comput. 69(231), 1267–1283 (2000)MathSciNetCrossRefMATH

34.

Wiedemann, D.: Solving sparse linear equations over finite fields. IEEE Trans. Inf. Theor. 32(1), 54–62 (1986)MathSciNetCrossRefMATH

Title: Extended Tower Number Field Sieve: A New Complexity for the Medium Prime Case
Authors: Taechan Kim
Razvan Barbulescu
Publisher: Springer Berlin Heidelberg
Book: Advances in Cryptology – CRYPTO 2016
Print ISBN: 978-3-662-53017-7

Electronic ISBN: 978-3-662-53018-4

Copyright Year: 2016
DOI: https://doi.org/10.1007/978-3-662-53018-4_20

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner