American Institute of Mathematical Sciences

Advanced
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  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, 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 Google Scholar

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

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

[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) Google Scholar

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

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

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

[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) Google Scholar

[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) Google Scholar

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

[11]

J.-M. Couveignes, Hard homogeneous spaces, Cryptology ePrint Archive, Report 2006/291 (2006) Google Scholar

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

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

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

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

[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 Google Scholar

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

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

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

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

[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) Google Scholar

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

[23]

A. Rostovtsev and A. Stolbunov, Public-key cryptosystem based on isogenies, Cryptology ePrint Archive, Report 2006/145 (2006) Google Scholar

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

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 Google Scholar

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

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

[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) Google Scholar

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

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

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

[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) Google Scholar

[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) Google Scholar

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

[11]

J.-M. Couveignes, Hard homogeneous spaces, Cryptology ePrint Archive, Report 2006/291 (2006) Google Scholar

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

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

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

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

[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 Google Scholar

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

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

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

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

[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) Google Scholar

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

[23]

A. Rostovtsev and A. Stolbunov, Public-key cryptosystem based on isogenies, Cryptology ePrint Archive, Report 2006/145 (2006) Google Scholar

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

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]

Z. Reichstein and B. Youssin. Parusinski's "Key Lemma" via algebraic geometry. Electronic Research Announcements, 1999, 5: 136-145.

[2]

Arseny Egorov. Morse coding for a Fuchsian group of finite covolume. Journal of Modern Dynamics, 2009, 3 (4) : 637-646. doi: 10.3934/jmd.2009.3.637
[3]

Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1717-1746. doi: 10.3934/dcdss.2020451
[4]

Israa Mohammed Khudher, Yahya Ismail Ibrahim, Suhaib Abduljabbar Altamir. Individual biometrics pattern based artificial image analysis techniques. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2020056
[5]

Enkhbat Rentsen, Battur Gompil. Generalized Nash equilibrium problem based on malfatti's problem. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 209-220. doi: 10.3934/naco.2020022
[6]

Jia Cai, Guanglong Xu, Zhensheng Hu. Sketch-based image retrieval via CAT loss with elastic net regularization. Mathematical Foundations of Computing, 2020, 3 (4) : 219-227. doi: 10.3934/mfc.2020013
[7]

Teddy Pichard. A moment closure based on a projection on the boundary of the realizability domain: 1D case. Kinetic & Related Models, 2020, 13 (6) : 1243-1280. doi: 10.3934/krm.2020045
[8]

Peter Benner, Jens Saak, M. Monir Uddin. Balancing based model reduction for structured index-2 unstable descriptor systems with application to flow control. Numerical Algebra, Control & Optimization, 2016, 6 (1) : 1-20. doi: 10.3934/naco.2016.6.1
[9]

Abdulrazzaq T. Abed, Azzam S. Y. Aladool. Applying particle swarm optimization based on Padé approximant to solve ordinary differential equation. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021008

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (44)
  • HTML views (167)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences