3

So I was trying to implement a CRS key exchange using modular polynomial. I start with a curve $E_1$, for Elkies prime $\ell$, I solve for the roots of classical modular polynomial $\Phi_\ell(X,j(E_1))$. Then I could obtain the j-invariant $j(E_2)$ of an isogeneous curve. However, I should be distinguishing two possible isogeny with different Frobenius eigenvalues $\lambda,\mu$. Therefore I have to somehow restore the isogeny polynomial to do this, which is suggested in [1], page 12.

Problem. Suppose $E_1,E_2$ of the same characteristic are isogeneous given by $\phi:E_1\to E_2$ where $\ker\phi$ is small. Is it possible to compute its kernel polynomial $\chi\in\mathbb F_p[X]$ that collects $\ker\phi$ as its zeros? In particular, I was using SageMath 9.0, is there anything I can use in it?

[1]"CSIDH: An Efficient Post-QuantumCommutative Group Action," Castryck et al.

Taylor Huang
  • 499
  • 2
  • 8

1 Answers1

2

The whole point of CSIDH is that by concocting a suitable elliptic curve in which all the necessary kernel points are defined over the base field, it is possible to compute isogenies without resorting to modular polynomials at all. Since you are implementing CRS, not CSIDH, you need modular polynomials. For that reason, the CSIDH paper is not the best place to go looking for hints on how to do your computation.

The precise algorithms for computing the kernel polynomial are quite complicated -- much too involved for me to provide here. The canonical source is Schoof, R.: Counting points on elliptic curves over finite fields. J. Théor. Nombres Bordeaux 7, 219–254 (1995), specifically Section 8 "The kernel of the isogeny." Unfortunately this paper is not super clear from an algorithmic point of view. I am not aware of any place where the entire algorithm is written out in explicit detail.

The best overview of modular polynomial isogeny computation is Broker, R., Charles, D., Lauter, K.: Evaluating large degree isogenies and applications to pairing-based cryptography, Pairing 2008, Lecture Notes in Computer Science 5209, 100-112 (2008). This article contains fairly explicit descriptions of algorithms for almost everything, including how to distinguish the two possible isogenies (end of Section 3.1) -- everything, that is, except the kernel polynomial computation!

djao
  • 1,119
  • Hi, thanks for your reply. The reference you just provided seems to focus on ordinary cases. Would you recommend some references for supersingular cases? As I am actually dealing with supersingular cases and specifically with those curves possibly of j-invariant=1728. – Taylor Huang Feb 19 '20 at 12:03
  • Your question doesn't make sense. CRS, by definition, operates over ordinary curves. CSIDH is a variant of CRS which uses supersingular curves. If you are indeed implementing CSIDH and not CRS, then please say so. In any case, if you are using modular polynomials, then the algorithm is the same regardless of whether the curves are ordinary or supersingular; the main advantage of CSIDH is that you can implement it WITHOUT modular polynomials, which would be a different algorithm (and if you are implementing that algorithm, please say so). – djao Feb 20 '20 at 13:08
  • Well, I'm using CRS except with supersingular curves, or equivalently you might say that I used CSIDH except with modular polynomial (since CSIDH, by definition samples torsion points directly instead of using modular polynomial). The problem with modular polynomial on supersingular curves is that, I don't know how to identify those Fp rational isogeny even if I knew there must be one from the setting. – Taylor Huang Feb 20 '20 at 18:43
  • What exactly goes wrong if you apply the ordinary algorithms in the supersingular case? As far as I know there is nothing in the ordinary algorithms that would go wrong in the supersingular case. – djao Feb 21 '20 at 00:41
  • So in particular, for some curves, there are 3 distinct roots of $\Phi_{\ell}(X,j(E))$ in $\mathbb{F}_p$, each with multiplicty 2. I don't know which one would lead me to the $\mathbb{F}_p$ rational isogeny. – Taylor Huang Feb 21 '20 at 07:48
  • They might all lead to rational isogenies--because there's no isogeny volcano in the supersingular case, one is not restricted to merely two possible rational isogenies. The theoretical structure of the supersingular isogeny graph is described in Mestre, La Methode des Graphes. – djao Feb 22 '20 at 05:22
  • Perhaps I should state it more clear. In my case there should only be two Fp-rational isogenies because I've chosen ell to be Elkies primes. – Taylor Huang Feb 22 '20 at 15:01
  • I don't think the concept of Elkies prime is useful in the supersingular case. In the ordinary case, the fact that Frobenius satisfies a certain characteristic equation determines the Frobenius completely up to conjugation, because there are only two dimensions of endomorphisms. But in the supersingular case there are four dimensions of endomorphisms, and you don't know which combination of those four basis vectors satisfying the characteristic polynomial is the one you want. Elkies primes are normally used for point counting, which is easy for supersingular curves since the trace is 0 mod p. – djao Feb 22 '20 at 18:24
  • Well, even for supersingular curve, its Fp-rational endomorphism, which is smaller than the full endomorphism ring, should be 2-dimensional because their kernels are Galois invariant. Elkies primes are still necessary to classify isogenies using Frobenius eigenvalue associated with its kernel. This is just as the construction in CSIDH. – Taylor Huang Feb 23 '20 at 05:57
  • Ok so you would take each candidate j-invariant and compute the corresponding kernel polynomial using School's algorithm. If the kernel polynomial is defined over Fp, then you have your Fp-rational isogeny. If not, then it's not Fp-rational. You'll have to try all the candidates, which is slower, but that's why the supersingular case is harder. CSIDH avoids this problem by starting with explicit kernel points instead of obtaining them indirectly via modular polynomials. – djao Feb 23 '20 at 16:25
  • just to make it clear, by all candidate did you mean all $\ell+1$ roots in algebraic closure? or we could restrict our candidate somehow to roots in $\mathbb F_p$? – Taylor Huang Feb 23 '20 at 16:44
  • If an isogeny is defined over Fp then its codomain is defined over Fp, so you only need to consider j-invariants in Fp. – djao Feb 24 '20 at 02:36
  • Oh, okay. I guess my problem is to construct the Fp-rational isogeny. A method discribed in "ON ELKIES SUBGROUPS OF`-TORSION POINTS INELLIPTIC CURVES DEFINED OVER A FINITE FIELD," algorithm 2, uses differential equation to solve it. However, I kinda stuck at the last step, which is to use Berlekamp-Massey algorithm to restore the rational form. What do you think about this approach? – Taylor Huang Feb 26 '20 at 10:31