Kummer Isogeny

This repository contains SageMath classes for KummerLine, KummerPoint and KummerLineIsogeny.

• KummerLine is the Kummer Line associated to a Montgomery curve $C : y^2 = x(x^2 + Ax + x)$.
• KummerPoint is the point on this line, and is the $x$-coordinate of a point on a Montgomery curve in projective coordinates $x(P) = (X : Z)$.
• KummerLineIsogeny computes a composite degree isogeny between two Kummer Lines

There are two main reasons to use $x$-only point arithmetic and isogeny computations:

1. Fast: Using $x$-only formula is more efficient. For example, we gain something like a 5-25x speed up against SageMath isogenies
2. More Torsion: Working with x-only isogenies allows us to access rational torsion on both the elliptic curve and its quadratic twist. This is used, for example, in SQISign.

However, $x$-only formula are not always suitable. The biggest issue is we lose our group structure. On an elliptic curve, we can always compute $P + Q$ given points $P, Q$. However, for points on the Kummer Line, we can only compute $x(P) + x(Q)$ if we have $x(P), x(Q), x(P-Q)$. Using a square-root, a $y$-coordinate can always be recovered to get $P$ or $-P$, but more information is needed if this sign needs to be set. Similarly, when we compute $\phi(xP)$ using KummerLineIsogeny, we can only evaluate the image of the $x$-coordinate.

The KummerLine and KummerPoint classes are simply $x$-only arithmetic on Montgomery curves packaged somewhat nicely. Further detail of these classes is included as comments in the code.

The KummerLineIsogeny classes implement:

• A simple and compact algorithm for SIDH with arbitrary degree isogenies by Craig Costello and Huseyin Hisil for the small, odd $\ell$ degree isogenies
• Computing Isogenies between Montgomery Curves Using the Action of (0, 0) by Joost Renes for the $2$-isogenies
• A trick from A faster way to the CSIDH by Michael Meyer and Steffen Reith for faster codomain computations using twisted Edwards curves
• Faster computation of isogenies of large prime degree the VeluSqrt formula by Daniel J. Bernstein, Luca De Feo, Antonin Leroux, Benjamin Smith for large $\ell$ degree isogenies

Examples

Construction of Kummer Line and Kummer Points

A KummerLine can be constructed straight from a Montgomery curve:

E = EllipticCurve(F, [0,A,0,1,0])
K = KummerLine(E)

Or, it can be constructed from the Montgomery coefficient

K = KummerLine(F, A)

Additionally, we allow A = (A : C) to be stored projectively and we can construct this in the following way:

K = KummerLine(F, [A, C])

A KummerPoint can be constructed from coordinates

xP = K(X, Z)

Where $x(P) = (X : Z)$ is the $x$-coordinate in projective $XZ$-coordinates.

A KummerPoint can also be made straight from an elliptic curve point

E = EllipticCurve(F, [0,A,0,1,0])
P = E.random_point()

K = KummerLine(E)
xP = K(P)

Arithmetic of Kummer Points

We can perform arithmetic in the following way:

# Take an elliptic curve and two points
F = GF(163)
A = 6
E = EllipticCurve(F, [0,A,0,1,0])
P, Q = E.random_point(), E.random_point()

# Map these to the Kummer Line and three Kummer points
K = KummerLine(E)
xP, xQ, xPQ = K(P), K(Q), K(P - Q)

# We can double points in two ways
assert 2*xP == xP.double()
assert 2*xP == K(2*P)

# We can perform differential addition
assert xP.add(xQ, xPQ) == K(P + Q)

# We can perform scalar multiplication
assert 11*xP == K(11*P)

# We can also do a three point ladder
assert xQ.ladder_3_pt(xP, xPQ, 11) == K(P + 11*Q)

Kummer Line Isogenies

The code should feel familiar to those who use the Elliptic Curve isogeny classes.

The main thing to understand is that for these $x$-only formula, we cannot compute a degree two isogeny with the point $P = (0, 0)$ as the kernel. Most of the time this can just be avoided when constructing the torsion basis, but it's something to be aware of.

# Supersingular curve
p = 163
F = GF(p^2)
A = 6
E = EllipticCurve(F, [0,A,0,1,0])
P, Q = E.gens()

# We can't use the point (0,0) in E[2] as a kernel
check = (p+1)//2 * P
if check[0] == 0:
    P, Q = Q, P

# Compute an isogeny of degree p+1
assert P.order() == 164
phi = E.isogeny(P, algorithm="factored")
EA = phi.codomain()

# Compute the same isogeny using x-only formula
K = KummerLine(E)
xP, xQ = K(P), K(Q)
psi = KummerLineIsogeny(K, xP, p+1)
EB = psi.codomain().curve()

# Isogenies should be the same up to isomorphism
assert EA.is_isomorphic(EB)

# We can also evaluate points
imQ = phi(Q)
imxQ = psi(xQ)

# Up to isomorphism and an overall sign, the images
# should be the same!
iso = EA.isomorphism_to(EB)

# We can check by comparing x-coordinates
assert iso(imQ)[0] == imxQ.x()

Future Work

There's a lot that could be improved, but the main things I'm thinking about:

• Implement isomorphisms between Kummer Lines, this is simply a case of writing explicit isomorphisms between Montgomery curves
• If we have these isomorphisms, we can avoid avoiding the point $(0,0)$ in the kernel by mapping to some other isomorphic Kummer Line
• Improve the performance of the velusqrt formula. They seem to be underperforming by a factor of 5-10x!!
• Implement the ability to compose two isogenies $\phi \circ \psi$ by phi * psi.

Rough Benchmarking

SQISign

The starting motivation for this code was to write $x$-only isogenies which could be integrated into https://github.com/LearningToSQI/SQISign-SageMath to allow our implementation SQISign to more closely match the proof of concept.

Looking at the rough benchmarks, the inclusion of this new code could have something between a 5-10x performance improvement of the isogeny computations, which by far are the most expensive part of our implementation.

Original SQISign Parameters

Using the original prime $p_{6983}$ from the paper SQISign: compact post-quantum signatures from quaternions and isogenies by Luca De Feo, David Kohel, Antonin Leroux, Christophe Petit, and Benjamin Wesolowski, we get the following results:

================================================================================
Computing isogenies of degree: 2^33 * 5^21 * 7^2 * 11 * 31 * 83 * 107 * 137 *
751 * 827 * 3691 * 4019 * 6983
================================================================================
Naive SageMath codomain computation: 3.97165
Naive SageMath point evaluation: 0.38979

Optimised SageMath codomain computation: 1.03724
Optimised SageMath point evaluation: 0.17907

KummerLine codomain computation: 0.10494
KummerLine point evaluation: 0.02335

================================================================================
Computing isogenies of degree: 2 * 3^53 * 43 * 103^2 * 109 * 199 * 227 * 419 *
491 * 569 * 631 * 677 * 857 * 859 * 883 * 1019 * 1171 * 1879 * 2713 * 4283
================================================================================
Naive SageMath codomain computation: 4.31377
Naive SageMath point evaluation: 0.40347

Optimised SageMath codomain computation: 1.54360
Optimised SageMath point evaluation: 0.26056

KummerLine codomain computation: 0.18248
KummerLine point evaluation: 0.13166

Updated SQISign Parameters

Using the prime $p_{3923}$ from the paper New algorithms for the Deuring correspondence: Towards practical and secure SQISign signatures by Luca De Feo, Antonin Leroux, Patrick Longa and Benjamin Wesolowski we get the following results:

================================================================================
Computing isogenies of degree: 2^33 * 5^21 * 7^2 * 11 * 31 * 83 * 107 * 137 *
751 * 827 * 3691 * 4019 * 6983
================================================================================
Naive SageMath codomain computation: 3.90661
Naive SageMath point evaluation: 0.38991

Optimised SageMath codomain computation: 1.00558
Optimised SageMath point evaluation: 0.17922

KummerLine codomain computation: 0.10415
KummerLine point evaluation: 0.02321

================================================================================
Computing isogenies of degree: 2 * 3^53 * 43 * 103^2 * 109 * 199 * 227 * 419 *
491 * 569 * 631 * 677 * 857 * 859 * 883 * 1019 * 1171 * 1879 * 2713 * 4283
================================================================================
Naive SageMath codomain computation: 4.20532
Naive SageMath point evaluation: 0.39591

Optimised SageMath codomain computation: 1.52446
Optimised SageMath point evaluation: 0.26089

KummerLine codomain computation: 0.17812
KummerLine point evaluation: 0.12469

BSIDH

Another example of where $x$-only isogenies are required is B-SIDH: supersingular isogeny Diffie-Hellman using twisted torsion by Craig Costello.

The file example_BSIDH.sage has two parameter sets which are Example 2 and Example 3 from the paper.

# Example 2
# p + 1 = 2^4 * 3 * 7^16 * 17^9 * 31^8 * 311 * 571 * 1321 * 5119 * 6011 * 14207 * 28477 * 76667 * 315668179
# p - 1 = 2 * 11^18 * 19 * 23^13 * 47 * 79 * 83 * 89 * 151 * 3347 * 17449 * 33461 * 51193 * 258434945441
p = 0x1935BECE108DC6C0AAD0712181BB1A414E6A8AAA6B510FC29826190FE7EDA80F

# Example 3
# p + 1 = 2^110 * 5 * 7^2 * 67 * 223 * 4229 * 9787 * 13399 * 21521 * 32257 * 47353 * 616228535059
# p - 1 = 2 * 3^34 * 11 * 17 * 19^2 * 29 * 37 * 53^2 * 97 * 107 * 109 * 131 * 137 * 197 * 199 * 227 * 251 * 5519 * 9091 * 33997 * 38201 * 460409 * 5781011
p = 0x76042798BBFB78AEBD02490BD2635DEC131ABFFFFFFFFFFFFFFFFFFFFFFFFFFF

BSIDH: Example 2 parameters

================================================================================
Computing isogenies of degree: 2^4 * 3 * 7^16 * 17^9 * 31^8 * 311 * 571 * 1321 *
5119 * 6011 * 14207 * 28477 * 76667
================================================================================
Naive SageMath codomain computation: 29.45755
Naive SageMath point evaluation: 2.97893

Optimised SageMath codomain computation: 2.50590
Optimised SageMath point evaluation: 0.56178

KummerLine codomain computation: 0.29879
KummerLine point evaluation: 0.09233

================================================================================
Computing isogenies of degree: 11^18 * 19 * 23^13 * 47 * 79 * 83 * 89 * 151 *
3347 * 17449 * 33461 * 51193
================================================================================
Naive SageMath codomain computation: 24.31294
Naive SageMath point evaluation: 2.38264

Optimised SageMath codomain computation: 2.03896
Optimised SageMath point evaluation: 0.44967

KummerLine codomain computation: 0.24272
KummerLine point evaluation: 0.07797

BSIDH: Example 3 parameters

================================================================================
Computing isogenies of degree: 2^110 * 5 * 7^2 * 67 * 223 * 4229 * 9787 * 13399
* 21521 * 32257 * 47353
================================================================================
Naive SageMath codomain computation: 29.58859
Naive SageMath point evaluation: 2.96113

Optimised SageMath codomain computation: 2.68519
Optimised SageMath point evaluation: 0.61415

KummerLine codomain computation: 0.33130
KummerLine point evaluation: 0.10982

================================================================================
Computing isogenies of degree: 3^34 * 11 * 17 * 19^2 * 29 * 37 * 53^2 * 97 * 107
* 109 * 131 * 137 * 197 * 199 * 227 * 251 * 5519 * 9091 * 33997 * 38201
================================================================================
Naive SageMath codomain computation: 19.96618
Naive SageMath point evaluation: 2.05993

Optimised SageMath codomain computation: 2.11092
Optimised SageMath point evaluation: 0.44078

KummerLine codomain computation: 0.24645
KummerLine point evaluation: 0.08013