# SIDH a quantum resistant algorithm for DH exchange

All algorithms that actually performs DH exchange are susceptible to be solved in polynomial time by a quantum computer: say based on discrete logarithm problem or based on elliptic curve point multiplication. Beside these, the other big algorithm that can perform public key encryption is RSA, which has its strength in the impossibility of factoring big numbers, but it also can be solved in polynomial time by a quantum computer. In fact, factoring is shown as an example of how a quantum computer works by means of the Shor’s algorithm.

A closer approach about quantum computing is given by the Github’s user arikalfus in her blog, with an interesting article series.

A plethora of public key algorithms resistant to quantum computation
are now feverly developed by mathematicians and cryptographers. Among them,
SIDH, by De Feo, Jao and Plût shines because
it is still based on elliptic curves.
**SIDH** stands for *Supersingular isogeny Diffie-Hellman interchange*.
The aim of this article is to provide a rough description of what
SIDH is, avoiding too technical wording (my apologies to mathematicians
and cryptographers if my language is not accurate enough).

# Some definitions

I assume that reader knows a bit about elliptic curves, how they are used in public key cryptography, and so on. However I remember that an elliptic curve is often expressed in its Weierstrass form, $E:\,y^2 = x^3 + a x + b$. An elliptic curve in cryptography is usually defined over a prime group such as $\mathbb{F}_p$, but also in a polynomial ring of order $m$, $\mathbb{F}_{p^m}$. For example, if $m=2$ it means that the field consist in polynomials of grade 1, which coefficients are given in $\mathbb{F}_p$, and with a grade 2 primitive reduction polynomial.

## j-invariant

It is a property of some mathematical objects, among them, elliptic curves. For a curve in Weierstrass form it is defined as

\[j(E) = 1728 \frac{4a^3}{4a^3 + 27b^2}\]Two curves are equivalent if both share the same j-invariant.

## Supersingularity

We have a supersingular elliptic curve if some internal properties are fulfilled. For the matter of this post, the interesting supersingular curves has j-invariant values 0 or 1728. So, either $a=0$ or $b=0$.

## Isogenies

An isogeny is an endomorphism that transforms a given curve to another
$\phi(E) \rightarrow E’$ where the curve order is conserved, $\#E = \#E’$.
It is driven by a point of the curve, say $R$, in
such a way that the image of point $R$ is the so called *point at infinity*,
$\phi(R) = \{0\}$, so
we can label the transform by the point, $\phi_R(E) \rightarrow E’$.

An isogeniy $\phi_R$ is expressed as a set of formulas (known as Velu’s formulas) depending on point $R$ that yields $\{a’,b’\}$ from $\{a,b\}$ and the transformation of any point $Q$ in $E$ to $Q’$ in $E’$. In principle, they consists in a bunch of field multiplications and divisions but repeated a numer of times equal to the point order of $R$, but there are strategies to reduce the overload (we will further see more about this).

In general, we can say that an isogeny is approximately as hard-computing as a point multiplication.

### The role of isogenies

Before plunging into details of SIDH, it is worthy to show roughly the role of isogenies in it.

Each agent of a DH interchange computes secretly a point $R$ as the kernel of an isogeny. Then the isogeny is applied to a known point $P$ and yields $P’$ in $E’$, what is made public.

It is hard to solve the kernel $R$ knowing $P$ and $P’$. For a
classical computer it can be solved in $\mathcal{O}(p^{1/4})$;
so, it is as hard as
the inversion of a point multiplication.
If we use a quantum computer the kernel can be solved in polynomial
time, $\mathcal{O}(\log\,p)$,
**except if the original curve, $E$, is supersingular**; then,
the difficulty of the problem rises to $\mathcal{O}(p^{1/6})$! That’s
the benefit of supersingular curves.

# SIDH description

In SIDH this latter idea is nuclear. Let’s see how.

The field used is based on a prime, $p$, of the form $ (\ell_A^{\,e_A})(\ell_B^{\,e_B})f \pm 1 $, where $\ell_A,\ell_B$ are small different primes (typically $\ell_A=2, \ell_B=3$) and $f$ is a small number that fulfils $\gcd(f,\ell_A)=1,\gcd(f,\ell_B)=1$. The exponents are chosen in such a way that both terms have similar size: $\ell_A^{\,e_A} \simeq \ell_B^{\,e_B}$.

We will focus in primes $p = 3\,\mathrm{mod}\,4$; so $p = (\ell_A^{\,e_A})(\ell_B^{\,e_B})f - 1 $ if $\ell_A = 2$ (if not, we can force $f = 0\,\mathrm{mod}\,4$ because it is interesting to conserve the “-1” form).

The field is chosen as $\mathbb{F}_{p^2}$ with the reduction primitive polynomial $X^2 + 1$ (it is primitive thanks to the election $p = 3\,\mathrm{mod}\,4$). Notice that this field has the same arithmetic as complex numbers; in fact, we can write the elements of the field as $a + bi$.

Now we define a supersingular curve over this field; for example, the simplest one:

\[y^2 = x^3 + x\]Its cardinality is $\#E = (p+1)^2 = (\ell_A^{\,e_A}\ell_B^{\,e_B}\cdot f)^2$; so, the curve has many cyclic subgroups. We are interested in $\ell_A^{\,e_A}$-torsion and $\ell_B^{\,e_B}$-torsion subgroups.

## Public bases

As in ECDH, it must be defined a fixed point of the curve. Actually there are 2 pairs of fixed points that are called A-base ($P_A,Q_A$) and B-base ($P_B,Q_B$), each with respective $\ell_A^{\,e_A}$ and $\ell_B^{\,e_B}$ point orders.

For the A-base we select a random seed point, $S_A$, then a $P_A$ candidate is calculated as $P_A = (\ell_B^{\,e_B}\cdot f)^2 S_A$. Then $P_A$ is probably a $\ell_A^{\,e_A}$-torsion point and we are done. If not, we search another seed point. Now we must select an independent A-base point, $Q_A$; the easiest way to do this is by applying a distortion map $\psi$ to $P_A$, defined as $\psi : (x,y) \rightarrow (-x,iy)$. So $Q_A = \psi(P_A)$.

The B-base is selected correspondingly: a seed point $S_B$ is chosen, then $P_B = (\ell_A^{\,e_A}\cdot f)^2 S_B$, etc.

So the partners of a SIDH interchange must share the following parameters that define the system: $\ell_A,\ell_B,e_A,e_B,f,P_A,Q_A,P_B,Q_B$.

## The interchange mechanism

Now we are ready to understand how SIDH works. As usual, the partners are Alice and Bob.

Alice uses A-base. She takes two random numbers $m_A,n_A$ (not both divisible by $\ell_A$) and computes

\[R = m_A P_A + n_A Q_A\]so $R$ is a $\ell_A^{\,e_A}$-torsion point; $m_A,n_A$ can be considered the Alice’s secret key; she also hides the point $R$. Alice now uses $R$ as the kernel of an isogeny and calculates a new curve $E_R = \phi_R (E)$ and the isogeny-driven image of the B-base, $\phi_R (P_B),\phi_R (Q_B)$. Now she sends the set $\{E_R,\phi_R (P_B),\phi_R (Q_B)\}$ to Bob.

In the mean time, Bob creates his own secret key $m_B,n_B$ (not both divisible by $\ell_B$), computes the secret point

\[T = m_B P_B + n_B Q_B\]Bob proceeds *mutatis mutandis* and sends the parameters
$\{E_T,\phi_T (P_A),\phi_T (Q_A)\}$ to Alice. She computes

also, the image of the curve, $E_{TR} = \phi_{R’} (E_T)$ and its j-invariant $j(E_{TR})$. Similarly, Bob computes

\[T' = m_B \phi_R (P_B) + n_B \phi_R (Q_B)\]and ends up with $E_{RT} = \phi_{T’} (E_R)$ and $j(E_{RT})$.

The trick is: **both curves are equivalent!** That is

so they can use this common j-invariant —Alice computes $j(E_{TR})$ and Bob computes $j(E_{RT})$— as the shared key for a symmetric encryption.

## Security

As I said, the security lies on the practical impossibility of isogeny inversion. So, although $\{\phi_R (P_B),\phi_R (Q_B)\}$ is send over an insecure channel (or even made public), the kernel $R$ is hard to be solved, even by a quantum computer (if $R$ is found, then the ECDH problem is easy to solve, because of the “smooth” cardinality of $R$, $\ell_A^{\,e_A}$, and the private key, $(m_A, n_A)$, can be revealed).

We can refine the estimation of isogeny inversion hardness exposed before: for a normal computer it is $\mathcal{O}(\min(\ell_A^{\,e_A/2}, \ell_B^{\,e_B/2}))$ and for a quantum computer, $\mathcal{O}(\min(\ell_A^{\,e_A/3}, \ell_B^{\,e_B/3}))$.

## Computation of isogenies

Along the post I talked about computing isogenies. This is a very tricky step, and I will sketch it very roughly (the topic deserves a full post).

As I said, in principle compute an isogeny is repeat some field operations (multiplications and divisions) as many times as the cardinality of the kernel point states. But if the cardinality is “smooth”, that is, if it is a compound of small numbers, then we can compound also “small” isogenies driven by these small numbers and they builds up the full isogeny.

But, by construction, the isogeny kernel is just a point with cardinality $\ell_A^{\,e_A}$ or $\ell_B^{\,e_B}$, so we deal with grained computation of $\ell_A$-isogenies (respective $\ell_B$-isogenies). This $\ell$-isogenies are “small” in the sense described above: they need a few number of field operations, so the smaller $\ell$, the fewer operations are needed.

And then, the number of $\ell$-isogenies needed to build up a $\ell^e$-isogeny grows polynomially with exponent $e$. We’ll need also some $\ell$-point multiplications which number also grows with $e$. The funny part is that the way to combine $\ell$-isogenies and $\ell$-point multiplications is not unique, but only few combinations are optimal regarding performance.

# Conclusion

In SIDH both partners share the j-invariant of a curve, calculated via two isogenies that are interchanged. The public knowledge of the interchanged curves does not allow to know the final j-invariant without the private multipliers used by the partners. If we want to break the security with a normal computer, the problem is as hard as ECDH; for a quantum computer the complexity is also exponential, but only if the base curve is supersingular.