# On the Performance Analysis for CSIDH-Based Cryptosystems
## 3 CSIDH-Based Schemes
### Collisions for CSIDH-Based Algorithms  
In this subsection, we examine the correspondence between the ideal classes and the vectors for the CSIDH-based algorithms. As denoted in [6, 13, 14], the private keys in CSIDH-based algorithms are ideal classes in the class group \(\operatorname{cl}(\mathcal{O})\). Due to the design choices, this ideals can be expected to have the form \(\prod_{i=1}^{n}\mathfrak{l}_{i}^{e_{i}}\), for small \(e_{i}\). Hence, selecting an ideal classes corresponds to selecting an integer vector \begin{table}
\begin{tabular}{l l c c} \hline \hline  & & \(\big{(}|\mathbb{S}_{p,\mathcal{O}}^{+}|:|\mathcal{E}\ell\ell_{p}(\mathcal{O})| \big{)}\) & \(\big{(}|\mathbb{S}_{p,\mathcal{O}}^{-}|:|\mathcal{E}\ell\ell_{p}(\mathcal{O})| \big{)}\) \\ \hline \multirow{2}{*}{\(p\equiv 3\mod 8\)} & \(\mathcal{O}=Z[\frac{1+\sqrt{-p}}{2}]\) & 0 & (3:1) \\  & \(\mathcal{O}=Z[\sqrt{-p}]\) & (1:1) & 0 \\ \hline \multirow{2}{*}{\(p\equiv 7\mod 8\)} & \(\mathcal{O}=Z[\frac{1+\sqrt{-p}}{2}]\) & (2:1) & (1:1) \\  & \(\mathcal{O}=Z[\sqrt{-p}]\) & (1:1) & 0 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: ([14]) The ratio of the number of Montgomery\(\pm\) coefficients to the number of \(\mathbb{F}_{p}\)-isomorphism classes of supersingular elliptic curves. \((e_{1},\ldots,e_{n})\). Therefore, for an exact security evaluation, analyzing whether two different integer vectors \((e_{1},\ldots,e_{n})\) and \((e^{\prime}_{1},\ldots,e^{\prime}_{n})\) represent the same ideal class is important. In CSIDH-based schemes, there are different collisions depending on the prime of the base field and the \(\mathbb{F}_{p}\)-endomorphism ring \(End_{p}(E)\) of the elliptic curve \(E\). As we use two different types of prime \(p_{1}\) and \(p_{2}\) for our implementation, we examine the collision in this prime field. We first state the main theorem in [13] and the following corollary. **Theorem 1** ([13]). : _Let \(p\equiv 3\mod 8\) and \(End_{p}(E)=\mathcal{O}\). Then, the ideal class \(\{\mathfrak{l}_{1}^{r_{1}}\cdots\mathfrak{l}_{n}^{r_{n}}\}\) has order 3 in \(cl(\mathcal{O})\)._  
Proof. : See ([13], Theorem 3). **Corollary 1** ([13]). : _In the CSIDH protocol, the secret exponents_  
\[(e_{1},e_{2},\ldots,e_{n})\qquad\text{and}\qquad(e_{1}+3r_{1},e_{2}+3r_{2}, \ldots,e_{n}+3r_{n})\]  
_represent the same ideal class._  
CSIDH-512 use \(p_{1}\) as the base prime, where \(p_{1}\equiv 3\mod 8\). Hence, the collisions pointed out in [13] exists for the original parameters of CSIDH-512. Similarly, in [15] [PERSON] et al. proved that there also exist collisions of the form \((e_{0}+1,e_{1}+2,e_{2}+1,\ldots,e_{74}+1)\) for the CSURF prime \(p_{3}\). Now, we generalize the idea of [15] to a prime \(p\equiv 7\mod 8\) of a certain form. Let \(p\) be a prime of base field of the form \(p=4\cdot 2^{r_{0}}\ell_{1}^{r_{1}}\cdots\ell_{n}^{r_{n}}-1\), with \(p\equiv 7\mod 8\). Let \(\pi=\sqrt{-p}\), \(K=\mathbb{Q}(\pi)\), \(\mathcal{O}=\mathbb{Z}[\pi]\), and \(\mathcal{O}_{K}=\mathbb{Z}[\frac{1+\pi}{2}]\). Theorem 2 generalizes the theorem in [15] to the prime \(p\), where \(p\equiv 7\mod 8\). **Theorem 2**. : _Let \(p\equiv 7\mod 8\) and \(End_{p}(E)=\mathcal{O}_{K}\). Then the secret exponents_  
\[(e_{0},e_{1},\ldots,e_{n})\qquad\text{and}\qquad(e_{0}+r_{0},e_{1}+r_{1}, \ldots,e_{n}+r_{n})\]  
_represent the same ideal class, where \(\mathfrak{l}_{0}=(2,\frac{\pi-1}{2})\)._  
Proof. : Since \(\mathfrak{l}_{i}=(\ell_{i},\pi-1)=(\ell_{i},\frac{\pi-1}{2})\) in \(\operatorname{cl}(\mathcal{O}_{K})\), the followings are hold. \[\mathfrak{l}_{0}^{r_{0}}\mathfrak{l}_{1}^{r_{1}}\cdots\mathfrak{l }_{n}^{r_{n}} =(2,\frac{\pi-1}{2})^{r_{0}}\cdot(\ell_{1},\frac{\pi-1}{2})^{r_{1} }\cdots(\ell_{n},\frac{\pi-1}{2})^{r_{n}}\] \[=(2^{r_{0}}\ell_{1}^{r_{1}}\cdots\ell_{n}^{r_{n}},\frac{\pi-1}{2})\] \[=(\frac{p+1}{4},\frac{\pi-1}{2})=(\frac{\pi-1}{2}),\]  
Thus, \([\mathfrak{l}_{0}^{r_{0}}\mathfrak{l}_{1}^{r_{1}}\cdots\mathfrak{l}_{n}^{r_{ n}}]E=[\mathfrak{l}_{0}^{r_{0}+r_{0}}\mathfrak{l}_{1}^{r_{1}+r_{1}}\cdots \mathfrak{l}_{n}^{e_{n}+r_{n}}]E\). **Corollary 2**.