# How does the security of Elliptic curve compare to normal discrete logarithm?

Intro:

EC are often compared with RSA but how about a more safe version of the discrete logarithm?

All 3 can be reduced to the problem:

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

In RSA $$P$$ is a product of two primes. To solve the discrete logarithm 'just' a factorization of $$P$$ is required. Different to the two other cases $$a,b$$ is known and $$g$$ is searched.

But if $$P$$ is a prime the problem can get much harder. It depends at the factorization of $$P-1$$ because $$P-1$$ is also equal to the number of different elements.

As far as I know the best choice is a 'safe prime' with $$P = 2 q +1$$ with $$q$$ a prime as well. This discrete logarithm can be solved in $$\mathcal{O}(\sqrt{q})$$ with $$q$$ the biggest prime factor (with Pollard's algorithm).

At EC $$P$$ is a prime as well but the number of elements can be different (but still $$\approx P$$). It can e.g. be determined with Schoof's algorithm. A number of safe elliptic curves can be found at safecurves.cr.yp.to . Tested safe curves had all $$2^3 \cdot q$$ elemnts (with $$q$$ a big prime). Afak solving those will also take $$\mathcal{O}(\sqrt{q})$$ time.

Question:

Given the discrete logarithm solving problem for normal numbers and elliptic curves (mod a prime $$P_i, P_e$$). Given a valid generator $$g_i, g_e$$ and a possible result $$b_i, b_e$$.

$$\text{normal: } b_i = g_i^{a_i} \mod P_i$$ $$\text{elliptic curve: } b_e = g_e^{a_e} \mod P_e$$

Let the elliptic curve have $$N_e = 2^3 \cdot q$$ different elements with $$q$$ a big prime (other variables chosen in that way).

Let $$P_i = 2 \cdot q +1$$

Do both problems have the same solving time of $$\mathcal{O}(\sqrt{q})$$ ?

(we ignore the linear factor of computation time for each single step due to different multiplication time)

Bonus questions:

Which other factor have impact into the solving speed?

BQ1.) The number of elements of some curves from safecurves.cr.yp.to had also the property: $$N_e -1 = 3 \cdot r$$ with $$r$$ a big prime. Does this have any impact?

BQ2.) Has the factorization of $$P_e -1$$ any impact at the security?

BQ3.) Has the factorization of $$q-1$$ any impact at the security? (for normal and EC)

Edit: Update

• It looks like 'number filed sieve' can do better than Pollard's algorithm ($$\mathcal{O}(\sqrt{q})$$). To use it on EC the embedding need to be small -> chose a big one
• besides the safe prime property $$P_i$$ should als be not close to $$p^n$$ with $$p$$ a small prime like $$2,3,..$$

$$\rightarrow$$ assumption: so there is a difference?

• keylength.com/en/compare – kelalaka Mar 4 at 19:01
• @kelalaka ty4link. But unsure about the naming: I guess symmetric would be AES, But whats the difference between 'Factoring Modulus', 'Discrete Logarithm Key', 'Discrete Logarithm Group'. – J. Doe Mar 4 at 19:16
• Symmetric is a general name for symmetric ciphers like AES, ChaCha. Factoring Modulus RSA like, the two other is realated to DSA – kelalaka Mar 4 at 19:20
• Interesting link but as far as I understood DSA is not exactly the same as the described normal discrete log problem. However it also operation at a sub-group generator with an order of 'Discrete Logarithm Key'-bit. This also supports the assumption of same computation time. During checking this links out I also noticed there is a faster method 'number filed sieve' and besides the safe prime property it should als not be close to $p^n$ with $p$ a small prime like $2,3,..$ Will add this – J. Doe Mar 4 at 21:10
• On the above comment: if one can solve the DLP in $\mathbb Z_p^*$, one can (trivially) solve DSA; for the converse, see this. – fgrieu Mar 5 at 19:09

As far as I know the best choice is a 'safe prime' with $$P=2q+1$$ with $$q$$ a prime as well.

This is the best choice for a given size of $$P$$, but not for a given size of $$q$$. See this.

This discrete logarithm can be solved in $$\mathcal{O}(\sqrt{q})$$ with q the biggest prime factor (with Pollard's (Rho) algorithm).

Essentially yes (minor caveat: $$\mathcal{O}(\sqrt{q})$$ is not effort, but the number of multiplications of integers of size $$P$$, with $$P>q$$, hence the effort grows faster by a factor at least $$\ln P\,\ln\ln P$$). That the DLP can be solved with such method and effort does not imply that such method or effort is needed. And if $$P$$ is a safe prime, there are methods (including the Number Field Sieve) requiring less effort. Again, see this.

Do (DLP in a subgroup of an appropriate Elliptic Curve on one hand, of $$\mathbb Z_P^*$$ on the other hand) have the same solving time of $$\mathcal{O}(\sqrt{q})$$ (group operations, where prime $$q$$ is the order of the subgroup)?

Yes, when using Pollard's Rho algorithm. That algorithm is believed optimum in the Elliptic Curve case, and for $$P$$ large enough in the $$\mathbb Z_P^*$$ case.

No, when $$P$$ is a safe prime (and large enough to make the DLP non-trivial), and using the Number Field Sieve to tackle the DLP in the subgroup of $$\mathbb Z_P^*$$.

Note: I don't know that the Number Field Sieve can be used to solve the DLP in an appropriate Elliptic Curve (sub)group; and it would come as a huge surprise if it was more efficient than Pollard's Rho algorithm.

• as far as I understood EC can be embedded in a $\mathbb{F}_{p^k}$ DLP. If the embedding degree $k$ is small NFS can be used at this. Depending at $k$ it can be faster. see question1 and question2 – J. Doe Mar 5 at 23:10
• ty for answering this as well. This was the first question and the linked was a 2nd trial but it generally also answering this question. I didn't knew how to proceed with this question. I think I know the difference now (except maybe the relation for some special primes which are somewhere in between those cases but not needed now). Thank you again. – J. Doe Mar 5 at 23:10