# On the Performance Analysis for CSIDH-Based Cryptosystems
## 4 Implementation and Security Analysis  
In this section, we provide the implementation results and security analysis for the algorithms presented in previous chapters. First, we measure the performance of each algorithm using the initial parameters. However, for implementing the algorithms on the surface, we choose \(p_{2}\) as the prime of the base field to match the cost of the field arithmetic with \(p_{1}\), as much as possible. Then, we present the performance result by modifying the interval of the private key of each algorithm in order to match the security level. All of the algorithms in this paper are implemented in \(C\) language to evaluate the performance of each algorithm. To this end, we use the field arithmetic implemented in [6]. Moreover, wall-clock times and clock cycles are obtained on one core of an Intel(R) Core(TM) i7-6700 CPU @ 3.40 GHz, running Ubuntu 18.04.1 LTS. For compilation, we used GNU GCC version 7.5.0 with compile option -O3 using the benchmark provided by [6]. All results are averaged over 500,000 rounds. Note that the prime \(p_{1}\) and the initial curve \(y^{2}=x^{3}+x\) are used for implementing the original CSIDH and [PERSON]'s CSIDH, and the prime \(p_{2}\) and the initial curve \(y^{2}=x^{3}-x\) are used for implementing CSURF. When implementing CSIDH over \(p_{2}\), as a rational 2-torsion point exist, the 2-torsion method in [11; 16] is used for the implementation. Therefore, for CSIDH over \(p_{2}\), the curve \(y^{2}=x^{3}+ax^{2}+x\) is used as the initial curve, where \(a\) of the initial curve is presented in [11]. We also implement [PERSON]'s hybrid method for a fair comparison. The prime and the base curve for implementing [PERSON]'s hybrid method follows the setting of CSIDH. Table 4 shows the implementation results for each scheme, using the intervals provided in the original papers. For [PERSON]'s CSIDH, as [13] does not specified the intervals of the secret exponents, we arbitrarily set the intervals according the the security level. The security in Table 4 is the result of considering the collisions mentioned in Section 3.4. For CSIDH over \(p_{1}\) and \(p_{2}\), this equals to \(11^{74}-8^{74}\approx 2^{255.998}\) and \(11^{73}-8^{73}\approx 2^{252.536}\), respectively. For CSURF over \(p_{2}\), this equals to \(275\cdot 9^{28}\cdot 11^{45}-273\cdot 6\cdot 8^{27}\cdot 9\cdot 10^{44} \approx 2^{252.535}\). As CSURF is an algorithm only applicable on the surface of supersingular curves, the result using \(p_{1}\) does not exist. Similarly, [PERSON]'s method cannot be applied directly on the surface using \(p_{2}\), so that the result using this prime does not exist. This is because 4-isogenies presented in [13] do not preserve the same \((\ell,\pi-1)\) action class of the Montgomery curves used on the surface, as proved in the Proposition 1. Lastly, we provide the performance of CSIDH-based algorithms by modifying the intervals of the secret exponents for a similar security level. As in [6,13,14], we heuristically expect that these exponents represent the elements of the class group quasi-uniformly. Note that the intervals are modified in a way so that the first three 3-, 5-, and 7-isogenies are performed up to four times, as in line with the idea in [14]. We manage to select the exponent of the first three primes small since probability of selecting a random small torsion point is lower than selecting a random large torsion point. We do not apply other technical optimization methods like SIMBA [19], new addition chains for a scalar multiplication [20], and Velusqrt algorithm [21]. This is because we intend to present the comparison results of primitive algorithms as possible. Except for applying Velusqrt to the original CSIDH and the [PERSON]'s method, those techniques are applicable for all of the algorithms in this paper. As denote in Table 4 and 5, CSIDH using \(p_{2}\) is faster than CSIDH using \(p_{1}\).