3
$\begingroup$

Given the normal discrete logarithm problem:

$$a = b^c \mod{P}$$

with prime $P$ and numbers $a,b,c$

For which kind of $P,b$ the NFS/IC algorithm is faster than Baby-Step/Giant-Step+ Pollard's Rho ($\approx \mathcal{O}(\sqrt{q}) $)?

(with $q$ the biggest prime in factorization of $P-1$, with $P$ big prime)

Or in which cases NFS/IC it used?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
3
$\begingroup$

Using its notation, the question is about the difficulty of the Discrete Logarithm Problem in a Schnorr Group modulo $P$, of prime order $q$. I'll assume $b^q\bmod P=1$ and $b\bmod P\ne1$.

That DLP problem is finding $c$ chosen at random in $[0,q)$ given $P$, $q$, $b$, and $a$ obtained as $b^c\bmod P$. Depending on parameters, the best known algorithms fall into two complexity classes:

  • somewhere between $\mathcal O(\sqrt{q}\,\ln P\,\ln\ln P)$ [in theory] and $\mathcal O(\sqrt{q}\,\ln^2 P)$ for Baby-Step/Giant-Step and it's practical improvement: Pollard's Rho with distinguished points (which can be efficiently distributed and requires little memory; see Paul C. van Oorschot and Michael J. Wiener, Parallel Collision Search with Cryptanalytic Applications, in Journal of Cryptology, 1999). The cost is often stated as $\mathcal O(\sqrt{q})$ multiplications of integers of size $P$, and this has been recently shown to cost $\mathcal O(\ln P\,\ln\ln P)$, see this.

  • something like $\exp\left( \left(\sqrt[3]{\frac{64}{9}} + o(1)\right)(\ln P)^{\frac{1}{3}}(\ln \ln P)^{\frac{2}{3}}\right)$, for the Number Field Sieve applied to the Discrete Logarithm (see this).

in which cases is NFS/Index Calculus used?

For a given size of $q$, the first class of algorithms (Pollard's Rho..) is best for large $P$. The second (NFS) is faster for relatively small $P$, including $q$ a Sophie Germain prime (equivalently, $P$ a safe prime).

For 256‑bit $q$, the first class of algorithm is better for 8192-bit $P$, the second for 512‑bit $P$. I prefer not digging where exactly the crossover is, or what's the exact difference between NFS and IC.

Improve this answer
$\endgroup$
4
  • $\begingroup$ ty. So given the Schnorr Group $P = r \cdot q+1$ with $q$ a prime would that mean that NFS is used if the subgroup used is much smaller than $P$? In your $256$-bit-$q$ example the other factor $r$ need to be much bigger than $q$. What would be a use case of this? Wouldn't be $256$-bit safe enough? As safe as a $256$-bit EC? $\endgroup$
    – J. Doe
    Commented Mar 5, 2021 at 16:50
  • 1
    $\begingroup$ @J. Doe: You are correct. With large-enough $P$, 256-bit $q$ is as safe as 256-bit ECC. In fact, Schnoor signature then DSA did just that, before ECDSA and EdDSA. $\endgroup$
    – fgrieu ♦
    Commented Mar 5, 2021 at 16:57
  • $\begingroup$ Do you have a reference or a name for the $\mathcal{O}(\sqrt{q}\ln P \ln \ln P)$ algortihm? $\endgroup$
    – Aman Grewal
    Commented Mar 5, 2021 at 17:13
  • 1
    $\begingroup$ @fgrieu so as final conclusion (related to other question ) using a Sophie Germain 256-bit prime in normal discrete logarithm is not as safe as in EC with similar order but not a small embedding. right? $\endgroup$
    – J. Doe
    Commented Mar 5, 2021 at 18:00
1
$\begingroup$

The exact cost of the number field sieve algorithm is somewhat fuzzy (the usually quoted complexity is only valid in a log-asymptotic sense). Lenstra and Verheul tried to capture a more usable version of the complexity which has been broadly accepted. For parameter sets of interest the related estimates published by NIST would probably be generally agreed on:

80-bits work: 160-bit $q$, 1024-bit $P$

112-bits work: 224-bit $q$, 2048-bit $P$

128-bits work: 256-bit $q$, 3072-bit $P$

192-bits work: 384-bit $q$, 7680-bit $P$

256-bits work: 512-bit $q$, 15360-bit $P$

Improve this answer
$\endgroup$
2
  • $\begingroup$ Given that order at which position would be 511-bit $q$ with 512-bit $P$ or 255-bit $q$ with 256-bit $P$? $\endgroup$
    – J. Doe
    Commented Mar 5, 2021 at 22:28
  • 1
    $\begingroup$ For 512-bit $P$ we can quote actual performance figures. The Logjam attack (en.wikipedia.org/wiki/Logjam_(computer_security)) was able to use the number field sieve to break such a system with a few thousand core weeks. 256-bit $P$ would be even more insecure. $\endgroup$
    – Daniel S
    Commented Mar 5, 2021 at 22:43

Your Answer

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

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