In this blog post, I will introduce CSIDH as a motivational example for the next post. We will cover eigen{values, spaces} of the Frobenius, how Elkies primes appear in CSIDH, and how they lead to a simple implementation in Sage.

What does “C” mean in CSIDH?

CSIDH, which stands for Commutative Supersingular Isogeny Diffie-Hellman and pronounced as [“si:saId] (seaside 🌊), is another simple isogeny-based key exchange protocol. CSIDH is a group action-based cryptography protocol, a term that we will define later. Despite the similarity in their names, SIDH and CSIDH rely on drastically different theory, as we will see soon. In SIDH, extra information is exchanged to allow the parties to compute the pushforward image of the private kernel point. This is different from say, (commutative) group-based Diffie-Hellman, where both parties can simply compute \((g^a)^b = (g^b)^a\) without any problem. This is because the actions \(g \mapsto g^a\) and \(g \mapsto g^b\) commute, while \(E \mapsto E / A\) and \(E \mapsto E / B\) don’t (the pushforward image differs). CSIDH resolves the problem SIDH faces by working with a commutative group action. Intuitively, this means the action (i.e. the arrows in the Diffie-Hellman square) commutes in a way that allows for group-based Diffie-Hellman construction, allowing the two parties to just exchange (the equivalent of) \(g^a\) and \(g^b\) without extra information.

Group Actions

Recall that a group Written multiplicatively is a tuple \((G, \cdot : G \to G \to G)\) such that the associativity, identity and inverse axioms hold. A group action is very similar, except that instead of \(\cdot\) being a binary operator on \(G\) acting on itself, it is now an action \(\alpha : G \times X \to X\) acting on a set \(X\), satisfying compatibility (\(\alpha(g, \alpha(h, x)) = \alpha(g \cdot h, x)\)) and identity axioms. We say a group action is commutative if \(\alpha(g, \alpha(h, x)) = \alpha(h, \alpha(g, x))\). From now on, we simply write \(g \cdot x\) or \(gx\) instead of \(\alpha(g, x)\).

An example would be the symmetric group \(S_n\): on its own, \(S_n\) as a group turns permutations into other permutations. However, we can view \(S_n\) as a group acting on any ordered list \(X\) of \(n\) elements, where the group action permutes the list according to the permutation element. As we will see later, in the setting of CSIDH, we have ideal (classes) acting on certain elliptic curves. This means we roughly have a commutative group action

\[ \alpha : \{ \mathrm{ideals} \} \times \mathcal{Ell} \to \mathcal{Ell} \]

From the definition of group action, we see that it behaves quite similarly to normal groups. Most importantly, we notice that we can adapt the commutative group-based Diffie-Hellman \((g^a)^b = (g^b)^a\) into a commutative group action-based Diffie-Hellman \(\alpha(b, \alpha(a, g)) = \alpha(a, \alpha(b, g))\). This is what CSIDH is based on, and thus for the remaining of this post we will investigate (1) what \(G\) and \(X\) is in the definition \(\alpha : G \times X \to X\), and (2) how to evaluate this group action. This is the power of group actions: it is a generic abstract framework that allows us to build primitives on top of.

Frobenius Endomorphism

Before we begin our actual journey, we first have to introduce the Frobenius endomorphism A map from a structure to itself . Consider any finite field \(K = \mathbb{F}_q\). We define the Frobenius endomorphism to be the map \(\pi : \overline{\mathbb{F}_q} \to \overline{\mathbb{F}_q}\), defined by \(\pi(x) = x^q\). Let \(x \in \mathbb{F}_q\) be any element. By considering the case \(x = 0\) separately and looking at the unit group order, we can see that for any \(x\), we have \(x^q = x\). This means that \(\pi\) actually fixes \(K\). Of course, this is not true for elements \(x \in \overline{\mathbb{F}_q} \setminus \mathbb{F}_q\). Another property we need is that for elements \(x, y \in \mathbb{F}_q\), we have \(\pi(x) + \pi(y) = \pi(x + y)\). This is often called the Freshman’s Dream, but nowadays it should be updated to middle schooler’s dream, and proves that \(\pi\) is indeed a homomorphism.

Furthermore, this definition extends naturally to points on elliptic curves. Let \(E\) be an elliptic curve over a finite field \(K = \mathbb{F}_q\). Then, for \(P = (x, y) \in E(K)\), we also have \(\pi(y)^2 = \pi(x)^3 + a\pi(x) + b\), meaning that the map \((x, y) \mapsto (x^q, y^q)\) is an endomorphism too. We also call this the Frobenius endomorphism. This endomorphism serves an immense amount of importance in isogeny-based cryptography, or even in Mathematics. For example, to compute the quantity \(|E(K)|\), instead of counting the points (which is hard to control), we can compute the number of fixed points More specifically, we can write this as \(|E(K)| = |\ker(1 - \pi)|\) and apply tools from algebraic topology etc. of \(\pi\) on \(E\). This allows all kinds of Mathematical tools to be applied, see e.g. Lorenz’s Masters thesis.

Next, let us introduce this important theorem about the Frobenius endomorphism:

Note that the equation in (1.) is a strong condition, as it is stating that the endomorphism on the left hand side equals zero “literally”, not just on \(E(K)\). In other words, \((\pi^2 - t\pi + q)(P) = O\) even for \(P \in E(\overline{K}) \setminus E(K)\).

Let’s look at an example. Consider the curve \(E: y^2 = x^3 + x + 1\) over \(K = \mathbb{F}_q\) where \(q = 107^2\). Its Frobenius endomorphism is \(\pi: (x, y) \mapsto (x^{107^2}, y^{107^2})\). It can then be shown that \(\pi^2 + 205\pi + q = 0\). This means that for any point \(P \in E = E(\overline{K})\), we have \(\pi(\pi(P)) + [205]\pi(P) + [q](P) = O\). We can verify the claims in Sage. First, we can extract the Frobenius polynomial using .frobenius_polynomial():

sage: E = EllipticCurve(GF((107, 2)), [1, 1])
sage: E.frobenius_polynomial()
x^2 + 205*x + 11449

sage: pi = E.frobenius_endomorphism(); pi
Frobenius endomorphism of degree 11449 = 107^2:
  From: Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field in z2 of size 107^2
  To:   Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field in z2 of size 107^2
sage: pi.characteristic_polynomial()
x^2 + 205*x + 11449

We can then evaluate it on random points of \(E\). We have to pass in the degree \(2\) into .frobenius_isogeny, since it returns the absolute Frobenius (i.e. \((x, y) \mapsto (x^p, y^p)\) by default.

sage: E1 = E.change_ring(GF((107, 6)))
....: pi = E1.frobenius_isogeny(2)
....: for _ in range(100):
....:     P = E1.random_point()
....:     assert pi(pi(P)) + 205 * pi(P) + 11449 * P == 0

(Currently you cannot directly add endomorphisms, but there is work in progress for it… I think.)

This theorem suggests a connection between the Frobenius endomorphism and imaginary quadratic fields.

Describing the Group Action

To describe the group action, it is simplest to quote directly from the CSIDH paper, Theorem 7:

Group Action? Where are Isogenies?

From here, we can finally begin to describe CSIDH. As the name suggests, we will be basing our key exchange protocol on a commutative group action, acting on certain supersingular elliptic curves. We first determine in “Parameter Choice 1” an appropriate \(p\) (which determines \(\pi\) via \(\pi^2 + p = 0\)) and an imaginary quadratic order \(\mathcal{O}\), along with a public starting curve \(E_0 \in \mathcal{Ell}_p(\mathcal{O}, \pi)\). With these parameters, we then look at when the group action \((\mathfrak{a}], E) \mapsto E / \mathfrak{a}\) is efficiently computable. We will discover a link with the so-called Elkies primes, which will lead us to the parameter choice of the acting set generators \(X \subseteq \mathrm{Cl}(\mathcal{O})\).

Parameter Choice 1

Elkies Primes

Parameter Choice 2

For no reason, here’s a song I like recently.