Discrete logarithm records explained

Discrete logarithm records are the best results achieved to date in solving the discrete logarithm problem, which is the problem of finding solutions x to the equation

gx=h

given elements g and h of a finite cyclic group G. The difficulty of this problem is the basis for the security of several cryptographic systems, including Diffie–Hellman key agreement, ElGamal encryption, the ElGamal signature scheme, the Digital Signature Algorithm, and the elliptic curve cryptography analogues of these. Common choices for G used in these algorithms include the multiplicative group of integers modulo p, the multiplicative group of a finite field, and the group of points on an elliptic curve over a finite field.

The current record for integers modulo prime numbers, set in December 2019, is a discrete logarithm computation modulo a prime with 240 digits. For characteristic 2, the current record for finite fields, set in July 2019, is a discrete logarithm over

GF(230750)

. When restricted to prime exponents, the current record, set in October 2014, is over

GF(21279)

. For characteristic 3, the current record, set in July 2016, is over

GF(36*509)

. For Kummer extension fields of "moderate" characteristic, the current record, set in January 2013, is over

GF(3334135357)

. For fields of "moderate" characteristic (which are not necessarily Kummer extensions), the current record, published in 2022, is over

GF(211102350)

.

Integers modulo p

Previous records for integers modulo p include:

Also of note, in July 2016, Joshua Fried, Pierrick Gaudry, Nadia Heninger, Emmanuel Thome published their discrete logarithm computation on a 1024-bit prime.[7] They generated a prime susceptible to the special number field sieve, using the specialized algorithm on a comparatively small subgroup (160-bits). While this is a small subgroup, it was the standardized subgroup size used with the 1024-bit digital signature algorithm (DSA).

Discrete logarithm records modulo primes!Size of prime!Type of prime!Date announced!Announced by!Algorithm!Hardware!Notes
240-digit (795-bit)safe primedata-sort-value="2019-12-02" 2 December 2019
  • Fabrice Boudot
  • Pierrick Gaudry
  • Aurore Guillevic
  • Nadia Heninger
  • Emmanuel Thomé
number field sieveThe prime used was RSA-240 + 49204 (the first safe prime above RSA-240). This computation was performed simultaneously with the factorization of RSA-240, using the Number Field Sieve algorithm and the open-source CADO-NFS software. Improvements in the algorithms and software made this computation about three times faster than would be expected from previous records after accounting for improvements in hardware.
1024-bitdata-sort-value="2016-07-01" July 2016
  • Joshua Fried
  • Pierrick Gaudry
  • Nadia Heninger
  • Emmanuel Thome
special number field sieveThe researchers generated a prime susceptible to the special number field sieve using a specialized algorithm on a comparatively small subgroup (160-bits).
232-digit (768-bit)safe primedata-sort-value="2016-06-16" 16 June 2016
  • Thorsten Kleinjung
  • Claus Diem
  • Arjen K. Lenstra
  • Christine Priplata
  • Colin Stahlke
number field sieveThis computation started in February 2015.
180 digit (596-bit)safe primedata-sort-value="2014-06-11" 11 June 2014
  • Cyril Bouvier
  • Pierrick Gaudry
  • Laurent Imbert
  • Hamza Jeljeli
  • Emmanuel Thomé
number field sieve
160-digit (530-bit) safe primedata-sort-value="2007-02-05" 5 February 2007Thorsten Kleinjungnumber field sievevarious PCs, a parallel computing cluster
130-digit (431-bit)strong primedata-sort-value="2005-06-18" 18 June 2005 number field sieve1.15 GHz 16-processor HP AlphaServer GS1280

Finite fields

The current record in a finite field of characteristic 2 was announced by Robert Granger, Thorsten Kleinjung, Arjen Lenstra, Benjamin Wesolowski, and Jens Zumbrägel on 10 July 2019.[8] This team was able to compute discrete logarithms in GF(230750) using 25,481,219 core hours on clusters based on the Intel Xeon architecture. This computation was the first large-scale example using the elimination step of the quasi-polynomial algorithm.[9]

Previous records in a finite field of characteristic 2 were announced by:

The current record in a finite field of characteristic 2 of prime degree was announced by Thorsten Kleinjung on 17 October 2014. The calculation was done in a field of 21279 elements and followed essentially the path sketched for

GF(24)

in [16] with two main exceptions in the linear algebra computation and the descent phase. The total running time was less than four core years.[17] The previous record in a finite field of characteristic 2 of prime degree was announced by the CARAMEL group on April 6, 2013. They used the function field sieve to compute a discrete logarithm in a field of 2809 elements.[18]

The current record for a field of characteristic 3 was announced by Gora Adj, Isaac Canales-Martinez, Nareli Cruz-Cortés, Alfred Menezes, Thomaz Oliveira, Francisco Rodriguez-Henriquez, and Luis Rivera-Zamarripa on 18 July 2016. The calculation was done in the 4841-bit finite field with 36 · 509 elements and was performed on several computers at CINVESTAV andthe University of Waterloo. In total, about 200 core years of computing time was expended on the computation.[19]

Previous records in a finite field of characteristic 3 were announced:

Over fields of "moderate"-sized characteristic, notable computations as of 2005 included those a field of 6553725 elements (401 bits) announced on 24 Oct 2005, and in a field of 37080130 elements (556 bits) announced on 9 Nov 2005.[25] The current record (as of 2013) for a Kummer extension finite field of "moderate" characteristic was announced on 6 January 2013. The team used a new variation of the function field sieve for the medium prime case to compute a discrete logarithm in a Kummer extension field of 3334135357 elements (a 1425-bit finite field).[26] [27] The same technique had been used a few weeks earlier to compute a discrete logarithm in a Kummer extension field of 3355377147 elements (an 1175-bit finite field).[27] [28] The current record (as of 2022) for a finite field of "moderate" characteristic (which is not necessarily a Kummer extension) is the computation of discrete logarithm in a field of 211102350 elements (a 1051-bit finite field);[29] previous record[30] of discrete logarithm computations over such fields was over fields having 29707940 elements (a 728-bitfinite field) and 6437337 elements (a 592-bit finite field). These computations were done using new ideas to speed up the function field sieve.

On 25 June 2014, Razvan Barbulescu, Pierrick Gaudry, Aurore Guillevic, and François Morain announced a new computation of a discrete logarithm in a finite field whose order has 160 digits and is a degree 2 extension of a prime field.[31] The algorithm used was the number field sieve (NFS), with various modifications. The total computing time was equivalent to 68 days on one core of CPU (sieving) and 30 hours on a GPU (linear algebra).

Discrete logarithm records over finite fields!Char.!Field size!Date announced!Announced by!Hardware!Compute!Notes
2230750data-sort-value="2019-07-10" 10 July 2019
  • Robert Granger
  • Thorsten Kleinjung
  • Arjen Lenstra
  • Benjamin Wesolowski
  • Jens Zumbrägel
Intel Xeon architecture25,481,219 core-hoursThis computation was the first large-scale example using the elimination step of the quasi-polynomial algorithm.
21279data-sort-value="2014-10-17" 17 October 2014Thorsten Kleinjung<4 core-years
29234data-sort-value="2014-01-31" 31 January 2014
  • Robert Granger
  • Thorsten Kleinjung
  • Jens Zumbrägel
~400,000 core-hoursNew features of this computation include a modified method for obtaining the logarithms of degree two elements and a systematically optimized descent strategy.
26168data-sort-value="2013-05-21" 21 May 2013Antoine Joux<550 CPU-hours
26120data-sort-value="2013-04-11" 11 April 2013
  • Robert Granger
  • Faruk Göloğlu
  • Gary McGuire
  • Jens Zumbrägel
749.5 core-hours
2809data-sort-value="2013-04-06" 6 April 2013the CARAMEL group
24080data-sort-value="2013-03-22" 22 March 2013Antoine Joux<14,100 core-hours
21971data-sort-value="2013-02-19" 19 February 2013
  • Robert Granger
  • Faruk Göloğlu
  • Gary McGuire
  • Jens Zumbrägel
SGI Altix ICE 8200EX cluster

Intel (Westmere) Xeon E5650 hex-core processors

3,132 core-hours
21778data-sort-value="2013-02-11" 11 February 2013Antoine Joux<220 core-hours
336 · 509data-sort-value="2016-07-18" 18 July 2016
  • Gora Adj
  • Isaac Canales-Martinez
  • Nareli Cruz-Cortés
  • Alfred Menezes
  • Thomaz Oliveira
  • Francisco Rodriguez-Henriquez
  • Luis Rivera-Zamarripa
several computers at CINVESTAV and the University of Waterloo~200 core-years
35 · 479data-sort-value="2014-12-01" December 2014
  • Antoine Joux
  • Cécile Pierrot
<8600 CPU-hours
36 · 163data-sort-value="2014-01-27" 27 January 2014
  • Gora Adj
  • Alfred Menezes
  • Thomaz Oliveira
  • Francisco Rodríguez-Henríquez
1201 CPU-hours
36 · 97data-sort-value="2012-01-01" 2012a joint Fujitsu, NICT, and Kyushu University team
36 · 71
"moderate"p2data-sort-value="2014-06-25" 25 June 2014
  • Razvan Barbulescu
  • Pierrick Gaudry
  • Aurore Guillevic
  • François Morain
68 CPU-days + 30 GPU-hoursThis field is a degree-2 extension of a prime field, where p is a prime with 80 digits.
3334135357data-sort-value="2013-01-06" 6 January 2013
3355377147
37080130data-sort-value="2005-11-09" 9 November 2005
6553725data-sort-value="2005-10-24" 24 October 2005

Elliptic curves

Certicom Corp. has issued a series of Elliptic Curve Cryptography challenges. Level I involves fields of 109-bit and 131-bit sizes. Level II includes 163, 191, 239, 359-bit sizes. All Level II challenges are currently believed to be computationally infeasible.[32]

The Level I challenges which have been met are:[33]

None of the 131-bit (or larger) challenges have been met .

In July 2009, Joppe W. Bos, Marcelo E. Kaihara, Thorsten Kleinjung, Arjen K. Lenstra and Peter L. Montgomery announced that they had carried out a discrete logarithm computation on an elliptic curve (known as secp112r1[34]) modulo a 112-bit prime. The computation was done on a cluster of over 200 PlayStation 3 game consoles over about 6 months. They used the common parallelized version of Pollard rho method.[35]

In April 2014, Erich Wenger and Paul Wolfger from Graz University of Technology solved the discrete logarithm of a 113-bit Koblitz curve in extrapolated 24 days using an 18-core Virtex-6 FPGA cluster.[36] In January 2015, the same researchers solved the discrete logarithm of an elliptic curve defined over a 113-bit binary field. The average runtime is around 82 days using a 10-core Kintex-7 FPGA cluster.[37]

On 2 December 2016, Daniel J. Bernstein, Susanne Engels, Tanja Lange, Ruben Niederhagen, Christof Paar, Peter Schwabe, and Ralf Zimmermann announced the solution of a generic 117.35-bit elliptic curve discrete logarithm problem on a binary curve, using an optimized FPGA implementation of a parallel version of Pollard's rho method. The attack ran for about six months on 64 to 576 FPGAs in parallel.[38]

On 23 August 2017, Takuya Kusaka, Sho Joichi, Ken Ikuta, Md. Al-Amin Khandaker, Yasuyuki Nogami, Satoshi Uehara, Nariyoshi Yamai, and Sylvain Duquesne announced that they had solved a discrete logarithm problem on a 114-bit "pairing-friendly" Barreto–Naehrig (BN) curve,[39] using the special sextic twist property of the BN curve to efficiently carry out the random walk of Pollard's rho method. The implementation used 2000 CPU cores and took about 6 months to solve the problem.[40]

On 16 June 2020, Aleksander Zieniewicz (zielar) and Jean Luc Pons (JeanLucPons) announced the solution of a 114-bit interval elliptic curve discrete logarithm problem on the secp256k1 curve by solving a 114-bit private key in Bitcoin Puzzle Transactions Challenge. To set a new record, they used their own software[41] based on the Pollard Kangaroo on 256x NVIDIA Tesla V100 GPU processor and it took them 13 days. Two weeks earlier - They used the same number of graphics cards to solve a 109-bit interval ECDLP in just 3 days.

Discrete logarithm records for elliptic curves!Curve name!Field size!Date announced!Announced by!Algorithm!Compute time
ECC2K-10821082000about 1300 people represented by Robert HarleyPollard rho method
ECCp-109a 109-bit prime2002about 10308 people represented by Chris Monicoparallelized Pollard rho method549 days
ECC2-10921092004about 2600 people represented by Chris Monicoparallelized Pollard rho method17 months
secp112r1a 112-bit primeJuly 2009 the common parallelized version of Pollard rho method6 months
2113April 2014
  • Erich Wenger
  • Paul Wolfger
47 days
2113January 2015
  • Erich Wenger
  • Paul Wolfger
82 days
2127Interval search size 2117.352 December 2016 parallel version of Pollard's rho method6 months of 64 to 576 FPGAs
23 August 2017
  • Takuya Kusaka
  • Sho Joichi
  • Ken Ikuta
  • Md. Al-Amin Khandaker
  • Yasuyuki Nogami
  • Satoshi Uehara
  • Nariyoshi Yamai
  • Sylvain Duquesne
secp256k12256 Interval search size 211416 August 2020
  • Aleksander Zieniewicz
  • Jean Luc Pons
parallel version of Pollard's rho method13 Days on 256xTesla V100

External links

Notes and References

  1. Emmanuel Thomé, “795-bit factoring and discrete logarithms,” December 2, 2019.
  2. F. Boudot et al, "Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment," June 10, 2020.
  3. Thorsten Kleinjung, “Discrete logarithms in GF(p) – 768 bits,” June 16, 2016.
  4. Antoine Joux, “Discrete logarithms in GF(p) – 130 digits,” June 18, 2005.
  5. Thorsten Kleinjung, “Discrete logarithms in GF(p) – 160 digits,” February 5, 2007.
  6. Cyril Bouvier, Pierrick Gaudry, Laurent Imbert, Hamza Jeljeli and EmmanuelThomé, "Discrete logarithms in GF(p) – 180 digits"
  7. Joshua Fried, Pierrick Gaudry, Nadia Heninger, Emmanuel Thome, “A kilobit hidden snfs discrete logarithm computation”, IACR spring, July 2016
  8. Jens Zumbrägel, "Discrete Logarithms in GF(2^30750)", 10 July 2019, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;62ab27f0.1907.
  9. R. Granger, T. Kleinjung, J. Zumbragel. On the discrete logarithm problem in finite fields of fixed characteristic. Trans. Amer. Math.Soc. 370, no. 5 (2018), pp. 3129-3145.
  10. Jens Zumbrägel, "Discrete Logarithms in GF(2^9234)", 31 January 2014, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;9aa2b043.1401.
  11. Antoine Joux, "Discrete logarithms in GF(26168) [=GF((2<sup>257</sup>)<sup>24</sup>)]", May 21, 2013, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1305&L=NMBRTHRY&F=&S=&P=3034.
  12. Antoine Joux. A new index calculus algorithm with complexity $L(1/4+o(1))$ in very small characteristic, 2013, http://eprint.iacr.org/2013/095
  13. Antoine Joux, "Discrete logarithms in GF(24080)", Mar 22, 2013, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1303&L=NMBRTHRY&F=&S=&P=13682.
  14. Faruk Gologlu et al., On the Function Field Sieve and the Impact of Higher Splitting Probabilities: Application to Discrete Logarithms in
    F
    21971
    , 2013, http://eprint.iacr.org/2013/074.
  15. Antoine Joux, "Discrete logarithms in GF(21778)", Feb. 11, 2013, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1302&L=NMBRTHRY&F=&S=&P=2317.
  16. Granger, Robert, Thorsten Kleinjung, and Jens Zumbrägel. “Breaking `128-Bit Secure’ Supersingular Binary Curves (or How to Solve Discrete Logarithms in
    {F}
    24
    and
    {F}
    212
    ).” arXiv:1402.3668 [cs, Math], February 15, 2014. https://arxiv.org/abs/1402.3668.
  17. Thorsten Kleinjung, 2014 October 17, "Discrete Logarithms in GF(2^1279)", https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;256db68e.1410.
  18. The CARAMEL group: Razvan Barbulescu and Cyril Bouvier and Jérémie Detrey and Pierrick Gaudry and Hamza Jeljeli and Emmanuel Thomé and Marion Videau and Paul Zimmermann, “Discrete logarithm in GF(2809) with FFS”, April 6, 2013, http://eprint.iacr.org/2013/197.
  19. Francisco Rodriguez-Henriquez, 18 July 2016, "Discrete Logarithms in GF(3^)", https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;65bedfc8.1607.
  20. Web site: Joux. Antoine. Pierrot. Cécile. Improving the Polynomial time Precomputation of Frobenius Representation Discrete Logarithm Algorithms. dead. https://web.archive.org/web/20141211051755/http://www-polsys.lip6.fr/~pierrot/papers/Simplified%20Frob%20Rep.pdf. 2014-12-11. 2014-12-11.
  21. Francisco Rodríguez-Henríquez, “Announcement,” 27 January 2014, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;763a9e76.1401.
  22. Gora Adj and Alfred Menezes and Thomaz Oliveira and Francisco Rodríguez-Henríquez, "Computing Discrete Logarithms in F_ and F_ using Magma", 26 Feb 2014, http://eprint.iacr.org/2014/057.
  23. Kyushu University, NICT and Fujitsu Laboratories Achieve World Record Cryptanalysis of Next-Generation Cryptography, 2012, http://www.nict.go.jp/en/press/2012/06/PDF-att/20120618en.pdf.
  24. Takuya Hayashi et al., Solving a 676-bit Discrete Logarithm Problem in GF(36n), 2010, http://eprint.iacr.org/2010/090.
  25. A. Durand, “New records in computations over large numbers,” The Security Newsletter, January 2005, http://eric-diehl.com/letter/Newsletter1_Final.pdf .
  26. Antoine Joux, “Discrete Logarithms in a 1425-bit Finite Field,” January 6, 2013, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1301&L=NMBRTHRY&F=&S=&P=2214.
  27. Faster index calculus for the medium prime case. Application to 1175-bit and 1425-bit finite fields, Eprint Archive, http://eprint.iacr.org/2012/720
  28. Antoine Joux, “Discrete Logarithms in a 1175-bit Finite Field,” December 24, 2012, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1212&L=NMBRTHRY&F=&S=&P=13902.
  29. Mukhopadhyay. Madhurima. Sarkar. Palash. Singh. Shashank. Thomé. Emmanuel. New discrete logarithm computation for the medium prime case using the function field sieve. Advances in Mathematics of Communications. 2022. 16 . 3 . 449 . 10.3934/amc.2020119.
  30. Sarkar. Palash. Singh. Shashank. Fine Tuning the Function Field Sieve Algorithm for the Medium Prime Case. IEEE Transactions on Information Theory. 2016. 62 . 4 . 2233–2253 . 10.1109/TIT.2016.2528996.
  31. Razvan Barbulescu, “Discrete logarithms in GF(p^2) --- 160 digits,” June 24, 2014, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;2ddabd4c.1406.
  32. Certicom Corp., “The Certicom ECC Challenge,” https://www.certicom.com/content/certicom/en/the-certicom-ecc-challenge.html
  33. Certicom Research, Certicom ECC Challenge (Certicom Research, November 10, 2009), Web site: Archived copy . 2010-12-30 . dead . https://web.archive.org/web/20151022135946/https://www.certicom.com/images/pdfs/challenge-2009.pdf . 2015-10-22 . .
  34. Certicom Research, "SEC 2: Recommended Elliptic Curve Domain Parameters" https://www.secg.org/SEC2-Ver-1.0.pdf
  35. Joppe W. Bos and Marcelo E. Kaihara, “PlayStation 3 computing breaks 2^60 barrier: 112-bit prime ECDLP solved,” EPFL Laboratory for cryptologic algorithms - LACAL, http://lacal.epfl.ch/112bit_prime
  36. Erich Wenger and Paul Wolfger, “Solving the Discrete Logarithm of a 113-bit Koblitz Curve with an FPGA Cluster” http://eprint.iacr.org/2014/368
  37. Erich Wenger and Paul Wolfger, “Harder, Better, Faster, Stronger - Elliptic Curve Discrete Logarithm Computations on FPGAs” http://eprint.iacr.org/2015/143/
  38. Ruben Niederhagen, “117.35-Bit ECDLP on Binary Curve,” https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;628a3b51.1612
  39. Web site: 23 August 2017. 114-bit ECDLP on a BN curve has been solved. dead. https://web.archive.org/web/20180527201520/http://isec.ec.okayama-u.ac.jp/whats-new/114-bit-ecdlp-has-been-solved/. 27 May 2018. isec.ec.okayama-u.ac.jp. 2018-05-03.
  40. Solving 114-Bit ECDLP for a Barreto–Naehrig Curve. Kusaka . Takuya . Joichi . Sho . Ken. Ikuta. Md. Al-Amin . Khandaker. Yasuyuki. Nogami. Satoshi. Uehara. Nariyoshi . Yamai. Sylvain. Duquesne. Lecture Notes in Computer Science . 2018 . 10779 . Springer. Information Security and Cryptology – ICISC 2017 . 231–244. 10.1007/978-3-319-78556-1_13. 978-3-319-78555-4 .
  41. Web site: Pollard's kangaroo for SECPK1 . Jean-Luc . Pons . Aleksander . Zieniewicz . . 17 January 2022 .