4
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ 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, though the 118-bit problem takes advantage of an automorphism structure that is not generically available. See also this paper by Bos et al for prime fields. $\endgroup$
    – Daniel S
    May 14 at 6:37

1 Answer 1

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks, presumably this subexponential improvement doesn't exist for elliptic curve discrete logarithm. $\endgroup$
    – kodlu
    May 14 at 1:56
  • 1
    $\begingroup$ 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 crypto.stackexchange.com/questions/52655/…. $\endgroup$
    – Wilson
    May 14 at 14:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.