Optimal strategies for CSIDH

Jesús-Javier Chi-Domínguez; Francisco Rodríguez-Henríquez

doi:10.3934/amc.2020116

Article Contents

2022, Volume 16, Issue 2: 383-411. Doi: 10.3934/amc.2020116

This issue Previous Article A new construction of odd-variable rotation symmetric boolean functions with good cryptographic properties Next Article A note on the Signal-to-noise ratio of $ (n, m) $-functions

Optimal strategies for CSIDH

Jesús-Javier Chi-Domínguez^1, , and
Francisco Rodríguez-Henríquez^2,

1.
Faculty of Information Technology and Communication Sciences, Tampere University, Hervanta Campus, Korkeakoulunkatu 1, 33720 Tampere, Finland
2.
Computer Science Department, Cinvestav IPN, Zacatenco Unit, Av. IPN no. 2508, San pedro Zacatenco, Gustavo A. Madero, 07300 Mexico city, Mexico

^* Corresponding author: Jesús-Javier Chi-Domínguez
^* Corresponding author: Jesús-Javier Chi-Domínguez

Received: May 2020

Revised: August 2020

Early access: October 2020

Published: May 2022

The first author is supported by ERC grant agreement No. 804476

Abstract / Introduction Full Text(HTML) Figure(3) / Table(7) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 94A60, 11T71; Secondary: 14L30.

Citation:

Full Text(HTML)

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.

Download: Full-size image PowerPoint slide

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.

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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]

Implementation	Group action evaluation	Mcycles	Speedup (%)
Cervantes-Vázquez et al. [7]	MCR-style	339	-
	OAYT-style	238	-
	dummy-free	482	-
Hutchinson et al. [14]	OAYT-style	229	3.78
This work	MCR-style	298	12.09
	OAYT-style	230	3.36
	dummy-free-style	431	10.58

| Show Table

DownLoad: CSV

Table 1. Costs for computing prime degree-$ \ell $ isogenies with $ \ell = 2d + 1 $ using the $\mathtt{KPS}$, $\mathtt{xEVAL}$ and $\mathtt{xISOG}$ building blocks. Field multiplication (M) and squaring (S) costs are taken from [10,7,9]. The cost of performing one scalar multiplication $ [\ell]P $ using differential addition chains as in [7], is also presented. The computational costs associated to the point addition and point doubling operations is of 4 M + 2 S + 6 A and 4 M + 2 S + 4 A, respectively. We define $ \lambda = \lceil\log_2{\ell}\rceil $ and $ \bar{\lambda} \approx \frac{\log_2{(\lceil\frac{\ell}{8}}\rceil)}{3}. $

Primitive	M	S	A
Primitive	M	S	Montgomery[10]	Edwards[7]
$ [\ell]P $ [7]	$ 12\lambda $	$ 6\lambda $	$ 15\lambda $	$ - $
$\mathtt{KPS}$	$ 4(d-1) $	$ 2(d-1) $	$ 6d - 2 $	$ 6d - 2 $
$\mathtt{xEVAL}$	$ 4d $	2	$ 6d $	$ 2d + 4 $
$\mathtt{xISOG}$ [9]	$ \ell + 2\bar{\lambda} + 1 $	$ 2(\lambda + 2) $	$ - $	$ 0 $

| Show Table

DownLoad: CSV

Table 2. Approximate arithmetic costs for computing prime degree-$ \ell $ isogenies with $ \ell\; = \; 2d + 1 2\cdot 64 + 1 = 127, $ using the $\mathtt{KPS}$, $\mathtt{xEVAL}$, and $\mathtt{xISOG}$ primitives. The cost of computing the scalar multiplication $ [127]T $ is also reported

Primitive	M	S	Total Cost
Primitive	M	S	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 $

| Show Table

DownLoad: CSV

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		MCR-style	0.900	0.296	0.939	0.00
	multiplicative		dummy-free	1.309	0.392	1.324	-
	optimal		dummy-free	1.308	0.392	1.322	0.00
SIMBA-$3$-$8$	multiplicative	as given in [22]	OAYT-style	0.642	0.198	0.661	-
SIMBA-$3$-$8$	optimal	as given in [22]	OAYT-style	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
SIMBA-$5$-$11$			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
		as given in [17]	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	-

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[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.