3
$\begingroup$

I'm studying the basics of cryptography and I didn't understand why elliptic curves use fewer bits. For example, finite-field Diffie-Hellman needs at least 1024 bit and it's a DLP, but elliptic curves need at least 256 bit and it's also a DLP. What is the actual difference? Can you show mathematically why (with some example)?

I know that they aren't the same DLP, but they are part of the class of DLP. Is this part of the explanation?

The DLP of EC is more difficult to solve for how the group laws are defined, but is this the explanation (or part of it) to why EC requires less bit?

$\endgroup$
  • 6
    $\begingroup$ The TL;DR is "the representation of the group doesn't allow for faster attacks like Index-Calculus or GNFS". $\endgroup$ – SEJPM Oct 28 '17 at 12:31
7
$\begingroup$

The best algorithm for computing discrete logs in a well-chosen finite field $\mathbb Z/p\mathbb Z$, where the safe prime $p$ has no structure that can be exploited by the special number field sieve, is the general number field sieve, or GNFS for short. The GNFS costs $L^{\sqrt[3]{64/9} + o(1)} \approx L^{1.92999 + o(1)}$ bit operations, where $L = e^{n^{1/3} (\log n)^{2/3}}$ and $n = \log p$. If we treat the $o(1)$ term as zero, to raise this cost above $2^{128}$ we need to pick $n$ so that $$2^{128} \leq e^{1.92999 n^{1/3} (\log n)^{2/3}}.$$ Solving this in closed form is a pain involving the Lambert W product log function, but if we restrict our search to $1024 t$-bit primes $p$ so that $n \approx 1024 t \log 2$, we find the smallest bit size is $1024 t = 3072$. If we allow merely raising the cost above $2^{112}$, we can make do with $1024 t = 2048$.

\begin{equation} \begin{array}{cc} \text{modulus bit size} & \text{GNFS cost: $L^{1.92999}$} \\ \hline 1024 & 2^{87} \\ 2048 & 2^{117} \\ 3072 & 2^{139} \\ 4096 & 2^{157} \end{array} \end{equation}

Caveat: There may be batch optimizations like there are in the NFS for factoring[1]. So these may be optimistic overestimates when the adversary has a large number of targets to attack simultaneously. There are also other reasons—performance, storage costs, and side channel security—to prefer elliptic curve groups over finite fields, but that's a topic for another question.

In contrast, the best algorithm for computing discrete logs in a well-chosen elliptic curve group of order $\ell$ is essentially a generic algorithm for finding discrete logs in an arbitrary group, namely Pollard's $\rho$ algorithm, with merely small constant factor speedups for elliptic curves, and costs $\sqrt{\ell \pi/4}$ curve additions, which will require hundreds of bit operations apiece.

The square root cost means that if we want the cost of an attack to be $2^\lambda$ then we need to choose a group of prime order $(2^\lambda)^2 = 2^{2\lambda}$. By Hasse's theorem, the order of the curve group over a coordinate field of order $q$ can't differ from $q$ by more than about $\sqrt q$, so we need to choose a curve over a finite field with about twice as many bits as we want bits of security $\lambda$. Some curves like NIST P-224 are chosen to have groups of prime order, while others like Curve25519 are chosen to have groups of composite order $h \ell$ for small cofactor $h = 8$ and large prime $\ell$ so $\ell \approx q/h$.

\begin{equation} \begin{array}{cccc} \text{group} & q & {\approx}\ell & \text{$\rho$ cost: $\sqrt{\ell \pi/4}$} \\ \hline \text{NIST P-224} & 2^{224} - 2^{96} + 1 & 2^{224} & 2^{111} \\ \text{Curve25519} & 2^{255} - 19 & 2^{252} & 2^{125} \\ \text{edwards448} & 2^{448} - 2^{224} - 1 & 2^{445} & 2^{222} \end{array} \end{equation}

In brief, there are much cheaper algorithms for computing discrete logs in the finite field $\mathbb Z/p\mathbb Z$ than for computing discrete logs in the elliptic curve $E(\mathbb F_q)$, so we need to choose $p$ much higher than $q$ for the same security.

$\endgroup$
0
$\begingroup$

It's very common for mathematicians to have a hard time understanding the concept that isomorphic groups can have drastically unequal difficulty of discrete logarithms.

For example, consider the additive group $(\mathbb{Z}/n\mathbb{Z}, +)$. Repeated addition here is just multiplication, so the discrete logarithm problem becomes: $$\text{Given } (x, \alpha x), \text{ find } \alpha.$$ This problem is easy to solve: just use the extended Euclidean algorithm to divide $\alpha x$ by $x$.

Now consider the multiplicative group of units mod $p$: $((\mathbb{Z}/p\mathbb{Z})^*, \cdot)$. This group is isomorphic to $(\mathbb{Z}/(p-1)\mathbb{Z}, +)$, but the discrete logarithm problem in the former is much harder, because there's no way to apply the extended Euclidean algorithm. The representation of integers as units mod $p$ provides much less information about their relationship to the group structure than the representation of integers as ordinary residue classes mod $n$.

If you just think about it enough, it makes total sense. For example if I see "1000" then I immediately know that adding 1 to itself one thousand times yields 1000, but if I see "942" then unless you're incredibly brilliant it would be hard to tell at a glance that multiplying 2 by itself one thousand times modulo 1009 yields 942.

In some cases, it is easy to see group relationships in the group of units of a finite field. This happens when the equation is small enough that elements don't reduce modulo $p$. For example, if I see "8" in a finite field then I immediately know that it equals 2 multiplied by itself three times. But in general you won't get so lucky.

Elliptic curves have even less information encoded in the representations of their elements than units in a finite field, which is why elliptic curve discrete logarithms are even harder than finite field discrete logarithms. In particular, unlike finite fields, even small equations are not obvious on an elliptic curve. On a finite field if I see "8" then I know it equals $2^3$, but if I see "(8,9)" on an elliptic curve then there is no immediately obvious relationship to "(2,5)" on the same curve.

The exact reasons why elliptic curve discrete logarithms are hard can be quite technical, but the above illustrates the intuition.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.