Supersingular isogeny key exchange

These are public parameters that can be shared by everyone in the network, or they can be negotiated by parties A and B at the beginning of a session.

1. A prime of the form ${\displaystyle p=w_{A}^{e_{A}}\cdot w_{B}^{e_{B}}\cdot f\pm 1.}$
2. A supersingular elliptic curve ${\displaystyle E}$ over ${\displaystyle \mathbb {F} _{p^{2}}}$.
3. Fixed elliptic points ${\displaystyle P_{A},Q_{A},P_{B},Q_{B}}$ on ${\displaystyle E}$.
4. The order of ${\displaystyle P_{A}}$ and ${\displaystyle Q_{A}}$ is ${\displaystyle (w_{A})^{e_{A}}}$. The order of ${\displaystyle P_{B}}$ and ${\displaystyle Q_{B}}$ is ${\displaystyle (w_{B})^{e_{B}}}$.

In the key exchange, parties A and B will each create an isogeny from a common elliptic curve E. They each will do this by creating a random point in what will be the kernel of their isogeny. The kernel of their isogeny will be spanned by ${\displaystyle R_{A}}$ and ${\displaystyle R_{B}}$ respectively. The different pairs of points used ensure that parties A and B create different, non-commuting, isogenies. A random point (${\displaystyle R_{A}}$, or ${\displaystyle R_{B}}$) in the kernel of the isogenies is created as a random linear combination of the points ${\displaystyle P_{A}}$, ${\displaystyle Q_{A}}$ and ${\displaystyle P_{B}}$, ${\displaystyle Q_{B}}$.

Using ${\displaystyle R_{A}}$, or ${\displaystyle R_{B}}$, parties A and B then use Velu's formulas for creating isogenies ${\displaystyle \phi _{A}}$ and ${\displaystyle \phi _{B}}$ respectively. From this they compute the image of the pairs of points ${\displaystyle P_{A}}$, ${\displaystyle Q_{A}}$ or ${\displaystyle P_{B}}$, ${\displaystyle Q_{B}}$ under the ${\displaystyle \phi _{B}}$ and ${\displaystyle \phi _{A}}$ isogenies respectively.

As a result, A and B will now have two pairs of points ${\displaystyle \phi _{B}(P_{A})}$, ${\displaystyle \phi _{B}(Q_{A})}$ and ${\displaystyle \phi _{A}(P_{B})}$, ${\displaystyle \phi _{A}(Q_{B})}$ respectively. A and B now exchange these pairs of points over a communications channel.

A and B now use the pair of points they receive as the basis for the kernel of a new isogeny. They use the same linear coefficients they used above with the points they received to form a point in the kernel of an isogeny that they will create. They each compute points ${\displaystyle S_{BA}}$ and ${\displaystyle S_{AB}}$ and use Velu's formulas to construct new isogenies.

To complete the key exchange, A and B compute the coefficients of two new elliptic curves under these two new isogenies. They then compute the j-invariant of these curves. Unless there were errors in transmission, the j-invariant of the curve created by A will equal to the j-invariant of the curve created by B.

Notationally, the SIDH key exchange between parties A and B works as follows:

1A. A generates two random integers ${\displaystyle m_{A},n_{A}<(w_{A})^{e_{A}}.}$

2A. A generates ${\displaystyle R_{A}:=m_{A}\cdot (P_{A})+n_{A}\cdot (Q_{A}).}$

3A. A uses the point ${\displaystyle R_{A}}$ to create an isogeny mapping ${\displaystyle \phi _{A}:E\rightarrow E_{A}}$ and curve ${\displaystyle E_{A}}$ isogenous to ${\displaystyle E.}$

4A. A applies ${\displaystyle \phi _{A}}$ to ${\displaystyle P_{B}}$ and ${\displaystyle Q_{B}}$ to form two points on ${\displaystyle E_{A}:\phi _{A}(P_{B})}$ and ${\displaystyle \phi _{A}(Q_{B}).}$

5A. A sends to B ${\displaystyle E_{A},\phi _{A}(P_{B})}$, and ${\displaystyle \phi _{A}(Q_{B}).}$

1B - 4B: Same as A1 through A4, but with A and B subscripts swapped.

5B. B sends to A ${\displaystyle E_{B},\phi _{B}(P_{A})}$, and ${\displaystyle \phi _{B}(Q_{A}).}$

6A. A has ${\displaystyle m_{A},n_{A},\phi _{B}(P_{A})}$, and ${\displaystyle \phi _{B}(Q_{A})}$ and forms ${\displaystyle S_{BA}:=m_{A}(\phi _{B}(P_{A}))+n_{A}(\phi _{B}(Q_{A})).}$

7A. A uses ${\displaystyle S_{BA}}$ to create an isogeny mapping ${\displaystyle \psi _{BA}}$.

8A. A uses ${\displaystyle \psi _{BA}}$ to create an elliptic curve ${\displaystyle E_{BA}}$ which is isogenous to ${\displaystyle E}$.

9A. A computes ${\displaystyle K:={\text{ j-invariant }}(j_{BA})}$ of the curve ${\displaystyle E_{BA}}$.

6B. Similarly, B has ${\displaystyle m_{B},n_{B},\phi _{A}(P_{B})}$, and ${\displaystyle \phi _{A}(Q_{B})}$ and forms ${\displaystyle S_{AB}=m_{B}(\phi _{A}(P_{B}))+n_{B}(\phi _{A}(Q_{B}))}$.

7B. B uses ${\displaystyle S_{AB}}$ to create an isogeny mapping ${\displaystyle \psi _{AB}}$.

8B. B uses ${\displaystyle \psi _{AB}}$ to create an elliptic curve ${\displaystyle E_{AB}}$ which is isogenous to ${\displaystyle E}$.

9B. B computes ${\displaystyle K:={\text{ j-invariant }}(j_{AB})}$ of the curve ${\displaystyle E_{AB}}$.

The curves ${\displaystyle E_{AB}}$ and ${\displaystyle E_{BA}}$ are guaranteed to have the same j-invariant. A function of ${\displaystyle K}$ is used as the shared key.[3]