nach oben

Erschienen in:

2015 | OriginalPaper | Buchkapitel

The Tower Number Field Sieve

verfasst von : Razvan Barbulescu, Pierrick Gaudry, Thorsten Kleinjung

Erschienen in: Advances in Cryptology – ASIACRYPT 2015

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

The security of pairing-based crypto-systems relies on the difficulty to compute discrete logarithms in finite fields \({\mathbb F}_{p^n}\) where n is a small integer larger than 1. The state-of-art algorithm is the number field sieve (NFS) together with its many variants. When p has a special form (SNFS), as in many pairings constructions, NFS has a faster variant due to Joux and Pierrot. We present a new NFS variant for SNFS computations, which is better for some cryptographically relevant cases, according to a precise comparison of norm sizes. The new algorithm is an adaptation of Schirokauer’s variant of NFS based on tower extensions, for which we give a middlebrow presentation.

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 Key-Recovery Attacks on ASASA

Nächstes Kapitel On the Impact of Known-Key Attacks on Hash Functions

The name, coined by Coppesmith, makes reference to the group who first used this technique [11].

Adleman, L.M., Lenstra, H.W.: Finding irreducible polynomials over finite fields. In: Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, pp. 350–355. ACM (1986)

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

Bai, S.: Polynomial selection for the number field sieve. Ph.D. thesis, Australian National University (2011)

Bai, S., Bouvier, C., Kruppa, A., Zimmermann, P.: Better polynomials for GNFS. Preprint (2014)

Barbulescu, R.: Algorithmes de logarithmes discrets dans les corps finis. Ph.D. thesis, Université de Lorraine (2013)

Barbulescu, R., Gaudry, P., Guillevic, A., Morain, F.: (Algebraic) improvements to the number field sieve for non-prime finite fields. Preprint http://hal.inria.fr/hal-01052449

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., Pierrot, C.: The multiple number field sieve for medium- and high-characteristic finite fields. LMS J. Comput. Math. 17, 230–246 (2014)MathSciNetCrossRef

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.

Bistritz, Y., Lifshitz, A.: Bounds for resultants of univariate and bivariate polynomials. Linear Algebra Appl. 432(8), 1995–2005 (2010)MATHMathSciNetCrossRef

11.

Blake, I.F., Fuji-Hara, R., Mullin, R.C., Vanstone, S.A.: Computing logarithms in finite fields of characteristic two. SIAM J. Algebraic Discrete Methods 5(2), 276–285 (1984)MATHMathSciNetCrossRef

12.

Brezing, F., Weng, A.: Elliptic curves suitable for pairing based cryptography. Des. Codes Crypt. 37(1), 133–141 (2005)MATHMathSciNetCrossRef

13.

Buhler, J.P., Lenstra Jr., H.W., Pomerance, C.: Factoring integers with the number field sieve. In: Lenstra, A.K., Lenstra Jr., H.W. (eds.) The Development of the Number Field Sieve. Lecture Notes in Mathematics, vol. 1554, pp. 50–94. Springer, Heidelberg (1993)

14.

Cohen, H.: Advanced Topics in Computational Number Theory. Graduate Texts in Mathematics, vol. 193. Springer, New York (2000) MATHCrossRef

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.

Coppersmith, D.: Modifications to the number field sieve. J. Cryptol. 6(3), 169–180 (1993)MATHMathSciNetCrossRef

17.

Foster, K.: HT90 and “simplest” number fields. Illinois J. Math. 55(4), 1621–1655 (2011)MATHMathSciNet

18.

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

19.

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

20.

Joux, A., Lercier, R.: The function field sieve is quite special. In: Fieker, C., Kohel, D.R. (eds.) ANTS 2002. LNCS, vol. 2369, pp. 431–445. Springer, Heidelberg (2002) CrossRef

21.

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

22.

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

23.

Kleinjung, T.: On polynomial selection for the general number field sieve. Math. Comput. 75(256), 2037–2047 (2006)MATHMathSciNetCrossRef

24.

Kleinjung, T.: Polynomial selection. Slides at CADO workshop (2008). http://cado.gforge.inria.fr/workshop/slides/kleinjung.pdf

25.

Kleinjung, T., Aoki, K., Franke, J., Lenstra, A.K., Thomé, E., Bos, J.W., Gaudry, P., Kruppa, A., Montgomery, P.L., Osvik, D.A., te Riele, H., Timofeev, A., Zimmermann, P.: Factorization of a 768-Bit RSA modulus. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 333–350. Springer, Heidelberg (2010) CrossRef

26.

Kleinjung, T., Bos, J.W., Lenstra, A.K.: Mersenne factorization factory. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8873, pp. 358–377. Springer, Heidelberg (2014)

27.

Lenstra, A.K., Lenstra Jr., H.W., Manasse, M., Pollard, J.: The number field sieve. The Development of the Number Field Sieve. Lecture Notes in Mathematics, vol. 1554, pp. 11–42. Springer, Heidelberg (1993)

28.

Matyukhin, D.V.: On asymptotic complexity of computing discrete logarithms over GF(p). Discrete Math. Appl. 13(1), 27–50 (2003)MATHMathSciNetCrossRef

29.

Miyaji, A., Nakabayashi, M., Takano, S.: New explicit conditions of elliptic curve traces for FR-reduction. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 84(5), 1234–1243 (2001)

30.

Murphy, A., Fitzpatrick, N.: Elliptic curves for pairing applications. Cryptology ePrint Archive, Report 2005/302 (2005). http://eprint.iacr.org/

31.

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)

32.

Pollard, J.M.: The lattice sieve. In: Lenstra, A.K., Lenstra, Jr., H.W.: The development of the number field sieve, vol. 1554 of Lecture Notes in Mathematics, pp. 43–49. Springer (1993)

33.

Schirokauer, O.: Discrete logarithms and local units. Philos. Trans. Roy. Soc. London Ser. A 345(1676), 409–423 (1993)MATHMathSciNetCrossRef

34.

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

35.

Semaev, I.: Special prime numbers and discrete logs in finite prime fields. Math. Comp. 71(237), 363–377 (2002)MATHMathSciNetCrossRef

36.

Wiedemann, D.H.: Solving sparse linear equations over finite fields. IEEE Trans. Inform. Theory 32(1), 54–62 (1986)MATHMathSciNetCrossRef

Titel: The Tower Number Field Sieve
verfasst von: Razvan Barbulescu
Pierrick Gaudry
Thorsten Kleinjung
Verlag: Springer Berlin Heidelberg
Buch: Advances in Cryptology – ASIACRYPT 2015
Print ISBN: 978-3-662-48799-0

Electronic ISBN: 978-3-662-48800-3

Copyright-Jahr: 2015
DOI: https://doi.org/10.1007/978-3-662-48800-3_2

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"