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?

  • $\begingroup$ 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. $\endgroup$
    – Maarten Bodewes
    Oct 22 '15 at 12:00
  • $\begingroup$ 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. $\endgroup$
    – user27950
    Oct 22 '15 at 14:32
  • $\begingroup$ So could I conclude that these are the main j-values? Does this mean that the other j-values are not used? $\endgroup$
    – user28082
    Oct 22 '15 at 17:19
  • $\begingroup$ I have only given an example of an interesting j value. From that you cannot conclude that other values are not interesting. $\endgroup$
    – user27950
    Oct 22 '15 at 18:24
  • $\begingroup$ 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 $\endgroup$
    – user27950
    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.

  • $\begingroup$ 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. $\endgroup$
    – user27950
    Oct 30 '15 at 14:33
  • $\begingroup$ 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. $\endgroup$
    – user27950
    Oct 30 '15 at 15:36
  • 1
    $\begingroup$ 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. $\endgroup$
    – Calodeon
    Oct 31 '15 at 9:22
  • $\begingroup$ @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. $\endgroup$
    – user27950
    Oct 31 '15 at 16:28
  • 1
    $\begingroup$ @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. $\endgroup$
    – Calodeon
    Oct 31 '15 at 18:54

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.