2
$\begingroup$

We consider the Discrete Logarithm Problem of finding integer $x$ random in $[0,n)$ where $n$ is the group order, given $Y=G^x$ (or $Y=xG$) computed in the group noted multiplicatively (or additively), group generator $G$, and the prime order $n$.

I ask how the cost of solving $k$ such problems with shared group and $G$, compares the cost of solving one such problem, according to:

  • The kind of group, e.g. multiplicative group modulo a safe prime $p$; or elliptic curve group; or a completely generic group.
  • Should that matter, whether the $k$ values of $Y_j$ are all given initially, or $Y_j$ is given for $j=0$ and after $x_{j-1}$ has been found for $j>0$.

Note: that cost for $k$ problems is somewhat between $1$ and $k$ times the cost for one.

In particular, I wonder what percentage of computations in GNFS can be shared across multiple instances sharing the same prime and generator.

This has applications, e.g. choice of group in DH key exchange.

$\endgroup$
2
  • $\begingroup$ Well, to be honest, if it reduces the complexity, then give me your single discrete log problem, and then I can create as many other problems ( that I've already known the solution to but am ignoring) after that I can solve your discrete log problem in reduced complexity. So, there must a great breakthrough in solving Dlog. $\endgroup$
    – kelalaka
    Dec 16, 2023 at 15:09
  • $\begingroup$ @kelalaka: Following your comment, I have edited the question to state that the cost for $k$ problems is at least the cost for one, and at most $k$ times that. Your line of thought is interesting. It proves that we can't hope to solve one problem out of $k$ with sizably less effort that solving one problem. But I don't think it can be used to prove that the cost of $k$ problems is $k$ times the cost for one, even for optimal method. At least, that's false for some methods. $\endgroup$
    – fgrieu
    Dec 16, 2023 at 15:20

2 Answers 2

5
$\begingroup$

There are two main cases to address here.

One is the generic "black box methods" which apply to elliptic curves. With these, the cost to solve one discrete logarithm is $O(n^{1/2+\epsilon})$, but to solve $k$ instances the cost is $O((kn)^{1/2+\epsilon})$. The easiest demonstration is a memory intensive baby-steps/giant-steps, though other methods also work. If I know that I have to compute $k$ instances, I can set $b=[\sqrt{n/k}]+1$ and run a one-time pre-computation of powers $bG, 2bG,\ldots,[\sqrt{kn}]bG$ with $O(\sqrt{kn})$ group operations. I sort and store this list. For each instance of a discrete logarithm problem $Y_j$, I can then compute $Y_j, Y_j-G, Y_j-2G,\ldots, Y_j-(b-1)G$ and search for a match in my table. There will be precisely one match in each table, for we can write $x_j=q_jb+r$ with $0\le r<b$ and $q<[\sqrt{kn}]+1$ in exactly one way. The individual instances each require $O(\sqrt{n/k})$ group operations and there are $k$ instances. Thus the precomputation and the sum of the individual steps both come to $O((kn)^{1/2+\epsilon})$ work (the $\epsilon$ covers sort and search costs). Note the individual problems can be presented serially, but I need to know $k$ in advance to optimise.

The other case is the GNFS case when attacking a multiplicative group mod $p$. Here a good study is the LOGJAM vulnerability and the attendant paper Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice by Adrian et al. They note that the GNFS attack on discrete logarithms can be divided into a one-time precomputation and a many-time "descent" step. The one-time precomputation has the usual GNFS complexity $L_p[1/3,\root3\of{64/9}\approx 1.923]$ independent of the value of $k$. They quote a figure of $L_p[1/3,1.232]$ for the descent step (again independent of $k$) based on work by Barbulescu in his thesis. Thus for $k\approx L_p[1/3,0.691]$ the cost to solve $k$ discrete logarithms is not significantly greater than the solution of a single instance. The LOGJAM authors were able to show that this separation between the one-time precomputation and the descent permitted an effective attack for 512-bit primes.

$\endgroup$
3
$\begingroup$

I think the other provides an excellent overview of the classical algorithmic side. Let me add some other perspectives.

  1. There are corresponding lower bounds in the generic group model. Namely, in the generic group model (GGM)*, we need to perform $\Omega(\sqrt{k|G|})$ group operations to solve all the $k$ instances of the discrete logarithm problems in the same group $G$ (proven by Yun in this paper). This can be extended to the $k$-out-of-$m$ case with the same complexity of $\Omega(\sqrt{k|G|})$ in the GGM, where we are given $m$ DL instances and want to solve at least $k$ of them (by Auerbach, Giacon, and Kiltz in this paper). In fact, this bound holds even when the oracle access to the CDH solver is given. As a side note, there was an interesting history for $1$-out-of-$m$ DL lower bound itself; see this question in CryptoStrackexchange.
  1. In the quantum case, Yamakawa, Yun, and I found a slight speed-up over Shor's algorithm in the multiple DL problem in this paper (along with the quantum GGM lower bound of DL). Roughly speaking, the overall complexity is proportional to $m/\log m$ for $m$ instances, resulting in $1/\log m$ speed-up.

(*) The generic group model is an abstract model for analyzing the group-theoretic algorithms where the algorithm only performs generic operations on the group elements, e.g., the group operation or the equality check of group elements. This model focuses on the group itself and excludes the method stemming from the representation; for example, the integer DL $g^x = y \bmod N$ has non-generic algorithms such as index calculus. To my knowledge, we do not know a non-generic method for solving the elliptic curve DL, and the best algorithms are generic.

$\endgroup$
4
  • $\begingroup$ Is a lower bound of $\Omega(\sqrt{G})$ group operations known in the single DL case? $\endgroup$
    – kodlu
    Dec 17, 2023 at 2:59
  • 1
    $\begingroup$ @kodlu Oh, only in the generic group model. I added the GGM descriptions. $\endgroup$
    – Hhan
    Dec 17, 2023 at 4:06
  • $\begingroup$ Of course, that's what I meant $\endgroup$
    – kodlu
    Dec 17, 2023 at 6:04
  • $\begingroup$ The single DL lower bound was proven by Nechaev in the deterministic case and by Shoup in a more general setting. $\endgroup$ Dec 17, 2023 at 6:30

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.