2
$\begingroup$

if i'm not mistaken, the supersingular curve's endomorphism ring is non-abelian. but why does it matters? or is it not even related to its endomorphism ring?

$\endgroup$
9
$\begingroup$

There's many different answers to this question, depending on what you mean by "why".

  1. You can't replace supersingular with ordinary and still have SIDH. Supersingular isogeny graphs are regular graphs ((ℓ+1)-regular for the graph of isogenies of degree ℓ). Ordinary isogeny graphs are not in general, so SIDH simply would not work with them.

  2. There is an older key-exchange protocol, proposed independently by Couveignes and Rostovtsev-Stolbunov, which uses ordinary graphs (we'll call CRS this protocol). It is similar to SIDH, but not the same. It is vulnerable to a sub-exponential attack by Childs-Jao-Soukharev, so its quantum security is hard to assess, although the system is not considered completely broken. At security levels that could be considered equivalent to SIDH, CRS is much slower (absolutely impractical).

  3. Recently, Castryck, Lange, Martindale, Panny and Renes introduced CSIDH, which is really the CRS system, where you replace the word "ordinary" with "supersingular", and do some optimizations. CSIDH is much faster than CRS, although slower than SIDH. CSIDH is still vulnerable to the Childs-Jao-Soukharev attack, so its parameters scale worse than SIDH.

  4. CSIDH highlights one of the main reasons we use supersingular curves: it is easy to control their group structure, which in turns makes it easy to have rational torsion points, which allows us to apply Vélu's formulas, which are much more efficient than generic isogeny-computation algorithms.

  5. Finally, going back to SIDH, the Childs-Jao-Soukharev attack does not apply to it. Why? Because the endomorphism ring of supersingular curves is larger (and non-commutative). The Childs-Jao-Soukharev attack requires expressing the isogeny computation problem as an (abelian) hidden shift problem. In the SIDH case, there is no known hidden shift structure. The net effect is that SIDH parameters scale better as security grows.

$\endgroup$
  • $\begingroup$ That is where i got confused. The endomorphism ring is an isogeny from a curve to itself right? but SIDH use isogeny from a curve to another curve right? i don't get it why the endomorphism ring of a supersingular curve could prevent the attack while SIDH is using an isogeny between different curves $\endgroup$ – Hanif May 22 '18 at 16:03
  • 1
    $\begingroup$ An endomorphism is an isogeny from a curve to itself. The endomorphism ring is the ring made of all such isogenies, with the operations of addition and composition. $\endgroup$ – Luca De Feo May 22 '18 at 18:33
  • 1
    $\begingroup$ The endomorphism ring is strongly related to the isogeny graph, both in the ordinary and in the supersingular case. Isogenies can be viewed as ideals of the endomorphism ring, and a path in an isogeny graph can be identified to an ideal class (i.e., a class of ideals up to some equivalence relation, depending on the precise case). The Childs-Jao-Soukharev attack exploits this relationship when the endomorphism ring is commutative (i.e., in the ordinary, or in the CSIDH case), however we do not know how to exploit this relationship in the general supersingular case. $\endgroup$ – Luca De Feo May 22 '18 at 18:40
  • $\begingroup$ I think i starting to get this. Thankyou so much sir! $\endgroup$ – Hanif May 23 '18 at 6:26

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.