Discrete Logarithm Challenges and Records

kodlu

5/13/24, 10:34 PM

I am wondering whether there are any current challenge problems for Discrete Logarithms.

Specifically in $\mathbb{Z}_p^\ast$ as well as in elliptic curve groups.

It turns out CERTICOM still has some ECC challenges, and it seems 131 bits is the smallest unsolved case. See the link here.

One concern I have is that given the 109 bit challenge was solved in 2004, is it the case that 131 bits is still out of reach, or have people simply not been trying?

I suppose this question could also be restated (ignoring specific ECC details) as follows:

What is the longest bitlength that a generic discrete logarithm solution has been found for? I am thinking Baby Step Giant Step (but memory would be a problem) so maybe think of Pollard rho.

I am aware of the special exponent and small ground field breakthroughs, see for example the question here but this question is not about them.

299

1 + 1

discrete-logarithm

number-theory

prime-numbers

Daniel S

5/14/24, 6:37 AM

Sect113r1 was broken in 2016 and also a curve with a 118- bit order over $\mathbb F_{127}$ [see the paper by Bernstein et al](https://eprint.iacr.org/2016/382.pdf), though the 118-bit problem takes advantage of an automorphism structure that is not generically available. See also [this paper by Bos et al](https://www.joppebos.com/files/noan112.pdf) for prime fields.

Score:5

Crypto

Wilson

5/14/24, 12:04 AM

For discrete log over $\mathbb{Z}_p^{*}$, as of 2019, a discrete logarithm was computed over a 795 bit safe prime [1].

In practice, no one uses generic discrete logarithm algorithms (such as pollard rho or baby step giant step) against the DLP over $\mathbb{Z}_p^*$, because there are more efficient algorithms (index calculus attacks or variants of the Number Field Sieve) that can leverage the structure of the integers. Here's a reference on attacks on discrete logs [2] if you want to dive deeper.

[1] https://dldb.loria.fr/?filter=ext&value=1&sort=date, https://eprint.iacr.org/2020/697.pdf, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;fd743373.1912

[2] https://www.math.auckland.ac.nz/~sgal018/crypto-book/ch15.pdf

+ 2

kodlu

5/14/24, 1:56 AM

Thanks, presumably this subexponential improvement doesn't exist for elliptic curve discrete logarithm.

Wilson

5/14/24, 2:57 PM

Yes, it looks like generic attacks are asymptotically the best for ECDLP. If the curve has more structure such as if the base field is a high degree extension field or it's a pairing friendly curve, then it looks like there are some options from this answer https://crypto.stackexchange.com/questions/52655/what-are-the-fastest-attacks-on-ecdlp.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Discrete Logarithm Challenges and Records

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.