0
$\begingroup$

Most isogeny-based cryptographic schemes rely on constructing an isogeny having a given kernel. That is, given an elliptic curve $E$ and a subgroup $G$ of points of $E$, there is interest in constructing an isogeny $\phi : E \rightarrow E_1$ into some elliptic curve $E_1$ such that the kernel of $\phi$ is $G$. The isogeny $\phi$ and curve $E_1$ can both be constructed through the use of Velu's formulas.

I'd like to perform this construction in MAGMA. MAGMA seems to natively support this somewhat, with a few functions defined here:

http://magma.maths.usyd.edu.au/magma/handbook/text/1443#16366

These functions seem to use the language of (subgroup) schemes, which I am unfamiliar with. From what I can tell it defines $\phi$ by specifying its kernel polynomial. I tried the following code below, but it doesn't give the result that I expect. In my case, I'd like the kernel of $\phi$ to be the subgroup generated by a single point $P$.

F := GF(83);
E := EllipticCurve([0, F ! 1]);
P := E ! [22,78];
R<x> := PolynomialRing(F);
f := x - P[1];
G := SubgroupScheme(E,f);
Order(P);
Points(G);

IsogenyFromKernel(G);

The output is:

21
{@ (22 : 5 : 1), (22 : 78 : 1), (0 : 1 : 0) @}

IsogenyFromKernel(G: Subgroup scheme of C defined by x + 61)
IsogenyFromKernel(C: C,f: x + 61)
In file "/magma/package/Geometry/CrvEll/subgroup_schemes.m", line 9, column 29:
>>     return IsogenyFromKernel(C, f, 0 : Check:=Check);
                               ^
Runtime error in 'IsogenyFromKernel': Does not appear to be a kernel in Isogeny

First, $P$ has order $21$ while the "subgroup" consists of three points: $P$, $-P$, and $Id(E)$. Does the polynomial have to contain the $x$ coordinates of every point in the subgroup? Is there a simpler way to do this?

$\endgroup$
1
$\begingroup$

I am the inventor of Supersingular Isogeny Diffie-Hellman. Magma for some ridiculous reason doesn't have this particular common construction built in. You can re-create it manually using

IsogenyFromKernel(E, &*{(x-(n*P)[1]) : n in [1..Order(P)-1]});

Essentially this command reconstructs the kernel polynomial (&* is the magma command corresponding to \prod in LaTeX).

$\endgroup$

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.