Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

The set of points of an elliptic curve over a finite field is isomorphic to the direct product of two cyclic groups (i.e. $E(F_{p^n}) \cong Z_{s} \times Z_{t})$.
What is the advantage of representing or conceiving the group as an Elliptic Curve instead of as a product of cyclic groups?

share|improve this question

3 Answers 3

up vote 7 down vote accepted

The first assumption: $E(F_q) \simeq Z_s \times Z_t$ is always true!! (see Handbook of Elliptic and HyperElliptic Curve Cryptography) It is never said that coordinates of points lie on $Z_s \times Z_t$ which has no sense except if $s=t$.

But the isomorphism is not trivial to compute (it is in fact hard to compute, since it is related to the discrete logarithm for the left-to-right part).

And working only with the representation $Z_s \times Z_t$ will weaken the discrete logarithm so useful for cryptographic purposes.

In brief, if you can exhibit a curve (or demonstrate that there is a NIST curve) for which the computation of the left-to-right part of the isomorphism is easy, then this curve MUST be considered as weak and must never be used for any cryptographic purpose.

Concerning quantum computers, EC-DLOG will be solved as easily as for any cyclic group, since the Shor algorithm can be adapted to solve it, but don't ask me about details, I don't understand them...

share|improve this answer
    
I'll assume that the weakening of the discrete logarithm refers to the lack of fast algorithms for it over elliptic curves. –  user1992284 Jun 26 '13 at 2:48

Your first assumption is not entirely correct. They are not isomorphic to the direct product of two cyclic groups but rather a subset of all points in $\mathbb{Z}_q^2$, which fulfill a certain equation. Elliptic curves over $\mathbb{C}$ are closely related to the torus (genus 1 curve). Since the addition and multiplication (defined via multiple additions) are defined in a different way, you can not just use the product of two cyclic groups.

But what is the advantage?

First, we do not know any subexponential algorithm like Index Calculus for the discrete logarithm in elliptic curves. Therefore, elliptic curves can be chosen much smaller than other groups. Although the computations for the EC-addition are quite complex compared to modular multiplication and exponentiation, they are much faster due to the smaller modulus.

And then, EC-crypto might still be viable in a world with quantum computers, where the traditional DLOG and factorization are easy. As of now, there are no algorithms based on quantum computers which would make EC-DLOG easy.

share|improve this answer
2  
Correction: a finite elliptic curve is known to be isomorphic to the product of two specific cyclic groups; that is, there is a bijective mapping between elliptic curve points and the product of two cyclic groups that preserves the group operation (that is, $MAP(a) + MAP(b) = MAP(a+b)$, for any two group members $a$ and $b$). However, what's also true is that this mapping is hard to compute (at least, from the curve to the explict group direction), and so while they are essential identical (isomorphic) from a mathematical perspective, they are not from a computational perspective. –  poncho Jun 26 '13 at 19:07

The entire reason for using Elliptic Curves for cryptography is that they make some operations easy (e.g. "given an integer $n$ and a point $G$, compute the point $nG$), while other operations are difficult (e.g. given two points $G$ and $nG$, give me the integer $n$); the security of Elliptic Curve Cryptography depends crucially on this.

Does this hold true for your alternative representation as "a product of cyclic groups"? If it does not, well, there's your answer -- we use Elliptic Curves rather than your alternative representation because Elliptic Curves has good security properties, and your alternative representation doesn't.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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