CSIDH

For this blogpost we will assume knowledge of

• Preview blogpost on Isogenies for Cryptography

• Optional: Previous blogpost on SIDH

We will also need a basic understanding of ideal class groups.

Ideal Class Groups

We briefly introduce ideal class groups in the context needed for CSIDH. For a more general treatment and precise definition, the reader is encouraged to refer to ‘Primes of the form $x^2 + ny^2$: Fermat, Class Field Theory, and Complex Multiplication’ by Cox. We consider a supersingular curve $E$ over $\mathbb{F}_p$ with End($E$) having a subring $\mathcal{O} := \mathbb{Z}[\pi]$, where $\pi$ is the Frobenius endomorphism.

The norm of an $\mathcal{O}$-ideal $\mathfrak{a} \subseteq \mathcal{O}$ is defined as $N(\mathfrak{a}) = \mid \mathcal{O}/\mathfrak{a} \mid$ and is equal to gcd{$N(\alpha) \mid \alpha \in \mathfrak{a}$}. Norms are multiplicative, meaning $N(\mathfrak{a}\mathfrak{b}) = N(\mathfrak{a})N(\mathfrak{b})$.

A fractional $\mathcal{O}$-ideal is an $\mathcal{O}$-submodule of End($E$) of the form $\alpha \mathfrak{a}$, with $\alpha \in \text{End}(E)$ non-zero and $\mathfrak{a}$ an $\mathcal{O}$-ideal. A fractional $\mathcal{O}$-ideal $\mathfrak{a}$ is invertible if there exists a $\mathcal{O}$-fractional ideal $\mathfrak{b}$ such that $\mathfrak{a}\mathfrak{b} = \mathcal{O}$. All principal fractional $\mathcal{O}$-ideals, i.e. ideals of the form $\alpha \mathcal{O}$, are invertible. The sets of invertible fractional $\mathcal{O}$-ideals, $I(\mathcal{O})$, and principal fractional $\mathcal{O}$-ideals, $P(\mathcal{O})$, form groups. We can, therefore, define the ideal class group of $\mathcal{O}$ as the quotient

\[cl(\mathcal{O}) := I(\mathcal{O})/P(\mathcal{O})\]

Hard Homogenous Spaces

A hard homogeneous space ¹ is an efficiently computable action $\star: G \times S \rightarrow S$ of a finite commutative group $G$ on a set $S$, with the following propoerties:

• it’s free: for all $s \in S$, $gs = s$ implies $g$ is the identity.

• it’s transitive: for every pair of elements $s_0$ and $s_1$, there is a group element $g$ such that $gs_0 = s_1$.

• the parallelization problem is hard: given $s_0, s_1, s_2 \in S$, it should be infeasible to find $g_1g_2 \star s_0$, where $g_1, g_2 \in S$ are such that $s_1 = g_1 \star s_0$ and $s_2 = g_2 \star s_0$.

This generalizes the notion of a cyclic group in which the Diffie-Hellman problem is hard. Indeed, any such space gives rise to a Diffie-Hellman-like protocol. The main appeal of hard homogeneous spaces is due to the potential for them to give post-quantum cryptographic schemes. This is because, whilst Shor’s developed a polynomial-time quantum attack against the exponentiation-based Diffie-Hellman, in the more general setting the best attack is Kuperberg’s subexponential-time hidden shift attack.

Apart from exponentiation, currently we only know one other candidate hard homogenous space: isogeny-based actions by ideal-class groups on sets of elliptic curves over finite fields. The first use of this to create cryptographic schemes was proposed independently by Couveignes ¹ and Rostovtsev-Stolbunov ². However, they considered ordinary elliptic curves, which led to an extremely slow scheme. Even despite speed-ups due to De Feo, Kieffer and Smith ³, several minutes are needed for one key exchange with 128-bit classical security. Due to the simplicity and flexibility of the Couveignes-Rostovtsev-Stolbunov scheme, Castryck, Lange, Martindale, Panny and Renes ⁴ constructed a similar scheme using supersingular elliptic curves called CSIDH (pronounced seaside). They let $S$ be the set of supersingular elliptic curves $E$ defined over $\mathbb{F}_p$ (up to $\mathbb{F}_{p}$-isomorphism). Then, restricting to $\mathbb{F}_p$, we get endomorphism ring End$_{\mathbb{F}_p}(E)$ whose corresponding ideal class group $G$ is commutative. For an ideal class $[\mathfrak{a}] \in G$ and $E \in S$ we get the action $[\mathfrak{a}] \star E$, which defines an elliptic curve $E/\mathfrak{a} \in S$ and an isogeny $\phi_{\mathfrak{a}}: E \rightarrow E/\mathfrak{a}$, defined over $\mathbb{F}_p$. The CSIDH paper showed this gives a hard homogeneous space ², so Couveignes’ framework ¹ can be applied to supersingular isogeny-based cryptography, giving us, for example, a non-interactive Diffie-Hellman-like key exchange.

Non-Interative Key Exchange Protocol

Set-up: Let $p = 4\cdot l_1\cdots l_n - 1$ be a large prime, with $l_i$ small distinct odd primes, such that $p \equiv 3 \mod 8$. Fix supersingular curve $E_0: y^2 = x^3 + x$ over $\mathbb{F}_{p}$. This has End$_{\mathbb{F}_p}(E_0) = \mathbb{Z}[\sqrt{-p}]$.

Key Generation: The secret key is the ideal class $\texttt{sk} = [\mathfrak{a}]$. In CSIDH, for efficient evaluation of the action, $[\mathfrak{a}]$ is a product of small norm ideals. The public key is $\texttt{pk} = [\mathfrak{a}] \star E_0 =: E_A$.

Key Exchange: Suppose Alice and Bob have public/secret key pairs $(E_A, [\mathfrak{a}])$ and $(E_B, [\mathfrak{b}])$. On receiving $E_B$, Alice verifies it is defined over $\mathbb{F}_{p}$ with End$_{\mathbb{F}_{p}}(E_B) = \mathbb{Z}[\sqrt{-p}]$. If so, she computes the action $[\mathfrak{a}]\star E_B = [\mathfrak{a}]\star [\mathfrak{b}]\star E_0$. Bob proceeds analogously to get $[\mathfrak{b}]\star [\mathfrak{a}]\star E_0$. Commutativity of $G$ ensures

\[[\mathfrak{b}]\star [\mathfrak{a}]\star E_0 = [\mathfrak{a}]\star [\mathfrak{b}]\star E_0\]

so this can be used as their secret shared key.

Security

The security of CSIDH is based on the hardness of the CSSDDH problem, defined below.

Commutative SSDDH (CSSDDH) Problem:

Let $p$, $E_0$ be as the CSIDH set-up. Given a tuple sampled with probability $\frac{1}{2}$ from one of the following two distributions

• ($E_0$, $[\mathfrak{a}]\star E_0$, $[\mathfrak{b}] \star E_0$, $[\mathfrak{a}]\star [\mathfrak{b}]\star E_0$)
• ($E_0$, $[\mathfrak{a}]\star E_0$, $[\mathfrak{b}] \star E_0$, $[\mathfrak{c}]\star E_0$)

where $[\mathfrak{a}], [\mathfrak{b}], [\mathfrak{c}]$ are random elements from End$_{\mathbb{F}_p}(E_0)$, determine from which distribution the tuple is sampled. We remark that the ideal classes have a special form, as described in §4.1, so the sampling method is not uniform.

No torsion-point images are published during the protocol, meaning it will be immune to any attacks that make use of this extra information, for example the attack by Petit on SIDH-like constructions ⁵. Nevertheless, in CSIDH the key spaces are also limited to around $\sqrt{p}$ supersingular points, giving us a classical attack of $\tilde{O}(p^{1/4})$. In August 2020, Colò and Kohel proposed OSIDH ⁶. This combines CSIDH and SIDH, but is defined over arbitrarily large subset of oriented supersingular elliptic curves over $\mathbb{F}_{p^2}$, which covers essentially all possible corresponding $j$-invariants. As a result, there is no limit to size of key space. OSIDH, however, needs further security analysis and research into implementation before becoming a viable alternative to CSIDH or SIDH.

The commutativity of $G$ in CSIDH allows for hidden shift quantum attacks that are asymptotically sub-exponential. Implicit constants in attack complexities, the infeasibility of long sequential quantum operations and the large memory requirements are therefore taken into account to find quantum secure CSIDH parameters. The original CSIDH paper proposed parameter sets $\texttt{CSIDH-512}$, $\texttt{-1024}$ and $\texttt{-1792}$, giving NIST 1-3 level security, respectively ². Recent strides in the quantum cryptanalysis of CSIDH by Peikert ⁷ and Bonnetain and Schrottenloher ⁸ have called these parameter sets into question.

Efficiency

The choice of $E_0$ means $[\mathfrak{a}] \star E_0$ can be represented in Montgomery form $y^2 = x^3 + Ax^2 + x$ for any $[\mathfrak{a}] \in G$, so it suffices to specify the coefficient $A \in \mathbb{F}_p$. Pairing this with a space-efficient representation of $[\mathfrak{a}]$, CSIDH has small keys compared to SIDH, which is currently the NIST submission with the smallest combined key and ciphertext length. However, it is slow. Considering NIST level 1 parameters, it takes around 80ms compared to 10ms for SIDH ⁹.

To increase the speed of the protocol, Castryck and Decru considered taking prime $p \equiv 7 \mod 8$ ¹⁰. Elliptic curves are can now be represented in the form $y^2 = x^3 +Ax^2 -x$ and there are two possible endomorphism rings. Proposed NIST level 1 secure parameters $\texttt{CSURF-512}$, give a speed-up of about 5.68% compared to $\texttt{CSIDH-512}$ when sampling from a specific set up. As highlighted above, the parameter sets may beed to be reconsidered, which may decrease efficiency. Therefore, advancements in this area are highly desirable for CSIDH to compete with other post-quantum secure key-exchange protocols.