Discrete logarithm records

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 analogs 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.

Integers modulo p[edit]

On 18 Jun 2005, Antoine Joux and Reynald Lercier announced the computation of a discrete logarithm modulo a 130-digit (431-bit) strong prime in three weeks, using a 1.15 GHz 16-processor HP AlphaServer GS1280 computer and a number field sieve algorithm.[1]

On 5 Feb 2007 this was superseded by the announcement by Thorsten Kleinjung of the computation of a discrete logarithm modulo a 160-digit (530-bit) safe prime, again using the number field sieve. Most of the computation was done using idle time on various PCs and on a parallel computing cluster.[2]

On 11 Jun 2014, Cyril Bouvier, Pierrick Gaudry, Laurent Imbert, Hamza Jeljeli and Emmanuel Thomé announced the computation of a discrete logarithm modulo a 180 digit (596-bit) safe prime using the number field sieve algorithm.[3]

Finite fields[edit]

The current record (as of January 2014) in a finite field of characteristic 2 was announced by Robert Granger, Thorsten Kleinjung, and Jens Zumbrägel on 31 January 2014. This team was able to compute discrete logarithms in GF(29234) using about 400,000 core hours. New features of this computation include a modified method for obtaining the logarithms of degree two elements and a systematically optimized descent strategy.[4]

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

  • Antoine Joux on 21 May 2013. His team was able to compute discrete logarithms in the field with 26168 = (2257)24 elements using less than 550 CPU-hours. This computation was performed using the same index calculus algorithm as in the recent computation in the field with 24080 elements.[5]
  • Robert Granger, Faruk Göloğlu, Gary McGuire, and Jens Zumbragel on 11 Apr 2013. The new computation concerned the field with 26120 elements and took 749.5 core-hours.
  • Antoine Joux on Mar 22nd, 2013. This used the same algorithm [6] for small characteristic fields as the previous computation in the field with 21778 elements. The new computation concerned the field with 24080 elements, represented as a degree 255 extension of the field with 216 elements. The computation took less than 14100 core hours.[7]
  • Robert Granger, Faruk Göloğlu, Gary McGuire, and Jens Zumbragel on 19 Feb 2013. They used a new variant of the medium-sized base field function field sieve, for binary fields, to compute a discrete logarithm in a field of 21971 elements. In order to use a medium-sized base field, they represented the field as a degree 73 extension of the field of 227 elements. The computation took 3132 core hours on an SGI Altix ICE 8200EX cluster using Intel (Westmere) Xeon E5650 hex-core processors.[8]
  • Antoine Joux on 11 Feb 2013. This used a new algorithm for small characteristic fields. The computation concerned a field of 21778 elements, represented as a degree 127 extension of the field with 214 elements. The computation took less than 220 core hours.[9]

The current record (as of 2013) 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.[10] The previous record in a finite field of characteristic 2 of prime degree was announced by Antoine Joux and Reynald Lercier on 23 Sep 2005. They used the function field sieve to compute a discrete logarithm in a field of 2613 elements. The computation took 17 days on four 16-processor (1.3 GHz) nodes of the Itanium 2-based Bull computer Teranova.[11]

The current record (as of 2014) for a field of characteristic 3 was announced by Gora Adj, Alfred Menezes, Thomaz Oliveira, and Francisco Rodríguez-Henríquez on 26 February 2014, updating a previous announcement on 27 January 2014. The computation used Joux's algorithm to compute discrete logarithms in the 1551-bit field GF(36 · 163), taking 1201 CPU hours. This work did not exploit any "special" aspects of the field such as Kummer or twisted-Kummer properties.[12][13] The previous record was announced in 2012 by a joint Fujitsu, NICT, and Kyushu University team, that computed a discrete logarithm in the field of 36 · 97 elements and a size of 923 bits,[14] using a variation on the function field sieve and beating the previous record in a field of 36 · 71 elements and size of 676 bits [15] by a wide margin.

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.[16] The current record (as of 2013) for a 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 field of 3334135357 elements (a 1425-bit finite field).[17][18] The same technique had been used a few weeks earlier to compute a discrete logarithm in a field of 3355377147 elements (an 1175-bit finite field).[18][19]

On 25 June 2014, Razvan Barbulescu, Pierrick Gaudry, Aurore Guillevic, and François Morain announced a 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.[20] 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).

Elliptic curves[edit]

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.[21]

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

  • ECC2K-108, involving taking a discrete logarithm on a Koblitz curve over a field of 2108 elements. The prize was awarded on 4 April 2000 to a group of about 1300 people represented by Robert Harley. They used a parallelized Pollard rho method with speedup.
  • ECC2-109, involving taking a discrete logarithm on a curve over a field of 2109 elements. The prize was awarded on 8 April 2004 to a group of about 2600 people represented by Chris Monico. They also used a version of a parallelized Pollard rho method, taking 17 months of calendar time.
  • ECCp-109, involving taking a discrete logarithm on a curve modulo a 109-bit prime. The prize was awarded on 15 Apr 2002 to a group of about 10308 people represented by Chris Monico. Once again, they used a version of a parallelized Pollard rho method method, taking 549 days of calendar time.

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

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 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.[23]

In April 2014, Erich Wenger and Paul Wolfger from Graz University of Technology solved the discrete logarithm of an 113-bit Koblitz curve in extrapolated 24 days using an 18-core Virtex-6 FPGA cluster.[24]

References[edit]

  1. ^ Antoine Joux, “Discrete logarithms in GF(p) – 130 digits,” June 18, 2005, http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0506&L=nmbrthry&T=0&P=20.
  2. ^ Thorsten Kleinjung, “Discrete logarithms in GF(p) – 160 digits,” February 5, 2007, http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0702&L=NMBRTHRY&P=R45&D=0&I=-3&T=0.
  3. ^ Cyril Bouvier, Pierrick Gaudry, Laurent Imbert, Hamza Jeljeli and Emmanuel Thomé, "Discrete logarithms in GF(p) – 180 digits" https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1406&L=NMBRTHRY&F=&S=&P=3161
  4. ^ Jens Zumbrägel, "Discrete Logarithms in GF(2^9234)", 31 January 2014, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;9aa2b043.1401.
  5. ^ Antoine Joux, "Discrete logarithms in GF(26168) [=GF((2257)24)]", May 21, 2013, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1305&L=NMBRTHRY&F=&S=&P=3034.
  6. ^ 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
  7. ^ 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.
  8. ^ Faruk Gologlu et al., On the Function Field Sieve and the Impact of Higher Splitting Probabilities: Application to Discrete Logarithms in \mathbb{F}_{2^{1971}}, 2013, http://eprint.iacr.org/2013/074.
  9. ^ 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.
  10. ^ 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.
  11. ^ Antoine Joux, “Discrete logarithms in GF(2607) and GF(2613),” September 23, 2005, http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0509&L=NMBRTHRY&P=R1490&D=0&I=-3&T=0.
  12. ^ Francisco Rodríguez-Henríquez, “Announcement,” 27 January 2014, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;763a9e76.1401.
  13. ^ Gora Adj and Alfred Menezes and Thomaz Oliveira and Francisco Rodríguez-Henríquez, "Computing Discrete Logarithms in F_{3^{6*137}} and F_{3^{6*163}} using Magma", 26 Feb 2014, http://eprint.iacr.org/2014/057.
  14. ^ 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.
  15. ^ Takuya Hayashi et al., Solving a 676-bit Discrete Logarithm Problem in GF(36n), 2010, http://eprint.iacr.org/2010/090.
  16. ^ A. Durand, “New records in computations over large numbers,” The Security Newsletter, January 2005, http://eric-diehl.com/letter/Newsletter1_Final.pdf.
  17. ^ 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.
  18. ^ a b 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
  19. ^ 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.
  20. ^ 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.
  21. ^ Certicom Corp., “The Certicom ECC Challenge,” http://www.certicom.com/index.php/the-certicom-ecc-challenge.
  22. ^ Certicom Research, Certicom ECC Challenge (Certicom Research, November 10, 2009), http://www.certicom.com/images/pdfs/challenge-2009.pdf.
  23. ^ 1. 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
  24. ^ 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