American Institute of Mathematical Sciences

Advanced
May  2022, 16(2): 383-411. doi: 10.3934/amc.2020116

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

Received  May 2020 Revised  August 2020 Published  May 2022 Early access  October 2020

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

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: Isogeny-based cryptography, post-quantum cryptography, CSIDH protocol, key-exchange protocol, group action evaluation.
Mathematics Subject Classification: Primary: 94A60, 11T71; Secondary: 14L30.
Citation: Jesús-Javier Chi-Domínguez, Francisco Rodríguez-Henríquez. Optimal strategies for CSIDH. Advances in Mathematics of Communications, 2022, 16 (2) : 383-411. doi: 10.3934/amc.2020116
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.

show all references

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.

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 Options

Download full-size image

Download as 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.
Figure Options

Download full-size image

Download as 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
Figure Options

Download full-size image

Download as 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
Table Options

Download as excel

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
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
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 $
Table Options

Download as excel

Primitive M S A
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 $
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
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 Options

Download as excel

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 Options

Download as excel

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 Options

Download as excel

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 Options

Download as excel

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
Table Options

Download as excel

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]

Jintai Ding, Sihem Mesnager, Lih-Chung Wang. Letters for post-quantum cryptography standard evaluation. Advances in Mathematics of Communications, 2020, 14 (1) : i-i. doi: 10.3934/amc.2020012
[2]

Giacomo Micheli. Cryptanalysis of a noncommutative key exchange protocol. Advances in Mathematics of Communications, 2015, 9 (2) : 247-253. doi: 10.3934/amc.2015.9.247
[3]

Javier de la Cruz, Ricardo Villanueva-Polanco. Public key cryptography based on twisted dihedral group algebras. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022031
[4]

Mohammad Sadeq Dousti, Rasool Jalili. FORSAKES: A forward-secure authenticated key exchange protocol based on symmetric key-evolving schemes. Advances in Mathematics of Communications, 2015, 9 (4) : 471-514. doi: 10.3934/amc.2015.9.471
[5]

Xinwei Gao. Comparison analysis of Ding's RLWE-based key exchange protocol and NewHope variants. Advances in Mathematics of Communications, 2019, 13 (2) : 221-233. doi: 10.3934/amc.2019015
[6]

Gérard Maze, Chris Monico, Joachim Rosenthal. Public key cryptography based on semigroup actions. Advances in Mathematics of Communications, 2007, 1 (4) : 489-507. doi: 10.3934/amc.2007.1.489
[7]

Jie Xu, Lanjun Dang. An efficient RFID anonymous batch authentication protocol based on group signature. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1489-1500. doi: 10.3934/dcdss.2019102
[8]

Gerhard Frey. Relations between arithmetic geometry and public key cryptography. Advances in Mathematics of Communications, 2010, 4 (2) : 281-305. doi: 10.3934/amc.2010.4.281
[9]

Iris Anshel, Derek Atkins, Dorian Goldfeld, Paul E. Gunnells. Ironwood meta key agreement and authentication protocol. Advances in Mathematics of Communications, 2021, 15 (3) : 397-413. doi: 10.3934/amc.2020073
[10]

Pedro Branco. A post-quantum UC-commitment scheme in the global random oracle model from code-based assumptions. Advances in Mathematics of Communications, 2021, 15 (1) : 113-130. doi: 10.3934/amc.2020046
[11]

Florian Luca, Igor E. Shparlinski. On finite fields for pairing based cryptography. Advances in Mathematics of Communications, 2007, 1 (3) : 281-286. doi: 10.3934/amc.2007.1.281
[12]

Ramprasad Sarkar, Mriganka Mandal, Sourav Mukhopadhyay. Quantum-safe identity-based broadcast encryption with provable security from multivariate cryptography. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022026
[13]

Anton Stolbunov. Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves. Advances in Mathematics of Communications, 2010, 4 (2) : 215-235. doi: 10.3934/amc.2010.4.215
[14]

Lidong Chen, Dustin Moody. New mission and opportunity for mathematics researchers: Cryptography in the quantum era. Advances in Mathematics of Communications, 2020, 14 (1) : 161-169. doi: 10.3934/amc.2020013
[15]

Mohamed Baouch, Juan Antonio López-Ramos, Blas Torrecillas, Reto Schnyder. An active attack on a distributed Group Key Exchange system. Advances in Mathematics of Communications, 2017, 11 (4) : 715-717. doi: 10.3934/amc.2017052
[16]

Rainer Steinwandt, Adriana Suárez Corona. Attribute-based group key establishment. Advances in Mathematics of Communications, 2010, 4 (3) : 381-398. doi: 10.3934/amc.2010.4.381
[17]

Rainer Steinwandt, Adriana Suárez Corona. Cryptanalysis of a 2-party key establishment based on a semigroup action problem. Advances in Mathematics of Communications, 2011, 5 (1) : 87-92. doi: 10.3934/amc.2011.5.87
[18]

Zoltán Faigl, Miklós Telek. Modeling the signaling overhead in Host Identity Protocol-based secure mobile architectures. Journal of Industrial and Management Optimization, 2015, 11 (3) : 887-920. doi: 10.3934/jimo.2015.11.887
[19]

Hanyu Cao, Meiying Zhang, Huanxi Cai, Wei Gong, Min Su, Bin Li. A zero-forcing beamforming based time switching protocol for wireless powered internet of things system. Journal of Industrial and Management Optimization, 2020, 16 (6) : 2913-2922. doi: 10.3934/jimo.2019086
[20]

Chiara Spadafora, Riccardo Longo, Massimiliano Sala. A coercion-resistant blockchain-based E-voting protocol with receipts. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021005

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (498)
  • HTML views (626)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy