2
$\begingroup$

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?

$\endgroup$
5
  • $\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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 20:14

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
9
  • $\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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 18:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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