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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The j-invariants classify the elliptic curves up to isomorphisms (if we suppose to work in the algebraic closure). Is this classification used in some way to decide whether or not an elliptic curve can be used in cryptography?

  • If j-invariants can not be used for classification, is there an other classification which responds to my question?

  • If j-invariants can be used for classification, what does the j-invariants tell us about the curve so that we know it is save to use it for cryptography?

For example: can a certain j-invariant correspond to a curve where we are sure that it has full-torsion so that it is a possible choice for Weil pairing?

share|improve this question
    
Try to split your questions into easy to read paragraphs and try to use small sentences with a minimum of (unclear) back references. We can read single paragraphs with long sentences and back references, but we'd rather not. – Maarten Bodewes Oct 22 '15 at 12:00
    
There are two special j values: 0 and 1728. Elliptic curves with j=0 are interesting for pairings, because they have twisting isomorphisms of degree 6. This will frequently be used for compact representations of elliptic curve points of Baretto-Naehrig curves. – Cryptostasis Oct 22 '15 at 14:32
    
So could I conclude that these are the main j-values? Does this mean that the other j-values are not used? – user28082 Oct 22 '15 at 17:19
    
I have only given an example of an interesting j value. From that you cannot conclude that other values are not interesting. – Cryptostasis Oct 22 '15 at 18:24
    
In addition to my previous comment: I would use j=0 curves for Tate(Ate,...) pairings only. For standard (i.e. non-pairing) ECC based algorithms I would use random curves, which have random j values – Cryptostasis Oct 22 '15 at 20:14

Giving the j-invariant is basically equivalent to giving a curve equation (up to quadratic twist) (over $\mathbb F_p$ for $p > 3$) : to each j-invariant you can attach a pair of curves $(E, \widetilde E)$. You can easily compute the curve equations of $E$ and $\widetilde E$ from $j$:

$$E: y^2 = x^3 + a x + 2a, \qquad a = -\frac{27j}{j-1728}$$

Now the $j$-invariant is "suitable for crypto" if both curves above are suitable, which you can check using the usual algorithms (SEA, etc.). Since it is easy to go from “curve equation” to “j-invariant” and back, it is also easy to conclude that the j-invariant does not contain anything particularly useful for cryptography.

share|improve this answer
    
This is not quite correct. The j invariant classifies elliptic curves up to isomorphism over an algebraic closure. There are many non $\mathbb F_p$-isomorphic curves with the same j-invariant. – Cryptostasis Oct 30 '15 at 14:33
    
You wrote: "Since it is easy to go from “curve equation” to “j-invariant” and back, it is also easy to conclude that the j-invariant does not contain anything particularly useful for cryptography." I cannot see this equivalence. For this and my previous comment, I have no choice but to vote your answer down. – Cryptostasis Oct 30 '15 at 15:36
1  
Cryptostasis, there are not "many non $\mathbf F_p$-isomorphic curves with the same j-invariant", but only two (in the ordinary case), as already stated in the answer: a curve and its quadratic twist. – Calodeon Oct 31 '15 at 9:22
    
@calodeon: The curve and their quadratic twist are the $\mathbb F_p$ isomorphic curves. But there are many non $\mathbb F_p$ isomorphic curves. For instance, all curves of the form $y^2 = x^3 + b$ have j=0. – Cryptostasis Oct 31 '15 at 16:28
1  
@Cryptostasis: So there are only... at most 6 isomorphism classes for curves of the form $y^2 = x^3 + b$ ("at most" because it depends on the number of cubic roots of unity in the field). That is more than 2, only because $j = 0$ is not ordinary. – Calodeon Oct 31 '15 at 18:54

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.