Score:6

Crypto

What's wrong with this simple reduction of discrete logarithms to the Diffie-Hellman problem?

RobinLinus

4/18/24, 1:38 PM

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?

475

1 + 5

discrete-logarithm

diffie-hellman

hardness-assumptions

fgrieu

4/18/24, 4:22 PM

Clarification: the question's $q$ is the prime order of $G$ (usually noted $n$ in [sec1](https://www.secg.org/sec1-v2.pdf#subsection.2.2) and [secp256k1](https://www.secg.org/sec2-v2.pdf#subsubsection.2.4.1)). 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](https://en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm) for smooth $q-1$.

RobinLinus

4/18/24, 4:30 PM

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$.

RobinLinus

4/18/24, 5:02 PM

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.

fgrieu

4/18/24, 5:24 PM

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.

RobinLinus

4/18/24, 5:49 PM

@fgrieu yes, that's what I meant.

Score:5

Crypto

CRTified

4/18/24, 5:30 PM

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.

+ 3

RobinLinus

4/18/24, 5:51 PM

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.

CRTified

4/18/24, 8:46 PM

[This paper](https://doi.org/10.1515/jmc-2017-0053) 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.

RobinLinus

4/18/24, 9:19 PM

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.

Elon Musk

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

EN: What's wrong with this simple reduction of discrete logarithms to the Diffie-Hellman problem?

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.