16
$\begingroup$

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?

$\endgroup$
21
$\begingroup$

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.

$\endgroup$
  • 13
    $\begingroup$ I have a feeling that teaching should emphasize more that all finite cyclic groups are (abstractly) isomorphic to some group in which discrete logarithms are easy (namely $(\mathbb Z/n\mathbb Z,+,0)$), and that the difficulty lies precisely in computing that isomorphism. Lots of people do not seem to grasp this concept, which may be partly due to everyone talking about "groups in which DLP is hard" instead of "group representations which make DLP hard", which is really what the matter is about. $\endgroup$ – yyyyyyy Jul 11 '15 at 21:28
  • $\begingroup$ very good point ! $\endgroup$ – Alexandre Yamajako Jul 12 '15 at 0:04
  • $\begingroup$ @yyyyyyy: To be entirely fair, that's only true if you use "group" to secretly mean "isomorphism class of groups", a habit whose use is a combination of experience, philosophy, and one's needs at the time. $\endgroup$ – Hurkyl Jul 13 '15 at 2:07
  • $\begingroup$ GREAT answer. Thanks. If possible, it would be great to have some references. $\endgroup$ – Chipotle Jan 24 at 16:14
1
$\begingroup$

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.

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