1
$\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
2
$\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, which 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 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}{llll} \text{group} & q & {\approx}\ell & \text{Pollard's $\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$

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.