Isogeny Based Cryptography

We introduce Isogeny based cryptography, one of the possible candidates for post-quantum cryptography. People may have heard the SIKE protocol have been broken CD22, but many other isogeny based cryptosystems, such as the CLG hash function CGL06 and SQISign SKLPW20 remains secure against the attack on SIDH. We begin with supersingular isogeny graph and its properties, then we describe several isogeny based cryptosystems.

Author(s): phamnhatminh1292001

Overview of Supersingular Isogeny Graph

In this chapter, we introduce supersingular isogeny graph and its properties to see why this graph is used in isogeny based cryptography. The vertices of the graph represent the supersingular elliptic curves, and the edges of the graph represent the isogenies between these curves. We will state the definitions of supersingular elliptic curves and isogenies, then describe the structure of the graph and its nice properties in cryptography.

Elliptic Curves

Definition

Let $K$ be a field. An elliptic curve $E$ is a plane curve defined over the field $K$ as follows: $E(K)=\\{y^2=x^3+ax+b : (x,y) \in K^2\\} \cup \\{O\\}$ where $(a,b) \in K^2$. The point $O$ is called the infinity point of the curve. The set $E(K)$ forms an abelian group with identity element $O$.

In addition, we need the curve to have no cusps, self-intersections, or isolated points. Algebraically, this can be defined by the condition $4a^3+27b^2 \neq 0$ in the field $K$.

The $j-$ invariant of an elliptic curve is defined to be $-1728\frac{4a^3}{4a^3+27b^2}$. Two elliptic curves are isomorphic to each other if and only if they have the same $j-$ invariant value.

The endomorphism ring of $E$ is denoted $End(E)$. The structure of $End(E)$ can be found in Chapter 3.9 of Silverman's book.

For an integer $n$, we define $E[n]=\\{(x,y) \in E(K) | n*(x,y)=O\\}$

Over a field $\mathbb{F}_p$, there are two types of curves: Ordinary and Supersingular, based on the set $E[p]$. We are interested in studying Supersingular curves, since the isogeny graph on these curves has nice structure and properties.

Isogenies

Definition

[Was08, Chapter XII.1] Let $E_1:y^2=x^3+a_1x+b_1$ and $E_2:y^2=x^3+a_2x+b_2$ be elliptic curves over a field $K$. An isogeny from $E_1$ to $E_2$ is a nonconstant homorphism $\alpha:E_1 \rightarrow E_2$ that is given by rational functions such that $\alpha(O)=O$.

This means $\alpha(P+Q)=\alpha(P)+\alpha(Q)$ for all $P,Q \in E_1$ and there exists rational functions $P, Q$ such that if $\alpha(x_1, y_1)=(P(x_1, y_1),Q(x_1, y_1))$.

In fact, it can be proved that we can write $\alpha$ in the form $\alpha(x_1, y_1)=(p(x_1), y_1q(x_1))$.

If $p(x)=\dfrac{r(x)}{s(x)}$ for polynomials $r$ and $s$ without common roots, define the degree of $\alpha$ to be $Max(deg(r(x)),deg(s(x)))$.

We say an isogeny is seperable if $s(x)$ have no repeated roots.

Example

Consider two curves $E_1:y^2=x^3+x$ and $E_2:y^2=x^3-4x$ over $\mathbb{F}_{11}$. Then the map $\alpha: E_1 \rightarrow E_2$ $(x,y) \mapsto \left(\dfrac{x^2+1}{x},\dfrac{y(x^2-1)}{x}\right)$ is an isogeny from $E_1$ to $E_2$.

Properties

We mention several important properties of isogenies.

1. Isogenies are uniquely determined by their kernel: Given an elliptic curve $E$ and a subgroup $L$, there is an unique elliptic curve $E'$ and an isogeny $\alpha: E \rightarrow E'$ such that the kernel of $\alpha$ is $L$.

2. [Sil09, Chapter III.6, Theorem 6.2] For every isogeny $\alpha: E \rightarrow E'$ of degree $l$, there exists an unique dual isogeny $\hat{\alpha}: E' \rightarrow E$ such that $\alpha \hat{\alpha}= \hat{\alpha} \alpha=l$

3. [Gha21, Proposition 2.2] (Decomposition of isogenies) Let $\alpha: E \rightarrow E'$ be a seperable isogeny. Then there exists an integer $k$ elliptic curves $E=E_0, E_1,...,E_n=E'$ and isogenies $\beta_i: E_i \rightarrow E_{i+1}$ of prime degree such that $\alpha=\beta_{n-1} \beta_{n-2} ... \beta_{0} [k]$

The edges of Supersingular isogeny graphs are determined by isogenies between the curves, we will talk about it later in the definition of the graph.

Supersingular Elliptic Curves

Definition

Let $p$ is a prime and let $q$ be a power of $p$. Let $E$ be an elliptic curve over $\mathbb{F}_q$. If $E[p]=O$, then $E$ is a Supersingular elliptic curve, if $E[p]=\mathbb{Z}/p\mathbb{Z}$ then $E$ is an Ordinary elliptic curve.

Example

For $p=3$, the curve $E: y^2=x^3-x$ is supersingular over the field $\bar{F}_3$. Here we see that $[3]*(x,y)=O$ for $(x,y) \neq O$ if and only if $3x^4-6x^2-1=0$, but such $x$ does not exist since $\bar{F}_3$ has characteristic $3$. Thus $E[3]=O$

Properties

Theorem [Sil09, Chapter V.3, Theorem 3.1] These following conditions are equivalent:

1. $E[p^r]=0$ for all $r \geq 1$.

2. $End(E)$ is an order in a quaternion algebra.

3. The map $[p]: E \rightarrow E$ is purely inseperable and $j(E) \in \mathbb{F}_{p^2}$.

As we see, all Supersingular elliptic curves are isomorphic to a curve in $F_{p^2}$, up to isomorphism, therefore the number of these curves are finite. It is natural that we want to count the number of these curves. Fortunately, we have a formula for the number of supersingular elliptic curves, as stated below:

Theorem. [Sil09, Chapter V.4, Theorem 4.1] The number of supersingular elliptic curves up to isomorphism is $\left\lfloor \dfrac{p}{12} \right\rfloor+z$, where

• $z=0$ if $p \equiv 1 \pmod{ 12}$

• $z=1$ if $p \equiv 5,7 \pmod{ 12}$

• $z=2$ if $p \equiv 11 \pmod{ 12}$

In the next chapter, we introduce the graph where the vertices are the Supersingular elliptic curves (up to isomorphism). This graph has several interesting properties that make it a candidate for constructing post quantum cryptosystems.

Supersingular Isogeny Graphs (Pizer Graphs)

Definition

Let $p$ be a prime number. For a prime $l \neq p$, a Supersingluar isogeny graph $\mathcal{G} _l (\mathbb{F} _{p ^2})$ is a graph whose vertices are the j-invariants of supersingular elliptic curves in $\mathbb{F} _{p ^2}$, and such that there is an edge from $j(E _1)$ to $j(E _2)$ if and only if there is an isogeny of degree $l$ from $E_1$ to $E_2$. There can be multiple edges from $j(E_1)$ to $j(E_2)$, the number of such edges is equal to the number of isogenies from $j(E_1)$ to $j(E_2)$.

Since each vertex represents a supersingular elliptic curve, the number of vertices in $\mathcal{G} _l (\mathbb{F} _{p ^2})$ is equal to $\lfloor \frac{p}{12} \rfloor + \epsilon$, where $\epsilon$ is defined in.

For these graph, we require $p \equiv 1 \pmod{ 12}$ so that we can pair an isogeny with its dual to make the graph regular and undirected Gha21.

Properties

The reason why Supersingular Isogeny Graphs are important lies in the following theorems:

Theorem. [CGL09, Theorem 4.1] For $p \equiv 1 \pmod{ 12}$ and $l \neq p$ , the graph $\mathcal{G} _l(\mathbb{F} _{p^2})$ is connected, and is a $l+1$ regular graph.

Theorem. [CGL09, Theorem 4.2] For $p \equiv 1 \pmod{ 12}$ and $l \neq p$ the graph $\mathcal{G} _l(\mathbb{F} _{p^2})$ are Ramanujan graphs.

We give an overview about Ramanujan graphs. They are optimal expander graph. There are two nice properties of this type of graph. First, relatively short walk on this graph approximate the uniform distribution, which is good for a source of randomness. This can be seen by the following theorem:

Theorem. Let $N_{l,p}$ denote the number of vertices of $\mathcal{G} _l(\mathbb{F} _{p ^2})$ .Fix a supersingular $j_1 \in \mathbb{F} _{p^2}$, and let $j_2$ be the endpoint of a walk of length $e$ orginating at $j_1$. Then for all $j \in \mathbb{F} _{p^2}$:

$|Pr[j=j_2]-N_{l,p}^{-1}| \leq \left(\dfrac{2\sqrt{l}}{l+1}\right)^e$

The other nice property of Ramanujan graph is that the path-finding problem is assumed to be hard on this graph, which is good for constructing a cryptographic hash function. Two types of Ramanujan are proposed in CGL06, LPS Graph and Supersingular Isogeny Graphs. However, the LPS hash function was attacked and broken in 2008 TZ08 PLQ08, leaving the Supersingular Isonegy Graph as the ruling graph.

The adjacency matrix of $\mathcal{G} _l(\mathbb{F} _{p^2})$ is the Brandt matrix $B(l)$. More informations of the matrix can be found in Voight's book. The matrix allow us to specify all primes $p$ so that the graph does not have short cycles Gha21, an important property to ensure the hardness of the path-finding problem of the graph CGL06.

Applications of Pizer Graphs

Supersingular Isogeny Graph has applications in both mathematics and cryptography. We list several of their applications below.

1. In mathematics Supersingular Isogeny Graph is used in the following computational problems:

   1. The endomorphism ring computation problem: Given $p$ and a supersingular $j$-invariant $j$, compute the endomorphism ring of $E(j)$ EHLMP18.
   2. The Deuring correspondence problem: Given a maximal order
      $A \in B_{p,\inf}$, return a supersingular j-invariant such that the endomorphism ring $E(j)$ is isomorphic to $A$ EHLMP18.

2. In cryptography Supersingular Isogeny Graph is used in encryption scheme MOT20, signature scheme SKLPW20, hash function CGL06, verifiable delay function LMPS19. These schemes are secure against the attack on SIKE.