# Tag Info

Accepted

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

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

### Calculate discrete log with known phi

As far as we know, no, there is no general method to efficiently solve the Discrete Logarithm Problem for composite $N$ even when $\phi(N)$ is given and $N$ is the product of two distinct primes†. ...
Accepted

### Discrete Logarithm Challenges and Records

For discrete log over $\mathbb{Z}_p^{*}$, as of 2019, a discrete logarithm was computed over a 795 bit safe prime . In practice, no one uses generic discrete logarithm algorithms (such as pollard ...
Accepted

### Challenges like RSA factoring challenge

Not that I am aware of. See the Certicom ECC challenge See the Darmstadt LWE challenge (part of a larger set of lattice challenges) Closest is probably the decoding challenge, though this is not ...
Accepted

### Multiplicative inversion of a generated point?

But can you construct $p^{-1}G$? No, you can't if: You're assuming that you can compute the inverse modulo an arbitrary base point (rather than a fixed one) The CDH problem is hard. That's because ...

### Method to break a baby Elliptic Curve analog to secp256k1

Solving discrete logarithms in $144$-bit groups is hard Even scaling down to 144-bits is likely beyond current capability. To my knowledge the largest elliptic curve problem tackled with "black ...

### Modular multiplication of two k-bit numbers takes k^2 modular additions?

TL,DR: The quote is wrong. Repair it by changing $k^2$ to $k$, or by counting bit operations rather than modular additions. We can perform multiplication modulo $p$ of two $k$-bit numbers $A$ and $B$ ...
Accepted

### On a problem assuming Diffie-Hellman oracle

If the group is of known prime order $q$ (which is usually the setting in which DH is considered), then $g^{1/x} = g^{x^{q-2}}$, and the latter can be obtained with $O(\log q)$ calls to the DH oracle.

### Modular multiplication of two k-bit numbers takes k^2 modular additions?

We want to find $x$ such that $g^x = h$, i.e. the discrete logarithm of $h$ to the base $g$ in $\mathbb F_p^*$ with $g$'s order $n$. For trial-and-error, brute-force, we can start to find $g^x$ ...

### discrete logarithm equality for independent groups

Here's a paper describing how to do it efficiently, with some concrete sizes depending on the size of $a$ and $b$: https://eprint.iacr.org/2022/1593, Fig. 1 (check table 1 for notation). It uses the ...
Accepted

### Given two unrelated generators $G_1$ and $G_2$, and a third with $H = G_1 + G_2$. Is it hard to compute $xG_1$ from $xH$?

Computing $xG_1$ knowing only $G_1$, $G_2$, and $xH$ is as hard as the computational Diffie-Hellman problem (CDH). For some given $xH$ we can choose, for example, $G_1 = yH$ and $G_2 = H - G_1$. This ...