Discrete logarithm records

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 g^x = 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 modulo p or over a finite field.

Integers modulo p

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]

Finite fields

The current record (as of 2010) in a finite field of characteristic 2 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 2⁶¹³ elements. The computation took 17 days on four 16-processor (1.3 GHz) nodes of the Itanium 2-based Bull computer Teranova.^[3]

The current record (as of 2010) for a field of characteristic 3 was announced by Takuya Hayashi et al., who computed a discrete logarithm in the field of 3^6 · 71 elements, using a variation on the function field sieve. ^[4] This also holds the record for the computation over the largest field (676 bits) of any type.

Over fields of "moderate"-sized characteristic, notable computations as of 2005 included those a field of 65537²⁵ elements (401 bits) announced on 24 Oct 2005, and in a field of 370801³⁰ elements (556 bits) announced on 9 Nov 2005.^[5]

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.^[6]

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

• ECC2K-108, involving taking a discrete logarithm on a Koblitz curve over a field of 2¹⁰⁸ 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 2¹⁰⁹ 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.^[8]

References

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. ^ Antoine Joux, “Discrete logarithms in GF(2⁶⁰⁷) and GF(2⁶¹³),” September 23, 2005, http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0509&L=NMBRTHRY&P=R1490&D=0&I=-3&T=0.
4. ^ Takuya Hayashi et al., Solving a 676-bit Discrete Logarithm Problem in GF(3^{6n), 2010, http://eprint.iacr.org/2010/090.}
5. ^{^ A. Durand, “New records in computations over large numbers,” The Security Newsletter, January 2005, http://eric-diehl.com/letter/Newsletter1_Final.pdf.}
6. ^{^ Certicom Corp., “The Certicom ECC Challenge,” http://www.certicom.com/index.php/the-certicom-ecc-challenge.}
7. ^{^ Certicom Research, Certicom ECC Challenge (Certicom Research, November 10, 2009), http://www.certicom.com/images/pdfs/challenge-2009.pdf.}
8. ^{^ 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}