# On the Performance Analysis for CSIDH-Based Cryptosystems
The work of [13] means that \((e_{1},e_{2},\ldots,e_{n})\) and \((e_{1}+3,e_{2}+3,\ldots,e_{n}+3)\) represent the same ideal class (same private key) so that the size of the private keyspace is reduced. To eliminate this collision, they present a new ideal representation that exploits an isogeny of degree 4. In [14], they proposed CSIDH on the surface, called CSURF, using supersingular elliptic curve with endomorphism ring \(\mathbb{Z}[(1+\sqrt{-p})/2]\). The CSURF algorithm allows the use of 2-isogeny in CSIDH by choosing the prime \(p\) such that \(p\equiv 7\mod 8\), unlike the original CSIDH execute on the floor, i.e., using endomorphism ring \(\mathbb{Z}[\sqrt{-p}]\) with the base prime \(p\equiv 3\mod 8\). As the computation of the large degree isogenies corresponds to the performance degradation of CSIDH, CSURF proposed a way to use 2-isogenies more and use a fewer number of large degree isogenies at the same security level. To summarize, all of this work focuses on optimizing the performance of CSIDH while enhancing the security level. In this paper, we analyze the performance and security of the various CSIDH-based algorithms in order to find out what sort of prime \(p\) and which method is most efficient. The following list details the main contribution of this work. * We implement the CSIDH-based algorithms in the same environment for the exact performance comparison. More explicitly, we implement CSURF [13; 14] in projective coordinates. The algorithm in [13] has not been previously implemented. For CSURF, the authors presented only Magma-based implementation. We implemented both of the algorithms in C for an exact comparison with CSIDH [6]. The projectivized formula for the building blocks for both of the algorithms is presented in Section 2. * We generalize the existence of a collision for a base prime \(p\) such that \(p\equiv 7\mod 8\). As CSIDH-based algorithms use ideal classes expressed by an integer vector as a private key, the number of ideal classes represented by these vectors determines the security level of CSIDH. Hence, analyzing whether different private key results in the same public key is important. The collisions for CSIDH and CSURF were examined in [13; 15], respectively. We generalize this idea to the prime \(p\equiv 7\mod 8\). Details of our proof are presented in Section 3.4
* We analyze the performance and the security of the three algorithms--CSIDH, CSURF, and [PERSON]'s CSIDH over the prime \(p\) with \(p\equiv 3\mod 8\) and \(p\equiv 7\mod 8\). Additionally, we present a new interval for the private key to have a similar security level for the various CSIDH-based algorithms. The details of our implementation are presented in Section 4. From the implementation result, we conclude that for a prime \(p\equiv 7\mod 8\), CSIDH on the surface using the Montgomery curves is the most likely to be efficient. For a prime \(p\equiv 3\mod 8\), CSIDH on the floor using the hybrid method with [PERSON]'s collision-free method is the most likely to be efficient and secure. This paper is organized as follows. In Section 2, we introduce two types of elliptic curves, which will be used for the implementation. We also present the computational cost of the lower-level functions to construct CSIDH-based algorithms over these curves. In Section 3, we review the CSIDH algorithms and two of its variants. The implementation results are presented in Section 4, and we draw our conclusions and future work in Section 5.