3
$\begingroup$

I don't understand how the shapes of isogeny graphs are determined. While Alice and Bob do walk on it and don't backtrack, are they actually relevant to crypto?

Also, I was told that supersingular isogeny graphs are expander graphs. Similarly, how is the shape of an expander graph determined

$\endgroup$
2
  • 2
    $\begingroup$ I highly recommend eprint.iacr.org/2018/593 for an overview of isogeny graphs in cryptography. $\endgroup$
    – djao
    Sep 10 '18 at 23:01
  • $\begingroup$ @djao thank you so much for this paper! It ascends to slightly daunting depths very soon, but is immensely helpful. Is there a visual demonstration of the encryption process of SIDH in regards to an isogeny graph? $\endgroup$
    – edlothia
    Apr 10 '19 at 8:48
3
$\begingroup$

Let an elliptic curve $E(F_p)$ have the Frobenius discriminant $D_\pi$, and $\left(\frac{D_\pi}{l}\right)$ be a Kronecker symbol for some $l$-degree isogeny. If $\left(\frac{D_\pi}{l}\right)=-1$, then there are no $l$-degree isogenies; if $\left(\frac{D_\pi}{l}\right)=1$, then two $l$-degree isogenies exist; if $\left(\frac{D_\pi}{l}\right)=0$, then $1$ or $l+1$ $l$-degree isogenies exist.

Therefore, if $\left(\frac{D_\pi}{l}\right)=1$. then $l$-degree isogenies of elliptic curves form branchless cycles, and changing direction in a cycle means switching to dual isogenies.

This is a Theorem2 of "PUBLIC-KEY CRYPTOSYSTEM BASED ON ISOGENIES", by Alexander Rostovtsev and Anton Stolbunov. With this theorem, you can determine the shape of isogeny graphs.

$\endgroup$
2
  • $\begingroup$ Thanks! It seems like constructing every graph will be a tedious task (is there any method of automation?) $\endgroup$
    – edlothia
    Sep 11 '18 at 11:29
  • 1
    $\begingroup$ @edlothia, It is easy to create a $2n$-regular graph, by choosing the $n$ $l_i$ that $\left(\frac{D_\pi}{l_i}\right)=1$. $\endgroup$ Sep 11 '18 at 18:21

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.