Why Elliptic Curves?

Question

What is the benefit of using elliptic curves over the standard finite field, when the cyclic subgroup we consider of the EC's solution group is just isomorphic to some integer residue class of prime order? Is it because the group operation is more complex?

Answer 1

The answer is about the difficulty of discrete logarithm. The notion of isomorphism does not capture all that matters in cryptography; we also need to consider computing costs.

Suppose that we have an abelian group $\mathbb{G}$ with additive notation. Let $G$ be a conventional element of $\mathbb{G}$ of order $n$. The subgroup generated by $G$ is: $$\langle G\rangle = \{ xG \ | \ 0\leq x\lt n \}$$ That subgroup is isomorphic to $\mathbb{Z}_n$ (the integers modulo $n$) and the isomorphism is easily computed in one direction, from $\mathbb{Z}_n$ to $\langle G\rangle$ with a double-and-add algorithm: from $x$, one can compute $xG$ with less than $2\log n$ group operations (see this in the case of elliptic curves, but it really applies to any group).

Discrete logarithm is about computing the inverse isomorphism, i.e. computing $x$ from $xG$. Generically, when the only operations that you can do on elements of $\mathbb{G}$ are applying the group law, and comparing two elements for equality, then the discrete logarithm cannot be computed with an average cost of less than $\sqrt{n}$ operations. We know several "generic" algorithms that offer that kind of performance, e.g. Pollard's rho algorithm. It can be proven that no faster algorithm exists, that would work on a generic group.

---

Of course, generic groups are an abstract concept. What we have in practice are groups on which we know how to compute the group law and compare two elements, and possibly have some extra information on the group structure that may or may not help in computing discrete logarithms.

Right now, when the group is a randomly chosen elliptic curve, then we have no idea how to compute the discrete logarithm faster than by applying a generic algorithm. Thus, a "256-bit curve" (sub-group order $n$ is a 256-bit prime) is enough to achieve a "security level of 128 bits" (i.e. unbreakable with existing and foreseeable technology). Note that there are some specific curves with a special structure for which we know faster discrete logarithm algorithms (e.g. supersingular curves).

However, when the group $\mathbb{G}$ consists in integers modulo $p$ for some prime $p$, with multiplication modulo $p$ as group law, then we do know faster (subexponential) discrete logarithm algorithms, in particular in the large family known as index calculus. To achieve a security level of 128 bits, one has to choose a modulus substantially larger (somewhere between 2500 and 3000 bits).

Since field operations tend to have a quadratic cost in the field size (at least with the kind of algorithms that are fastest in fields commonly used in cryptography), the speedup obtained by using an elliptic curve and a relatively small field more than compensates the overhead of elliptic curve operations. In practice, on today's computers and for comparable security levels, with decently optimized implementations, elliptic curves offer a 5x to 20x speedup. Which is why we use them. As an added bonus, the corresponding curve points can be encoded over fewer bits, so this also saves a bit of network bandwidth in some cases.

Answer 2

In elliptic curves you don't have index calculus method. Only the generic algorithms (Shank's, Pollard) as the previous poster said. In order to elaborate a little, why you don't have index calculus, you have to see the steps of index calculus. The first step is to construct a factor base (in $GF(p^n)$ is consisting from polynomials) the second is to find relations and the third is the linear algebra step(solve a large linear system). In the case of elliptic curves we do not know how to construct a factor base. An interesting (but not successful) approach in order to solve the previous problem is the XEDNI algorithm.