# On the Performance Analysis for CSIDH-Based Cryptosystems
## 3 CSIDH-Based Schemes
### Csidh  
CSIDH is an isogeny-based Diffie-Hellman protocol proposed by [PERSON] et al. [6] using supersingular curves defined over \(\mathbb{F}_{p}\) and commutative group action. The prime \(p\) of the base field is of the form \(p=4\prod_{i=1}^{n}\ell_{i}-1\), where \(\ell_{i}\)'s are odd primes. For an order \(\mathcal{O}=\operatorname{End}_{\mathbb{F}_{p}}(E)\), it is well-known that the class group \(\operatorname{cl}(\mathcal{O})\) acts freely and transitively on \(\mathcal{E}\ell\ell_{p}(\mathcal{O})\), where \(\mathcal{E}\ell\ell_{p}(\mathcal{O})\) is the set of elliptic curves \(E\) defined over \(\mathbb{F}_{p}\) with \(\operatorname{End}_{\mathbb{F}_{p}}(E)=\mathcal{O}\). This group action is represented by \([\mathsf{a}]E\), where \(E\in\mathcal{E}\ell\ell_{p}(\mathcal{O})\) and an ideal class \([\mathsf{a}]\in\operatorname{cl}(\mathcal{O})\). Since \(E\) is a supersingular curve with \(\#E(\mathbb{F}_{p})=p+1=4\cdot\ell_{1}\cdots\ell_{n}\), for each \(i\), there is \(\mathbb{F}_{p}\)-rational subgroup of order \(\ell_{i}\). Moreover, let \(\pi=\sqrt{-p}\) be the \(\mathbb{F}_{p}\)-Frobenius endomorphism of \(E\). Then, since \(p=-1\mod\ell_{i}\), for a prime \(\ell_{i}\), it is well-known that \(\ell_{i}\mathcal{O}\) splits into two prime ideals \(\mathfrak{l}_{i}=(\ell_{i},\pi-1)\) and \(\mathfrak{l}_{i}^{-1}=(\ell_{i},\pi+1)\). Using [PERSON]'s formula, we compute \([\mathfrak{l}_{i}]E\) through the isogeny \(\phi_{\mathfrak{l}_{i}}\) with the kernel generated by a point of order \(\ell_{i}\), which lies in the kernel of \(\pi-1\) and compute \([\mathfrak{l}_{i}^{-1}]E\) through the isogeny \(\phi_{\mathfrak{l}_{i}^{-1}}\) with the kernel generated by a point of order \(\ell_{i}\), which lies in the kernel of \(\pi+1\).  
Assume that [PERSON] and [PERSON] execute a key exchange. [PERSON] and [PERSON] randomly select each secret key \([\mathsf{a}]\) and \([\mathsf{b}]\) in \(\operatorname{cl}(\mathcal{O})\), respectively. Next, [PERSON] sends \(E_{A}=[\mathsf{a}]E\) to [PERSON], [PERSON] sends \(E_{B}=[\mathsf{b}]E\) to [PERSON]. Upon the receipt of \(E_{B}\) from [PERSON], [PERSON] computes \([\mathsf{a}]E_{B}\) and obtains \(E_{AB}=[\mathsf{a}]E_{B}\). Similarly, [PERSON] obtains \(E_{BA}=[\mathsf{b}]E_{A}\). Then \(E_{AB}=E_{BA}\) is the shared secret between [PERSON] and [PERSON].  
As an element of the ideal-class group \(\operatorname{cl}(\mathcal{O})\) is expected to be of the form \(\prod_{i=1}^{n}\mathfrak{l}_{i}^{\ell_{i}}\) (\(\mathfrak{l}_{i}=(\ell_{i},\pi-1)\)) by Cohen-Lenstra heuristics, the private key \([\mathsf{a}]\) and \([\mathsf{b}]\) is represented as the integer vectors \((e_{1},e_{2},\ldots,e_{n})\in\mathbb{Z}^{n}\), each of \(e_{i}\) sampled randomly from a range \([-m,m]\). Thus a group action \([\mathsf{a}]E\) can be computed by applying \(\ell_{i}\)-isogeny operation \(e_{i}\) times for \(\mathsf{a}=\prod_{i=1}^{n}\mathfrak{l}_{i}^{\ell_{i}}\in\operatorname{cl}( \mathcal{O})\). If \(e_{i}>0\), \(\ell_{i}\)-isogeny is applied with the kernel generated by a point in \(E(\mathbb{F}_{p})\) of order \(\ell_{i}\). If \(e_{i}<0\), \(\ell_{i}\)-isogeny is applied with the kernel generated by a point in \(E(\mathbb{F}_{p^{2}})\mathbb{F}_{p})\) of order \(\ell_{i}\).  
The CSIDH-512 offers an 128-bit classical security and uses the prime \(p_{1}\). The secret exponent of CSIDH-512 is of the form \((e_{1},e_{2},\ldots,e_{74})\), where \(e_{i}\in[-5,5]\). Thus, they expect that there are \(11^{74}\approx 2^{255.998}\) distinct exponents.