Since its proposal in Asiacrypt 2018, the commutative isogeny-based key exchange protocol (CSIDH) has spurred considerable attention to improving its performance and re-evaluating its classical and quantum security guarantees. In this paper we discuss how the optimal strategies employed by the Supersingular Isogeny Diffie-Hellman (SIDH) key agreement protocol can be naturally extended to CSIDH. Furthermore, we report a software library that achieves moderate but noticeable performance speedups when compared against state-of-the-art implementations of CSIDH-512, which is the most popular CSIDH instantiation. We also report an estimated number of field operations for larger instantiations of this protocol, namely, CSIDH-1024 and CSIDH-1792.
Citation: |
Figure 1. Subfigure 1s shows a discrete triangle used to compute the inner loop of the CSIDH group action Algorithm 1. The main goal of this task is to find the field constants that define the elliptic curve $E_B$. As stated in Algorithm 1, the discrete triangle of Subfigure 1A must be computed exactly $m$ times. Using an optimal strategy as in [12], a discrete triangle $\Delta_n$ is processed by splitting it into two sub-triangles as shown in Subfigure 1b.
Figure 2. Two variants of the CSIDH group action evaluation: MCR style as proposed in [17] and OAYT style as proposed in [22]. Each one of the two aproaches depicted in this figure, computes a group action using the SIMBA-$\sigma$-$\kappa$ method, constructing isogenies of prime degree grouped in $\sigma$ batches. Each round must be repeated $\kappa$ times. A final repair round applies a multiplicative strategy to process the prime factors not covered during the $\kappa$ rounds. Horizontal edges and vertical edges represent isogeny evaluations $q_{\ell_i}, $ and scalar multiplications $p_{\ell_i}, $ respectively.
Figure 3. A graphical view of the strategies followed by three variants of the CSIDH group action evaluation: MCR style as presented [17], OAYT style as proposed [22] and dummy-free style as presented [7]. Horizontal edges and vertical edges represent isogeny evaluations $ q_{\ell_i}, $ and scalar multiplications $ p_{\ell_i}, $ respectively
Table 5. Clock cycle timings for constant-time CSIDH-512 group action evaluation, averaged over 1024 runs. The speedups given in the last column are calculated with respect to the MCR, OAYT and dummy-free using the SIMBA approach as they were reported in [7]
Table 1.
Costs for computing prime degree-
Table 2.
Approximate arithmetic costs for computing prime degree-
Primitive | M | S | Total Cost | |
S = M | S = 0.8 M | |||
$ [\ell]P $ | $ 84 $ | $ 42 $ | $ 126 $ | $ 118 $ |
$\mathtt{KPS}$ | $ 252 $ | $ 126 $ | $ 378 $ | $ 352 $ |
$\mathtt{xEVAL}$ | $ 256 $ | $ 2 $ | $ 256 $ | $ 256 $ |
$\mathtt{xISOG}$ | $ 151 $ | $ 18 $ | $ 169 $ | $ 166 $ |
Table 3. Expected number of field operation for the constant-time CSIDH-512 group action evaluation. Counts are given in millions of operations, averaged over 1024 random experiments. The speedup is computed using the multiplicative version of SIMBA-$\sigma$-$\kappa$ as a baseline, by only considering multiplication and squaring operations, and assuming M = S. The last three rows in this table report the highest speedups. Adding the public key validation cost to these three rows, get the last three rows in Table 4. Public key validation was separately measured, and presented in the last row of the table
Algorithm | Strategy | Bounds: $\overrightarrow{m}$ | Group action evaluation | M | S | a | Speedup (%) |
SIMBA-$5$-$11$ | multiplicative | as given in [17] | MCR-style | 0.900 | 0.297 | 0.939 | - |
optimal | 0.900 | 0.296 | 0.939 | 0.00 | |||
multiplicative | dummy-free | 1.309 | 0.392 | 1.324 | - | ||
optimal | 1.308 | 0.392 | 1.322 | 0.00 | |||
SIMBA-$3$-$8$ | multiplicative | as given in [22] | OAYT-style | 0.642 | 0.198 | 0.661 | - |
optimal | 0.642 | 0.198 | 0.661 | 0.00 | |||
SIMBA-$5$-$11$ | Multiplicative | as given in section 4.4 | MCR-style | 0.881 | 0.310 | 0.956 | 0.50 |
dummy-free | 1.280 | 0.415 | 1.353 | 0.35 | |||
SIMBA-$3$-$8$ | OAYT-style | 0.632 | 0.202 | 0.663 | 0.71 | ||
This work | optimal | as given in [17] | MCR-style | 0.930 | 0.242 | 0.851 | 2.09 |
dummy-free | 1.378 | 0.335 | 1.249 | -0.71 | |||
as given in [22] | OAYT-style | 0.670 | 0.173 | 0.626 | -0.36 | ||
This work | optimal | as given in section 4.4 | MCR-style | 0.835 | 0.231 | 0.784 | 10.94 |
dummy-free | 1.244 | 0.322 | 1.158 | 7.94 | |||
OAYT-style | 0.642 | 0.172 | 0.610 | 3.10 | |||
Public key validation | - | 0.021 | 0.010 | 0.030 | - |
Table 4. Field operation counts for constant-time CSIDH-512 group action evaluation. Counts are given in millions of operations, averaged over 1024 random experiments. The three speedups given in the last column are calculated with respect to the MCR, OAYT and dummy-free using the SIMBA approach as they were reported in [7]. Only multiplication and squaring operations were considered and it was assumed that M = S
Implementation | Group action evaluation | M | S | a | Speedup (%) | |
Cervantes-V#225;zquez et al. [7] | MCR-style | 0.900 | 0.310 | 0.964 | - | |
OAYT-style | 0.658 | 0.210 | 0.691 | - | ||
dummy-free-style | 1.319 | 0.423 | 1.389 | - | ||
Hutchinsond et al. [14] | OAYT-style | strategy | 0.637 | 0.212 | 0.712 | 2.19 |
This work | MCR-style | 0.862 | 0.255 | 0.866 | 7.69 | |
OAYT-style | 0.666 | 0.189 | 0.691 | 1.50 | ||
dummy-free-style | 1.273 | 0.346 | 1.280 | 7.06 |
Table 6. Expected number of field operation for the constant-time CSIDH-1024 group action evaluation. Counts are given in millions of operations, averaged over 1024 random experiments. For computing the Cost column, it is assumed that M = S and all addition costs are ignored. Public key validation was separately measured, and presented in the last row of the table
Group action evaluation | M | S | a | Cost |
MCR-style | 0.776 | 0.191 | 0.695 | 0.967 |
dummy-free | 1.152 | 0.259 | 1.011 | 1.411 |
OAYT-style | 0.630 | 0.152 | 0.576 | 0.782 |
Public key validation | 0.046 | 0.023 | 0.067 | 0.069 |
Table 7. Expected number of field operation for the constant-time CSIDH-1792 group action evaluation. Counts are given in millions of operations, averaged over 1024 random experiments. For computing the Cost column, it is assumed that M = S and all addition costs are ignored. Public key validation and full torsion point search were separately measured, and presented in the last rows of the table. The OAYT-style CSIDH group action reported in this table uses full torsion points and executes in a fixed running-time
Group action evaluation | M | S | a | Cost |
MCR-style | 1.040 | 0.239 | 0.910 | 1.279 |
dummy-free | 1.557 | 0.327 | 1.337 | 1.884 |
OAYT-style | 1.364 | 0.252 | 1.104 | 1.616 |
Full torsion points search | 1.571 | 0.785 | 2.295 | 2.356 |
Public key validation | 0.089 | 0.044 | 0.130 | 0.133 |
[1] | R. Azarderakhsh, et al., Supersingular isogeny key encapsulation, Second Round Candidate of the NIST's Post-quantum Cryptography Standardization Process, 2017, Available from: https://sike.org/. |
[2] | D. J. Bernstein, M. Hamburg, A. Krasnova and T. Lange, Elligator: Elliptic-curve points indistinguishable from uniform random strings, in 2013 ACM SIGSAC Conference on Computer and Communications Security, 2013,967–980. doi: 10.1145/2508859.2516734. |
[3] | D. J. Bernstein, T. Lange, C. Martindale and L. Panny, Quantum circuits for the CSIDH: Optimizing quantum evaluation of isogenies, Advances in Cryptology-EUROCRYPT 2019, LNCS, 11477, 2019,409–441. doi: 10.1007/978-3-030-17656-3_15. |
[4] | D. J. Bernstein, L. De Feo, A. Leroux and B. Smith, Faster computation of isogenies of large prime degree, Cryptology ePrint Archive, Report 2020/341 (2020), Available from: https://eprint.iacr.org/2020/341. |
[5] | W. Castryck and T. Decru, CSIDH on the surface, Post-Quantum Cryptography - 11th International Conference, LNCS, 12100, 2020,111–129. doi: 10.1007/978-3-030-44223-1_7. |
[6] | W. Castryck, T. Lange, C. Martindale, L. Panny and J. Renes, CSIDH: An efficient post-quantum commutative group action, Advances in Cryptology-ASIACRYPT 2018, LNCS, 11274, 2018,395–427. doi: 10.1007/978-3-030-03332-3_15. |
[7] | D. Cervantes-Vázquez, M. Chenu, J.-J. Chi-Domínguez, L. De Feo, F. Rodríguez-Henríquez and B. Smith, Stronger and faster side-channel protections for CSIDH, Progress in Cryptology - LATINCRYPT 2019, LNCS, 11774, 2019,173–193. doi: 10.1007/978-3-030-30530-7_9. |
[8] | D. Cervantes-Vázquez, E. Ochoa-Jiménez and F. Rodríguez-Henríquez, Parallel strategies for SIDH: Towards computing SIDH twice as fast, Cryptology ePrint Archive, Report 2020/383 (2020), Available from: https://eprint.iacr.org/2020/383. |
[9] | D. Cervantes-Vázquez and F. Rodríguez-Henríquez, A note on the cost of computing odd degree isogenies, Cryptology ePrint Archive, Report 2019/1373 (2019), Available from: https://eprint.iacr.org/2019/1373. |
[10] | C. Costello and H. Hisil, A simple and compact algorithm for SIDH with arbitrary degree isogenies, Advances in Cryptology - ASIACRYPT 2017 Part II, LNCS, 10625, 2017,303–329. doi: 10.1007/978-3-319-70697-9_1. |
[11] | J.-M. Couveignes, Hard homogeneous spaces, Cryptology ePrint Archive, Report 2006/291 (2006), Available from: http://eprint.iacr.org/2006/291. |
[12] | L. De Feo, D. Jao and J. Plût, Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies, Journal of Mathematical Cryptology, 8 (2014), 209-247. doi: 10.1515/jmc-2012-0015. |
[13] | L. De Feo, J. Kieffer and B. Smith, Towards practical key exchange from ordinary isogeny graphs, Advances in Cryptology-ASIACRYPT 2018, LNCS, 11274, 2018,365–394. doi: 10.1007/978-3-030-03332-3_14. |
[14] | A. Hutchinson, J. LeGrow, B. Koziel and R. Azarderakhsh, Further Optimizations of CSIDH: A Systematic Approach to Efficient Strategies, Permutations, and Bound Vectors., Cryptology ePrint Archive, Report 2019/1121 (2019) Available from http://eprint.iacr.org/2019/1121. |
[15] | A. Jalali, R. Azarderakhsh, M. Kermani and D. Jao, Towards optimized and constant-time CSIDH on embedded devices, Constructive Side-Channel Analysis and Secure Design-COSADE 2019, LNCS, 11421, 2019,215–231. doi: 10.1007/978-3-030-16350-1_12. |
[16] | P. Longa, Practical quantum-resistant key exchange from supersingular isogenies and its efficient implementation, Latincrypt 2019, Invited Talk. Available at: https://latincrypt2019.cryptojedi.org/slides/latincrypt2019-patrick-longa.pdf |
[17] | M. Meyer, F. Campos and S. Reith, On lions and elligators: An efficient constant-time implementation of CSIDH, Post-Quantum Cryptography-PQCrypto 2019, LNCS, 11505, 2019,307–325. doi: 10.1007/978-3-030-25510-7_17. |
[18] | M. Meyer and S. Reith, A faster way to the CSIDH, Progress in Cryptology-INDOCRYPT 2018, LNCS, 11356, 2018,137–152. doi: 10.1007/978-3-030-05378-9_8. |
[19] | T. Moriya, H. Onuki and T. Takagi, How to construct CSIDH on Edwards curves, Topics in Cryptology - CT-RSA, LNCS, 12006, 2020,512–537. doi: 10.1007/978-3-030-40186-3_22. |
[20] | "Submission requirements and evaluation criteria for the post-quantum cryptography standardization process", National Institute of Standards and Technology, 2016, Available from https://csrc.nist.gov/csrc/media/projects/post-quantum-cryptography/documents/call-for-proposals-final-dec-2016.pdf. |
[21] | K. Nakagawa, H. Onuki, A. Takayasu and T. Takagi, $L_1$-Norm ball for CSIDH: Optimal strategy for choosing the secret key space, Cryptology ePrint Archive, Report 2020/181 (2020), Available from https://eprint.iacr.org/2020/181. |
[22] | H. Onuki, Y. Aikawa, T. Yamazaki and T. Takagi, (Short Paper) A faster constant-time algorithm of CSIDH keeping two points, Advances in Information and Computer Security IWSEC, LNCS 11689, 23–33. doi: 10.1007/978-3-030-26834-3_2. |
[23] | A. Rostovtsev and A. Stolbunov, Public-key cryptosystem based on isogenies, Cryptology ePrint Archive, Report 2006/145 (2006), Available from http://eprint.iacr.org/2006/145. |
[24] | A. Stolbunov, Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves, Advances in Mathematics of Communication, 4 (2010), 215-235. doi: 10.3934/amc.2010.4.215. |
Subfigure 1s shows a discrete triangle used to compute the inner loop of the CSIDH group action Algorithm 1. The main goal of this task is to find the field constants that define the elliptic curve $E_B$. As stated in Algorithm 1, the discrete triangle of Subfigure 1A must be computed exactly $m$ times. Using an optimal strategy as in [12], a discrete triangle $\Delta_n$ is processed by splitting it into two sub-triangles as shown in Subfigure 1b.
Two variants of the CSIDH group action evaluation: MCR style as proposed in [17] and OAYT style as proposed in [22]. Each one of the two aproaches depicted in this figure, computes a group action using the SIMBA-$\sigma$-$\kappa$ method, constructing isogenies of prime degree grouped in $\sigma$ batches. Each round must be repeated $\kappa$ times. A final repair round applies a multiplicative strategy to process the prime factors not covered during the $\kappa$ rounds. Horizontal edges and vertical edges represent isogeny evaluations $q_{\ell_i}, $ and scalar multiplications $p_{\ell_i}, $ respectively.
A graphical view of the strategies followed by three variants of the CSIDH group action evaluation: MCR style as presented [17], OAYT style as proposed [22] and dummy-free style as presented [7]. Horizontal edges and vertical edges represent isogeny evaluations