# On the Performance Analysis for CSIDH-Based Cryptosystems
## 3 CSIDH-Based Schemes
### [PERSON]'s Csidh  
In [13], [PERSON] and [PERSON] proposed a new interval of the secret exponent and a new method for computing the coefficient of the image curve using 4-torsion points for CSIDH protocol. In CSIDH, the ideal classes, which are used as a private key, are represented by vectors with integer coefficients. As the number of ideal classes represented by these vectors determines the security level of CSIDH, it is important to examine the correspondence between the ideal classes and the vectors. They proved that the vector \((1,\ldots,1)\) corresponds to an ideal class of order 3. This means that a secret exponent \((e_{1},e_{2},\ldots,e_{n})\) and \((e_{1}+3,e_{2}+3,\ldots,e_{n}+3)\) represents the same ideal class. Since CSIDH-512 selects a secret exponent \((e_{1},e_{2},\ldots,e_{n})\) from a range \([-5,5]\), there exists the collision of the form \((e_{1}+3,e_{2}+3,\ldots,e_{n}+3)\). Thus, [PERSON] and [PERSON] used the ideal \(l_{0}=(4,\pi-1)\) instead of using the ideal \(l_{n}=(\ell_{n},\pi-1)\). Therefore, a secret exponent proposed in [13] is of the form \((e_{0},e_{1},\ldots,e_{n-1})\) to compute class group action \([\mathfrak{a}]E\coloneqq[\ell_{0}^{e_{1}}\ell_{1}^{e_{1}}\cdots\ell_{n-1}^{e _{n-1}}]E\), where \(e_{0}\in[-1,1]\) and \(e_{i}\in[-m,m]\) for \(1\leq i\leq n-1\). They also proposed a new formula for computing the actions of the ideal classes represented by \((1,\ldots,1)\) and \((-1,\ldots,-1)\) by using degree 4 isogenies. Let \(P_{-}\) and \(P_{+}\) be a point of \(M_{a}\) of \(x\)-coordinate -1 and 1, respectively. Then, for 4-isogenies \(\phi:M_{a}\to M_{a^{\prime}}\) used in this algorithm with \(\ker\phi=\left\langle P_{-}\right\rangle\) (resp. \(\ker\phi=\left\langle P_{+}\right\rangle\)), \(a^{\prime}\) is computed as  
\[a^{\prime}=\frac{2a-12}{a+2}\quad\Big{(}\text{resp. }a^{\prime}=\frac{-2a-12}{a-2} \Big{)}. \tag{5}\]  
The former case is computed if \(e_{0}=1\), and the later case is computed when \(e_{0}=-1\). Applicability of these 4-isogenies is argued in below proposition, where \(End_{p}(M_{a})\cong\mathbb{Z}[\left(1+\sqrt{-p}\right)/2]\). **Proposition 1**. : _Let \(p\) be a prime of the form \(p\equiv 7\mod 8\) and \(M_{a}:y^{2}=x^{3}+ax^{2}+x\) be a Montgomery curve with the endomorphism ring \(End_{p}(M_{a})\cong\mathcal{O}_{K}\). Then, the 4-isogenies \(\phi:M_{a}\to M_{a^{\prime}}\) presented in (5)_  
\[(i)\quad a^{\prime}=\frac{2a-12}{a+2}\qquad\text{and}\qquad(ii)\quad a^{\prime }=\frac{-2a-12}{a-2}\]  
_do not preserve the same \((\ell,\pi-1)\) action class._  
Proof. : First, the set \(S^{+}_{p,\mathcal{O}_{K}}=\{a\mid End_{p}(M_{a})\cong\mathcal{O}_{K}\}\) splits into two partitions, denoted \(S^{+}_{p,1}\) and \(S^{+}_{p,2}\) respectively. These sets are defined as below,  
\[S^{+}_{p,1} =\{a\in S^{+}_{p,\mathcal{O}_{K}}\mid(0,0)\
otin 2M_{a}(\mathbb{F}_{p })\},\] \[S^{+}_{p,2} =\{a\in S^{+}_{p,\mathcal{O}_{K}}\mid(0,0)\in 2M_{a}(\mathbb{F}_{p })\}.\]  
Note that \(a\pm 2\) are both square in \(\mathbb{F}_{p}\) if \(a\in S^{+}_{p,2}\), and \(a\pm 2\) are not both square in \(\mathbb{F}_{p}\) if \(a\in S^{+}_{p,1}\) by Theorem 2 in [11]. Assume that we apply above former 4-isogeny. Since \(a^{\prime}=(2a-12)/(a+2)\),  
\[a^{\prime}+2=\frac{4(a-2)}{a+2}\qquad\text{and}\qquad a^{\prime}-2=\frac{-16} {a+2}.\]  
If \(a\in S^{+}_{p,1}\), then \(a^{\prime}\pm 2\) are both square in \(\mathbb{F}_{p}\), so that \(a^{\prime}\in S^{+}_{p,2}\). If \(a\in S^{+}_{p,2}\), then \(a^{\prime}+2\) is square and \(a^{\prime}-2\) is not square in \(\mathbb{F}_{p}\), so that \(a^{\prime}\in S_{p,\mathcal{O}}\). That is, the image curve \(M_{a^{\prime}}\) is on the floor. Similarly, the case of later 4-isogeny does not preserve the same \((\ell,\pi-1)\) action class. We summarize the result of Proposition 1 in Table 2. \begin{table}
\begin{tabular}{c c c} \hline  & \((i)\) & \((ii)\) \\ \hline \(S^{+}_{p,1}\) & \(S^{+}_{p,2}\) & \(S_{p,\mathcal{O}}\) \\ \(S^{+}_{p,2}\) & \(S_{p,\mathcal{O}}\) & \(S^{+}_{p,1}\) \\ \hline \end{tabular}
\end{table}