6
$\begingroup$

This recent paper shows that discrete logarithms are solvable if you have an oracle for the Diffie–Hellman problem. However, to me, it seems there is a much simpler reduction and I wonder where I am wrong:

Core idea: A DH oracle allows us to exploit the multiplicative structure of a curve's scalar field, whereas normally, we can work only on its additive structure.

You can use a DH oracle to compute exponentiations in the hidden exponent. For any $xG$ you can compute $(x^t)G$ for any $t$, simply by applying the exponentiation by squaring method.

This allows us to apply the Pollig-Hellman algorithm in the exponent. If the curve order is prime $q$ and $q-1 = q_1 \cdot ... \cdot q_k$, then $x_i = x^{\frac{q-1}{q_i}}$ is an element of multiplicative order $q_i$ in the scalar field $\mathbb{F}_q$. Thus, breaking $x_iG$ can be done in $\mathcal{O}(\sqrt{q_i})$ using, e.g., the baby-step giant-step algorithm.

Let's define $q_1 \geq ... \geq q_k$. Then this method reduces the hardness of discrete logarithms to $\mathcal{O}(\sqrt{q_1})$. For example, in the case of secp256k1 this would reduce the security to about 54 bits.

What's wrong with that idea?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Clarification: the question's $q$ is the prime order of $G$ (usually noted $n$ in sec1 and secp256k1). The DLog problem is solving for scalar $x$ the equation $x\,G=X$ for given $X$. Indeed the DH oracle allows to compute $x^t\,G=X^t$ for any $t$. But for now I fail to get how that allows an attack related to Pohlig–Hellman for smooth $q-1$. $\endgroup$
    – fgrieu ♦
    Commented Apr 18, 2023 at 16:22
  • 1
    $\begingroup$ Looks like I jumped over too many steps: Suppose $q - 1 = q_1 \cdot ... \cdot q_k$ and we have generators $g_1, ... , g_k$ of the simple multiplicative subgroups of $\mathbb{F}_q$. The oracle allows us to decompose $xG$ into $xG=g_1^{x_1}G + ...+ g_k^{x_k}G$. E.g. using $t = \frac{q-1}{q_1}$ then $x^tG = g_1^{x_1}G$. We can break any point $P_i = g_i^{x_i}G$ by finding $x_i$ by iteratively multiplying $g_i$ to $P_i$. $\endgroup$
    – RobinLinus
    Commented Apr 18, 2023 at 16:30
  • 1
    $\begingroup$ For any set of generators $g_i$, any $x\in \mathbb{F}_q$ can be decomposed into a distinct set of $x_i$ that satisfy $x = \sum g_i^{x_i}$. It is similar to integer factorization, just that you factor into powers of generators of simple subgroups. $\endgroup$
    – RobinLinus
    Commented Apr 18, 2023 at 17:02
  • 1
    $\begingroup$ If I get you correctly, with $t_i=(q-1)/{q_i}$, you assert that if $x^{t_i}\equiv{g_i}^{x_i}\pmod q$ then $x\equiv\sum g_i^{x_i}\pmod q$. Then I get the rest: we can indeed compute $x^{t_i}G$ with the DH oracle, and it holds ${g_i}^{x_i}G=({g_i}G)^{x_i}$, thus we can find the $x_i$ by enumeration, BS/GS or better, and the $x_i$ yield $x$. I'll think about that assertion. $\endgroup$
    – fgrieu ♦
    Commented Apr 18, 2023 at 17:24
  • $\begingroup$ @fgrieu yes, that's what I meant. $\endgroup$
    – RobinLinus
    Commented Apr 18, 2023 at 17:49

1 Answer 1

Reset to default
5
$\begingroup$

You are essentially describing the reduction by den Boer. It works fine (i.e., your idea works), but it has the disadvantage that the runtime essentially depends on the prime factorization of $q-1$. If that one is not sufficiently smooth, you won't get into a practically feasible regime.

For example, the largest factor of $q-1$ for the SM2 curve has 197 bit. Even with BSGS (which requires additional memory) or Pollard's Rho, this subgroup would be infeasible to solve (even without considering the number of oracle calls).

With the reduction by Maurer — the one used in the paper — you are using an elliptic curve instead of $\mathbb{F}^*_q$ as the auxiliary group. This makes you independent of the prime factorization of $q-1$, as long as you find a sufficiently smooth auxiliary curve to become feasible. These auxiliary curve parameters are provided in the paper, as well.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Was my algorithm for elliptic curves ever described in the literature? It seems relevant, because, e.g., for secp256k1 the scalar field's multiplicative order, $q-1$, is sufficiently smooth to significantly reduce the curve's security under the assumption of a DH oracle. And for secp256r1 it's even more smooth. Even ed25519 suffers from a relevant reduction in security. Additionally, applying index calculus might weaken it further. $\endgroup$
    – RobinLinus
    Commented Apr 18, 2023 at 17:51
  • 1
    $\begingroup$ This paper is mentioned in the related works and uses notation with an additive base group (i.e., applied to curve standards). But note that if you're "lucky", and a sufficiently smooth number is within the Hasse interval of $q$, you can get a better reduction with Maurer's approach, as it uses less oracle calls. Regarding Index Calculus: Keep in mind that you need to be able to use the algorithm implicitly. I can't really tell whether Index Calculus would translate easily into that setting. $\endgroup$
    – CRTified
    Commented Apr 18, 2023 at 20:46
  • $\begingroup$ Actually, the first steps of the computation translate quite nicely, as the field can be fully "analyzed" in the plain setting and then only the result needs to be transformed to break dlogs in the implicit setting. However, the last step involves factoring, which translates poorly to the implicit setting, I suppose. $\endgroup$
    – RobinLinus
    Commented Apr 18, 2023 at 21:19

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.