Indiscreet logarithms in finite fields of small characteristic

Robert Granger; Thorsten Kleinjung; Jens Zumbrägel

doi:10.3934/amc.2018017

Article Contents

2018, Volume 12, Issue 2: 263-286. Doi: 10.3934/amc.2018017

This issue Previous Article Constacyclic codes of length

$np^s$

over

$\mathbb{F}_{p^m}+u\mathbb{F}_{p^m}$

Next Article Hilbert quasi-polynomial for order domains and application to coding theory

Indiscreet logarithms in finite fields of small characteristic

1.
Laboratory for Cryptologic Algorithms, École polytechnique fédérale de Lausanne, Station 14, 1015 Lausanne, Switzerland
2.
Faculty of Computer Science and Mathematics, University of Passau, Innstraße 33, 94032 Passau, Germany

Received: March 31, 2016

Revised: November 30, 2017

Published: April 2018

The first author is supported by the Swiss National Science Foundation via grant number 200021-156420

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

Abstract

Recently, several striking advances have taken place regarding the discrete logarithm problem (DLP) in finite fields of small characteristic, despite progress having remained essentially static for nearly thirty years, with the best known algorithms being of subexponential complexity. In this expository article we describe the key insights and constructions which culminated in two independent quasi-polynomial algorithms. To put these developments into both a historical and a mathematical context, as well as to provide a comparison with the cases of so-called large and medium characteristic fields, we give an overview of the state-of-the-art algorithms for computing discrete logarithms in all finite fields. Our presentation aims to guide the reader through the algorithms and their complexity analyses ab initio.

Keywords:

Mathematics Subject Classification: Primary: 11Y16, 11T71.

Citation:

Full Text(HTML)

Table 1. Discrete logarithm record computations in finite fields of small or medium characteristic. Details, as well as further announcements, can be found in the number theory mailing list (https://listserv.nodak.edu/cgi-bin/wa.exe?A0=NMBRTHRY)

bitlength	charact.	Kummer	who/when	running time
127	2	no	Coppersmith 1984 [16]	$L(1/3\, , \, 1.526..1.587)$
401	2	no	Gordon, McCurley 1992 [26]	$L(1/3\, , \, 1.526..1.587)$
521	2	no	Joux, Lercier 2001 [36]	$L(1/3\, , \, 1.526)$
607	2	no	Thomé 2002	$L(1/3\, , \, 1.526..1.587)$
613	2	no	Joux, Lercier 2005	$L(1/3\, , \, 1.526)$
556	medium	yes	Joux, Lercier 2006 [38]	$L(1/3\, , \, 1.442)$
676	3	no	Hayashi et al. 2010 [31]	$L(1/3\, , \, 1.442)$
923	3	no	Hayashi et al. 2012 [30]	$L(1/3\, , \, 1.442)$
1175	medium	yes	Joux 24 Dec 2012 [34]	$L(1/3\, , \, 1.260)$
1425	medium	yes	Joux 6 Jan 2013 [34]	$L(1/3\, , \, 1.260)$
1778	2	yes	Joux 11 Feb 2013 [35]	$L(1/4 + o(1))$
1971	2	yes	GGMZ 19 Feb 2013 [23]	$L(1/3\, , \, 0.763)$
4080	2	yes	Joux 22 Mar 2013 [35]	$L(1/4 + o(1))$
809	2	no	CARAMEL 6 Apr 2013 [7]	$L(1/3\, , \, 1.526)$
6120	2	yes	GGMZ 11 Apr 2013 [24]	$L(1/4)$
6168	2	yes	Joux 21 May 2013	$L(1/4 + o(1))$
1303	3	no	AMOR 27 Jan 2014 [2]	$L(1/4 + o(1))$
4404	2	no	GKZ 30 Jan 2014 [27]	$L(1/4 + o(1))$
9234	2	yes	GKZ 31 Jan 2014	$L(1/4 + o(1))$
1551	3	no	AMOR 26 Feb 2014 [2]	$L(1/4 + o(1))$
3796	3	no	Joux, Pierrot 15 Sep 2014 [41]	$L(0 + o(1))$
1279	2	no	Kleinjung 17 Oct 2014	$L(0 + o(1))$
4841	3	no	ACCMORR, 18 Jul 2016 [3]	$L(0 + o(1))$

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	G. Adj, A. Menezes, T. Oliveira and F. Rodríguez-Henríquez, Weakness of $\mathbb{F}_{3^{6 · 509\;\;}}$ for discrete logarithm cryptography, in: Pairing-Based Cryptography—Pairing 2013, Springer, LNCS 8365 (2014), 20–44.
[2]	G. Adj, A. Menezes, T. Oliveira and F. Rodríguez-Henríquez, Computing discrete logarithms in $\mathbb{F}_{3^{6 · 137}}\;\;$ and $\mathbb{F}_{3^{6 · 163}}\;\;$ using Magma, in: Arithmetic of Finite Fields, Springer, LNCS 9061 (2015), 3–22.
[3]	G. Adj, I. Canales-Martínez, N. Cruz-Cortés, A. Menezes, T. Oliveira, L. RiveraZamarripa and F. Rodríguez-Henríquez, Computing discrete logarithms in cryptographicallyinteresting characteristic-three finite fields, IACR Cryptology ePrint Archive, (2016), 19 pages, eprint. iacr. org/2016/914.
[4]	L. M. Adleman, A subexponential algorithm for the discrete logarithm problem with applications to cryptography, in: 20th Annual Symposium on Foundations of Computer Science, (1979), 55–60.
[5]	L. M. Adleman, The function field sieve, in: Algorithmic Number Theory, Springer, LNCS 877 (1994), 108–121.
[6]	L. M. Adleman and M.-D. A. Huang, Function field sieve method for discrete logarithms over finite fields, Inform. and Comput., 151 (1999), 5-16. doi: 10.1006/inco.1998.2761.
[7]	R. Barbulescu, C. Bouvier, J. Detrey, P. Gaudry, H. Jeljeli, E. Thomé, M. Videau and P. Zimmermann (the CARAMEL group), Discrete logarithm in GF(2⁸⁰⁹) with FFS, in: Public-Key Cryptography—PKC 2014, Springer, LNCS 8383 (2014), 221–238.
[8]	R. Barbulescu, P. Gaudry, A. Guillevic and F. Morain, Improving NFS for the discrete logarithm problem in non-prime finite fields, in: Advances in Cryptology—EUROCRYPT 2015, Springer, LNCS 9056 (2015), 129–155.
[9]	R. Barbulescu, P. Gaudry, A. Joux and E. Thomé, A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic, in: Advances in Cryptology—EUROCRYPT 2014, Springer, LNCS 8441 (2014), 1–16.
[10]	R. Barbulescu, P. Gaudry and T. Kleinjung, The Tower Number Field Sieve, in: Advances in Cryptology—ASIACRYPT 2015, Springer, LNCS 9453 (2015), 31–55.
[11]	R. Barbulescu and T. Kim, Extended tower number field sieve: A new complexity for the medium prime case, in: Advances in Cryptology—CRYPTO 2016, Springer, LNCS 9814 (2016), 543–571.
[12]	A. W. Bluher, On $x^{q+1} + a x + b$, Finite Fields Appl., 10 (2004), 285-305. doi: 10.1016/j.ffa.2003.08.004.
[13]	D. Boneh and M. Frapringer, LNCS 2139 (2001nklin, Identity-based encryption from the Weil pairing, in: Advances in Cryptology—CRYPTO 2001, S), 213–229.
[14]	E. R. Canfield, P. Erdős and C. Pomerance, On a problem of Oppenheim concerning 'factorisatio numerorum', J. Number Theory, 17 (1983), 1-28. doi: 10.1016/0022-314X(83)90002-1.
[15]	A. Commeine and I. Semaev, An algorithm to solve the discrete logarithm problem with the number field sieve, in: Public Key Cryptography—PKC 2006, Springer, LNCS 3958 (2006), 174–190.
[16]	D. Coppersmith, Fast evaluation of logarithms in fields of characteristic two, IEEE Trans. Inform. Theory, 30 (1984), 587-594. doi: 10.1109/TIT.1984.1056941.
[17]	C. Diem, On the discrete logarithm problem in elliptic curves, Compositio Math., 147 (2011), 75-104. doi: 10.1112/S0010437X10005075.
[18]	W. Diffie and M. E. Hellman, New directions in cryptography, IEEE Trans. Inform. Theory, 22 (1976), 644-654. doi: 10.1109/TIT.1976.1055638.
[19]	T. ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, in: Advances in Cryptology—CRYPTO '84, Springer, LNCS 196 (1985), 10–18.
[20]	A. Enge and P. Gaudry, A general framework for subexponential discrete logarithm algorithms, Acta Arithmetica, 102 (2002), 83-103. doi: 10.4064/aa102-1-6.
[21]	S. D. Galbraith, Supersingular curves in cryptography, in: Advances in Cryptology—ASIACRYPT 2001, Springer, LNCS 2248 (2001), 495–513.
[22]	C. F. Gauß, Disquisitiones Arithmeticae, Translated into English by Arthur A. Clarke, S. J. Yale University Press, New Haven, Conn. -London, 1966.
[23]	F. Göloğlu, R. Granger, G. McGuire and J. Zumbrägel, On the function field sieve and the impact of higher splitting probabilities: Application to discrete logarithms in $\mathbb{F}_{2^{1971}}\;\;$ and $\mathbb{F}_{2^{3164}}\;\;$, in: Advances in Cryptology—CRYPTO 2013, Springer, LNCS 8043 (2013), 109–128.
[24]	F. Göloğlu, R. Granger, G. McGuire and J. Zumbrägel, Solving a 6120-bit DLP on a desktop computer, in: Selected Areas in Cryptography—SAC 2013, Springer, LNCS 8282 (2014), 136–152.
[25]	D. M. Gordon, Discrete logarithms in ${\rm GF}(p)$ using the number field sieve, SIAM J. Discrete Math., 6 (1993), 124-138. doi: 10.1137/0406010.
[26]	D. M. Gordon and K. S. McCurley, Massively parallel computation of discrete logarithms, in: Advances in Cryptology—CRYPTO'92, Springer, LNCS 740 (1993), 312–323.
[27]	R. Granger, T. Kleinjung and J. Zumbrägel, Breaking '128-bit secure' supersingular binary curves, in: Advances in Cryptology—CRYPTO 2014, Springer, LNCS 8617 (2014), 126–145.
[28]	R. Granger, T. Kleinjung and J. Zumbrägel, On the powers of 2, IACR Cryptology ePrint Archive, (2014), 18 pages, eprint. iacr. org/2014/300.
[29]	R. Granger, T. Kleinjung and J. Zumbrägel, On the discrete logarithm problem in finite fields of fixed characteristic, Trans. Amer. Math. Soc., 370 (2018), 3129-3145. doi: 10.1090/tran/7027.
[30]	T. Hayashi, T. Shimoyama, N. Shinohara, T. Takagi, Breaking pairing-based cryptosystems using η_T pairing over GF(3⁹⁷), in: Advances in Cryptology—ASIACRYPT 2012, Springer, LNCS 7658 (2012), 43–60.
[31]	T. Hayashi, N. Shinohara, L. Wang, S. I. Matsuo, M. Shirase and T. Takagi, Solving a 676-bit discrete logarithm problem in GF(3⁶ⁿ), in: Public Key Cryptography—PKC 2010, Springer, LNCS 6056 (2010), 351–367.
[32]	T. Helleseth and A. Kholosha, $\smash{x^{2^l+1}}+ x + a$ and related affine polynomials over $GF(2^k)$, Cryptogr. Commun., 2 (2010), 85-109. doi: 10.1007/s12095-009-0018-y.
[33]	A. Joux, A one round protocol for tripartite Diffie-Hellman, in: Algorithmic Number Theory, Springer, LNCS 1838 (2000), 385–393.
[34]	A. Joux, Faster index calculus for the medium prime case; application to 1175-bit and 1425-bit finite fields, in: Advances in Cryptology—EUROCRYPT 2013, Springer, LNCS 7881 (2013), 177–193.
[35]	A. Joux, A new index calculus algorithm with complexity L(1/4 + o(1)) in small characteristic, in: Selected Areas in Cryptography—SAC 2013, Springer, LNCS 8282 (2014), 355–379.
[36]	A. Joux and R. Lercier, The function field sieve is quite special, in: Algorithmic Number Theory, Springer, LNCS 2369 (2002), 431–445.
[37]	A. Joux and R. Lercier, Improvements to the general number field sieve for discrete logarithms in prime fields, Math. Comp., 72 (2003), 953-967. doi: 10.1090/S0025-5718-02-01482-5.
[38]	A. Joux and R. Lercier, The function field sieve in the medium prime case, in: Advances in Cryptology—EUROCRYPT 2006, Springer, LNCS 4004 (2006), 254–270.
[39]	A. Joux, R. Lercier, N. Smart and F. Vercauteren, The number field sieve in the medium prime case, in: Advances in Cryptology—CRYPTO 2006, Springer, LNCS 4117 (2006), 326–344.
[40]	A. Joux, A. M. Odlyzko and C. Pierrot, The past, evolving present and future of discrete logarithm, in: Open Problems in Mathematical and Computational Science, Springer (2014), 5–36.
[41]	A. Joux and C. Pierrot, Improving the polynomial time precomputation of Frobenius representation discrete logarithm algorithms, in: Advances in Cryptology—ASIACRYPT 2014, Springer, LNCS 8873 (2014), 378–397.
[42]	M. Kalkbrener, An upper bound on the number of monomials in determinants of sparse matrices with symbolic entries, Mathematica Pannonica, 8 (1997), 73-82.
[43]	T. Kim and J. Jeong, Extended tower number field sieve with application to finite fields of arbitrary composite extension degree, in: Public-Key Cryptography-PKC 2017, 10174 (2017), 388-408.
[44]	B. A. LaMacchia and A. M. Odlyzko, Solving large sparse linear systems over finite fields, in: Advances in Cryptology—CRYPTO'90, Springer, LNCS 537 (1991), 109–133.
[45]	C. Lanczos, An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, J. Research Nat. Bur. Standards, 45 (1950), 255-282. doi: 10.6028/jres.045.026.
[46]	A. K. Lenstra and H. W. Lenstra, Jr, Algorithms in number theory, in: Handbook of Theoretical Computer Science (A): Algorithms and Complexity, Elsevier, (1990), 673–715.
[47]	A. K. Lenstra and H. W. Lenstra, Jr (eds), The Development of the Number Field Sieve, Springer, 1993.
[48]	A. K. Lenstra, H. W. Lenstra Jr and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann., 261 (1982), 515-534. doi: 10.1007/BF01457454.
[49]	H. W. Lenstra Jr, Finding isomorphisms between finite fields, Math. Comp., 56 (1991), 329-347. doi: 10.1090/S0025-5718-1991-1052099-2.
[50]	R. Lovorn, Rigorous Subexponential Algorithms for Discrete Logarithms over Finite Fields, Ph. D. Thesis, University of Georgia, 1992.
[51]	V. I. Nechaev, On the complexity of a deterministic algorithm for a discrete logarithm, Mat. Zametki, 55 (1994), 91-101. doi: 10.1007/BF02113297.
[52]	J. Neukirch, Algebraic Number Theory, Translated from the 1992 German original, Springer, 1999.
[53]	A. M. Odlyzko, Discrete logarithms in finite fields and their cryptographic significance, in: Advances in Cryptology—CRYPTO'84, Springer, LNCS 209 (1985), 224–314.
[54]	A. M. Odlyzko, Discrete logarithms: the past and the future, Des. Codes Cryptogr., 19 (2000), 129-145. doi: 10.1023/A:1008350005447.
[55]	S. C. Pohlig and M. E. Hellman, An improved algorithm for computing logarithms over ${\rm GF}(p)$ and its cryptographic significance, IEEE Trans. Inform. Theory, 24 (1978), 106-110. doi: 10.1109/TIT.1978.1055817.
[56]	J. M. Pollard, Monte Carlo methods for index computation (mod p), Math. Comp., 32 (1978), 918-924. doi: 10.1090/S0025-5718-1978-0491431-9.
[57]	C. Pomerance, Analysis and comparison of some integer factoring algorithms, in: Computational Methods in Number Theory, Math. Centre Tracts, Math. Centrum, Amsterdam, 154 (1982), 89–139.
[58]	C. Pomerance, Fast, rigorous factorization and discrete logarithm algorithms, in: Discrete Algorithms and Complexity, Perspect. Comput., Academic Press, 15 (1987), 119–143.
[59]	R. Sakai, K. Ohgishi and M. Kasahara, Cryptosystems based on pairing, in: Symposium on Cryptography and Information Security, Okinawa, Japan, (2000), 26–28.
[60]	P. Sarkar and S. Singh, A general polynomial selection method and new asymptotic complexities for the tower number field sieve algorithm, in: Advances in Cryptology—ASIACRYPT 2016, Springer, LNCS 10031 (2016), 37–62.
[61]	O. Schirokauer, Discrete logarithms and local units, Philos. Trans. Roy. Soc. London Ser. A, 345 (1993), 409-423. doi: 10.1098/rsta.1993.0139.
[62]	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.
[63]	O. Schirokauer, Virtual logarithms, J. Algorithms, 57 (2005), 140-147. doi: 10.1016/j.jalgor.2004.11.004.
[64]	C.-P. Schnorr, Efficient signature generation by smart cards, J. Cryptology, 4 (1991), 161-174. doi: 10.1007/BF00196725.
[65]	I. A. Semaev, Special prime numbers and discrete logs in finite prime fields, Math. Comp., 71 (2002), 363-377. doi: 10.1090/S0025-5718-00-01308-9.
[66]	P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Computing J., 26 (1997), 1484-1509. doi: 10.1137/S0097539795293172.
[67]	V. Shoup, Lower bounds for discrete logarithms and related problems, in: Advances in Cryptology—EUROCRYPT'97, Springer, LNCS 1223 (1997), 256–266.
[68]	D. Wan, Generators and irreducible polynomials over finite fields, Math. Comp., 66 (1997), 1195-1212. doi: 10.1090/S0025-5718-97-00835-1.
[69]	D. H. Wiedemann, Solving sparse linear equations over finite fields, IEEE Trans. Inform. Theory, 32 (1986), 54-62. doi: 10.1109/TIT.1986.1057137.