Abstract
In this paper we propose a binary field variant of the Joux-Lercier medium-sized Function Field Sieve, which results not only in complexities as low as \(L_{q^n}(1/3,(4/9)^{1/3})\) for computing arbitrary logarithms, but also in an heuristic polynomial time algorithm for finding the discrete logarithms of degree one and two elements when the field has a subfield of an appropriate size. To illustrate the efficiency of the method, we have successfully solved the DLP in the finite fields with 21971 and 23164 elements, setting a record for binary fields.
Research supported by the Claude Shannon Institute, Science Foundation Ireland Grant 06/MI/006. The fourth author was in addition supported by SFI Grant 08/IN.1/I1950.
Chapter PDF
Similar content being viewed by others
References
Adleman, L.M., Huang, M.D.A.: Function field sieve method for discrete logarithms over finite fields. Inform. and Comput. 151(1-2), 5–16 (1999)
Bailey, D.V., Paar, C., Sarkozy, G., Hofri, M.: Computation in optimal extension fields. In: Conference on The Mathematics of Public Key Cryptography, The Fields Institute for Research in the Mathematical Sciences, pp. 12–17 (2000)
Bluher, A.W.: On xq + 1 + ax + b. Finite Fields and Their Applications 10(3), 285–305 (2004)
Chung, F.R.K.: Diameters and eigenvalues. J. Amer. Math. Soc. 2(2), 187–196 (1989)
Coppersmith, D.: Fast evaluation of logarithms in fields of characteristic two. IEEE Trans. Inform. Theory 30(4), 587–593 (1984)
Faugère, J.-C., Otmani, A., Perret, L., Tillich, J.-P.: Algebraic cryptanalysis of mcEliece variants with compact keys. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 279–298. Springer, Heidelberg (2010)
Faugère, J.-C., Perret, L., Petit, C., Renault, G.: Improving the complexity of index calculus algorithms in elliptic curves over binary fields. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 27–44. Springer, Heidelberg (2012)
Gaudry, P., Hess, F., Smart, N.P.: Constructive and destructive facets of Weil descent on elliptic curves. J. Cryptology 15(1), 19–46 (2002)
Göloğlu, F., Granger, R., McGuire, G., Zumbrägel, J.: Discrete Logarithms in GF(21971). NMBRTHRY list (February 19, 2013)
Granger, R., Vercauteren, F.: On the discrete logarithm problem on algebraic tori. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 66–85. Springer, Heidelberg (2005)
Granlund, T.: The GMP development team: GNU MP: The GNU Multiple Precision Arithmetic Library, 5.0.5 edn (2012), http://gmplib.org/
Helleseth, T., Kholosha, A.: \(x^{{2^l}+1}+x+a\) and related affine polynomials over GF(2k). Cryptogr. Commun. 2(1), 85–109 (2010)
Joux, A.: Faster index calculus for the medium prime case application to 1175-bit and 1425-bit finite fields. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 177–193. Springer, Heidelberg (2013)
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)
Joux, A., Lercier, R.: Improvements to the general number field sieve for discrete logarithms in prime fields: a comparison with the gaussian integer method. Math. Comput. 72(242), 953–967 (2003)
Joux, A., Lercier, R.: The function field sieve in the medium prime case. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 254–270. Springer, Heidelberg (2006)
Joux, A., Lercier, R., Naccache, D., Thomé, E.: Oracle-assisted static diffie-hellman is easier than discrete logarithms. In: Parker, M.G. (ed.) Cryptography and Coding 2009. LNCS, vol. 5921, pp. 351–367. Springer, Heidelberg (2009)
LaMacchia, B.A., Odlyzko, A.M.: Solving large sparse linear systems over finite fields. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 109–133. Springer, Heidelberg (1991)
Lenstra, A.K., Lenstra Jr., H.W.: The development of the number field sieve. Lecture Notes in Mathematics, vol. 1554. Springer, Heidelberg (1993)
Lenstra Jr., H.W.: Finding isomorphisms between finite fields. Math. Comp. 56(193), 329–347 (1991)
Misoczki, R., Barreto, P.S.L.M.: Compact McEliece keys from Goppa codes. In: Jacobson Jr., M.J., Rijmen, V., Safavi-Naini, R. (eds.) SAC 2009. LNCS, vol. 5867, pp. 376–392. Springer, Heidelberg (2009)
Pollard, J.M.: Monte carlo methods for index computation (mod p). Math. Comp. 32(143), 918–924 (1978)
Rubin, K., Silverberg, A.: Torus-based cryptography. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 349–365. Springer, Heidelberg (2003)
Shoup, V.: NTL: A library for doing number theory, 5.5.2 edn. (2009), http://www.shoup.net/ntl/
Wagstaff, S., et al.: The Cunningham Project, http://homes.cerias.purdue.edu/~ssw/cun/index.html
Wan, D.: Generators and irreducible polynomials over finite fields. Math. Comp. 66(219), 1195–1212 (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 International Association for Cryptologic Research
About this paper
Cite this paper
Göloğlu, F., Granger, R., McGuire, G., Zumbrägel, J. (2013). On the Function Field Sieve and the Impact of Higher Splitting Probabilities. In: Canetti, R., Garay, J.A. (eds) Advances in Cryptology – CRYPTO 2013. CRYPTO 2013. Lecture Notes in Computer Science, vol 8043. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40084-1_7
Download citation
DOI: https://doi.org/10.1007/978-3-642-40084-1_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40083-4
Online ISBN: 978-3-642-40084-1
eBook Packages: Computer ScienceComputer Science (R0)