nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

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

verfasst von : Taechan Kim, Razvan Barbulescu

Erschienen in: Advances in Cryptology – CRYPTO 2016

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Breaking the Circuit Size Barrier for Secure Computation Under DDH

Nächstes Kapitel Efficient Algorithms for Supersingular Isogeny Diffie-Hellman

Nur mit Berechtigung zugänglich

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

Titel: Extended Tower Number Field Sieve: A New Complexity for the Medium Prime Case
verfasst von: Taechan Kim
Razvan Barbulescu
Verlag: Springer Berlin Heidelberg
Buch: Advances in Cryptology – CRYPTO 2016
Print ISBN: 978-3-662-53017-7

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

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

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner