Supersingular Elliptic Curves in Cryptography

Since old times cryptography has been present in our lifes, but it had deep development during the second world war. At middle 70's Whitfield Diffie and Martin Hellman presented a protocol of key exchanged using exponentiation in groups. At middle 90's Peter Shor proposed an algorithm to break Diffie-Hellman based in supersingular elliptic curves resistant against quantum attacks. In 2010 Jao-De Feo build key exchange using graphs of isogenies.

$\textbf{Diffie-Hellman key exchange using actions on groups}$
The protocol Diffie-Hellman give a way to get a common key between two users. Here we give a version of Diffie-Hellman using action on groups.

$\textrm{Definition}$ (Action of a group on a set)
Let $(G,\cdot)$ be a group and a set $X$ non empty, then we say $\varphi :G\times X \rightarrow X$ denoted by $(g,x)\mapsto g*x$ is an action of $G$ on $X$ if $e*x=x$ and $g*(h*x)=(g\cdot h)*x \ \forall g,h\in G \ and \ x\in X$.

Suppose Anna and Bob want to have a common private key.
Then they use an abelian group $(G,\cdot)$ acting in $X$. Both has a public key $x_0\in X$. To get a common key they have to do next:
-Anna chooses a private key $a\in G$ and Bob chooses his private key $b\in G$.
-Then, Anna sends $a*x_0$ to Bob, and Bob sends $b*x_0$ to Anna.
-So, Anna and Bob can get the common key
\begin{equation}
 a*(b*x_0)=(a\cdot b)*x_0=b*(a*x_0)
\end{equation}Check that is relatively easy compute $a*x_0$ but is more difficult compute $a$ given $a*x_0$ (similar problem to the discrete logarithm).

$\textbf{Endomorphism ring of an elliptic curve}$
Remember that an Elliptic curve over a field $K$ is a pair $(E,O)$ where $E$ is a non singular algebraic curve of gender 1 defined over $K$ and $O$ is a fixed point of $E$. To express the last, we just write $E/K$.
Check that in the notation we don't make reference to the point $O$, since that is not important because we have the same structure of an elliptic curve doing a translation. So, in many papers $O$ is the point to infinity, because we can see an elliptic curve in its affine form (see the next paragraph) adding its point to infinity.

Even more, an elliptic curve over a field $K$ with $\mathrm{char}(K)\neq 2,3$ has associated a Waierstrass' equation:
\begin{equation}
y^2=x^3+Ax+B \ \ \ with  \ \ A,B\in K
\end{equation}The set of $K$-rational points of last equation is denoted by $E(K)$ and It has an abelian group structure with an operation of geometric origin.

So, an isogeny $\varphi$ of elliptic curves (from $E_1$ to $E_2$) will be for us a morphism non constant $\varphi: E_1 \rightarrow E_2$ such that $\varphi (O_1)=O_2$. So, if $E_1=E_2$, then called the endomorphism ring of $E_1$ to the set $End(E_1)=\{\varphi :E_1\rightarrow E_1 : \varphi \ is \ an \ isogeny \}$. One has to check morphisms are just homomorphisms between rational point sets.

One remarkable fact is when we work over a specific field, for example $K=\mathbb{F}_p$, then we denoted $End_{\mathbb{F}_p}(E_1)$ as all isogenies such that can be written using coefficients in $\mathbb{F}_p$. So $End(E_1)$ is a bigger ring. The importance of emphasizing the above is the next important result.

\begin{equation}
"Let \ E/\mathbb{F}_p \ be \ an \ elliptic \ curve. \ Then \ End_{\mathbb{F}_p}(E) \ is \ isomorphic \ to \ an \ imaginary \ quadratic \ order." \\
\ So \ End_{\mathbb{F}_p}(E) \ is \ a \ commutative \ ring.
\end{equation}
Some important morphisms are next.
Let $E/K$ an elliptic curve with $\mathrm{char}(K)=p$.

• $\textrm{The multiplication morphism}$: Let $n\in \mathbb{Z}$ be, then the map $[n]: E\rightarrow E$ given by $[n](P):=\underbrace{P + \cdots +P}_{n-times}$. So we can check that $\mathbb{Z}$ is isomorph to the set of multiplication morphisms.

• $\textrm{Frobenius' morphism}$: 

\begin{equation}
\pi: E \rightarrow E
\end{equation}\begin{equation}
(x,y)\longmapsto (x^p,y^p)
\end{equation}So, we have the next chain of contentions

$\mathbb{Z}[\pi]\subset End_{K}(E)\subset O_{\mathbb{Q}(\pi)} \longrightarrow $maximal order

$\textbf{Ideal class group}$
Consider an imaginary quadratic order $O$ and $I_1,I_2\subset O$ two ideals, then we say those are equivalent if there exist $\alpha,\beta \in O \setminus \{0\} $ such that $<\alpha>\cdot I_1 =\ <\beta> \cdot I_2$, i.e. they are the same module principal ideals.
With this ideal multiply we can multiply equivalence classes. If $I_1 \sim J_1$ and $I_2 \sim J_2$ then $I_1\cdot I_2 \sim J_1 \cdot J_2$.

The $\textit{ideal class group}$ of $O$ is defined as:

$Cl(O):=\{equivalence \ classes \ of \ non \ zero \ ideals \ I \subset O \ not \ containing \ conductor\}$

Backing to talk of elliptic curves, one result very important in elliptic curves is the next.

"Let $E_1/K$ be an elliptic curve and $H$ a subgroup of $E_1$, then there exist $E_2/K$ (where $\ E_2$ is denoted by $E_1/H$) and an isogeny $\varphi : E_1 \rightarrow E_2$ with kernel $K$".

They both $\varphi,E_2$ are defined over $K$, and if we restrict to separable isogenies then $E_2$ is unique up to $K$-isomorphism.

...............We are working..............