
Previous Article
A note on the Signaltonoise ratio of $ (n, m) $functions
 AMC Home
 This Issue

Next Article
A new construction of oddvariable rotation symmetric boolean functions with good cryptographic properties
Optimal strategies for CSIDH
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 
Since its proposal in Asiacrypt 2018, the commutative isogenybased key exchange protocol (CSIDH) has spurred considerable attention to improving its performance and reevaluating its classical and quantum security guarantees. In this paper we discuss how the optimal strategies employed by the Supersingular Isogeny DiffieHellman (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 stateoftheart implementations of CSIDH512, which is the most popular CSIDH instantiation. We also report an estimated number of field operations for larger instantiations of this protocol, namely, CSIDH1024 and CSIDH1792.
References:
[1] 
R. Azarderakhsh, et al., Supersingular isogeny key encapsulation, Second Round Candidate of the NIST's Postquantum Cryptography Standardization Process, 2017, Available from: https://sike.org/. 
[2] 
D. J. Bernstein, M. Hamburg, A. Krasnova and T. Lange, Elligator: Ellipticcurve 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 CryptologyEUROCRYPT 2019, LNCS, 11477, 2019,409–441. doi: 10.1007/9783030176563_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, PostQuantum Cryptography  11th International Conference, LNCS, 12100, 2020,111–129. doi: 10.1007/9783030442231_7. 
[6] 
W. Castryck, T. Lange, C. Martindale, L. Panny and J. Renes, CSIDH: An efficient postquantum commutative group action, Advances in CryptologyASIACRYPT 2018, LNCS, 11274, 2018,395–427. doi: 10.1007/9783030033323_15. 
[7] 
D. CervantesVázquez, M. Chenu, J.J. ChiDomínguez, L. De Feo, F. RodríguezHenríquez and B. Smith, Stronger and faster sidechannel protections for CSIDH, Progress in Cryptology  LATINCRYPT 2019, LNCS, 11774, 2019,173–193. doi: 10.1007/9783030305307_9. 
[8] 
D. CervantesVázquez, E. OchoaJiménez and F. RodríguezHenrí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. CervantesVázquez and F. RodríguezHenrí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/9783319706979_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 quantumresistant cryptosystems from supersingular elliptic curve isogenies, Journal of Mathematical Cryptology, 8 (2014), 209247. doi: 10.1515/jmc20120015. 
[13] 
L. De Feo, J. Kieffer and B. Smith, Towards practical key exchange from ordinary isogeny graphs, Advances in CryptologyASIACRYPT 2018, LNCS, 11274, 2018,365–394. doi: 10.1007/9783030033323_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 constanttime CSIDH on embedded devices, Constructive SideChannel Analysis and Secure DesignCOSADE 2019, LNCS, 11421, 2019,215–231. doi: 10.1007/9783030163501_12. 
[16] 
P. Longa, Practical quantumresistant key exchange from supersingular isogenies and its efficient implementation, Latincrypt 2019, Invited Talk. Available at: https://latincrypt2019.cryptojedi.org/slides/latincrypt2019patricklonga.pdf 
[17] 
M. Meyer, F. Campos and S. Reith, On lions and elligators: An efficient constanttime implementation of CSIDH, PostQuantum CryptographyPQCrypto 2019, LNCS, 11505, 2019,307–325. doi: 10.1007/9783030255107_17. 
[18] 
M. Meyer and S. Reith, A faster way to the CSIDH, Progress in CryptologyINDOCRYPT 2018, LNCS, 11356, 2018,137–152. doi: 10.1007/9783030053789_8. 
[19] 
T. Moriya, H. Onuki and T. Takagi, How to construct CSIDH on Edwards curves, Topics in Cryptology  CTRSA, LNCS, 12006, 2020,512–537. doi: 10.1007/9783030401863_22. 
[20] 
"Submission requirements and evaluation criteria for the postquantum cryptography standardization process", National Institute of Standards and Technology, 2016, Available from https://csrc.nist.gov/csrc/media/projects/postquantumcryptography/documents/callforproposalsfinaldec2016.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 constanttime algorithm of CSIDH keeping two points, Advances in Information and Computer Security IWSEC, LNCS 11689, 23–33. doi: 10.1007/9783030268343_2. 
[23] 
A. Rostovtsev and A. Stolbunov, Publickey cryptosystem based on isogenies, Cryptology ePrint Archive, Report 2006/145 (2006), Available from http://eprint.iacr.org/2006/145. 
[24] 
A. Stolbunov, Constructing publickey cryptographic schemes based on class group action on a set of isogenous elliptic curves, Advances in Mathematics of Communication, 4 (2010), 215235. 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 Postquantum Cryptography Standardization Process, 2017, Available from: https://sike.org/. 
[2] 
D. J. Bernstein, M. Hamburg, A. Krasnova and T. Lange, Elligator: Ellipticcurve 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 CryptologyEUROCRYPT 2019, LNCS, 11477, 2019,409–441. doi: 10.1007/9783030176563_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, PostQuantum Cryptography  11th International Conference, LNCS, 12100, 2020,111–129. doi: 10.1007/9783030442231_7. 
[6] 
W. Castryck, T. Lange, C. Martindale, L. Panny and J. Renes, CSIDH: An efficient postquantum commutative group action, Advances in CryptologyASIACRYPT 2018, LNCS, 11274, 2018,395–427. doi: 10.1007/9783030033323_15. 
[7] 
D. CervantesVázquez, M. Chenu, J.J. ChiDomínguez, L. De Feo, F. RodríguezHenríquez and B. Smith, Stronger and faster sidechannel protections for CSIDH, Progress in Cryptology  LATINCRYPT 2019, LNCS, 11774, 2019,173–193. doi: 10.1007/9783030305307_9. 
[8] 
D. CervantesVázquez, E. OchoaJiménez and F. RodríguezHenrí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. CervantesVázquez and F. RodríguezHenrí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/9783319706979_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 quantumresistant cryptosystems from supersingular elliptic curve isogenies, Journal of Mathematical Cryptology, 8 (2014), 209247. doi: 10.1515/jmc20120015. 
[13] 
L. De Feo, J. Kieffer and B. Smith, Towards practical key exchange from ordinary isogeny graphs, Advances in CryptologyASIACRYPT 2018, LNCS, 11274, 2018,365–394. doi: 10.1007/9783030033323_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 constanttime CSIDH on embedded devices, Constructive SideChannel Analysis and Secure DesignCOSADE 2019, LNCS, 11421, 2019,215–231. doi: 10.1007/9783030163501_12. 
[16] 
P. Longa, Practical quantumresistant key exchange from supersingular isogenies and its efficient implementation, Latincrypt 2019, Invited Talk. Available at: https://latincrypt2019.cryptojedi.org/slides/latincrypt2019patricklonga.pdf 
[17] 
M. Meyer, F. Campos and S. Reith, On lions and elligators: An efficient constanttime implementation of CSIDH, PostQuantum CryptographyPQCrypto 2019, LNCS, 11505, 2019,307–325. doi: 10.1007/9783030255107_17. 
[18] 
M. Meyer and S. Reith, A faster way to the CSIDH, Progress in CryptologyINDOCRYPT 2018, LNCS, 11356, 2018,137–152. doi: 10.1007/9783030053789_8. 
[19] 
T. Moriya, H. Onuki and T. Takagi, How to construct CSIDH on Edwards curves, Topics in Cryptology  CTRSA, LNCS, 12006, 2020,512–537. doi: 10.1007/9783030401863_22. 
[20] 
"Submission requirements and evaluation criteria for the postquantum cryptography standardization process", National Institute of Standards and Technology, 2016, Available from https://csrc.nist.gov/csrc/media/projects/postquantumcryptography/documents/callforproposalsfinaldec2016.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 constanttime algorithm of CSIDH keeping two points, Advances in Information and Computer Security IWSEC, LNCS 11689, 23–33. doi: 10.1007/9783030268343_2. 
[23] 
A. Rostovtsev and A. Stolbunov, Publickey cryptosystem based on isogenies, Cryptology ePrint Archive, Report 2006/145 (2006), Available from http://eprint.iacr.org/2006/145. 
[24] 
A. Stolbunov, Constructing publickey cryptographic schemes based on class group action on a set of isogenous elliptic curves, Advances in Mathematics of Communication, 4 (2010), 215235. doi: 10.3934/amc.2010.4.215. 
Primitive  M  S  Total Cost  
S = M  S = 0.8 M  
$\mathtt{KPS}$  
$\mathtt{xEVAL}$  
$\mathtt{xISOG}$ 
Primitive  M  S  Total Cost  
S = M  S = 0.8 M  
$\mathtt{KPS}$  
$\mathtt{xEVAL}$  
$\mathtt{xISOG}$ 
Algorithm  Strategy  Bounds: $\overrightarrow{m}$  Group action evaluation  M  S  a  Speedup (%) 
SIMBA$5$$11$  multiplicative  as given in [17]  MCRstyle  0.900  0.297  0.939   
optimal  0.900  0.296  0.939  0.00  
multiplicative  dummyfree  1.309  0.392  1.324    
optimal  1.308  0.392  1.322  0.00  
SIMBA$3$$8$  multiplicative  as given in [22]  OAYTstyle  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  MCRstyle  0.881  0.310  0.956  0.50 
dummyfree  1.280  0.415  1.353  0.35  
SIMBA$3$$8$  OAYTstyle  0.632  0.202  0.663  0.71  
This work  optimal  as given in [17]  MCRstyle  0.930  0.242  0.851  2.09 
dummyfree  1.378  0.335  1.249  0.71  
as given in [22]  OAYTstyle  0.670  0.173  0.626  0.36  
This work  optimal  as given in section 4.4  MCRstyle  0.835  0.231  0.784  10.94 
dummyfree  1.244  0.322  1.158  7.94  
OAYTstyle  0.642  0.172  0.610  3.10  
Public key validation    0.021  0.010  0.030   
Algorithm  Strategy  Bounds: $\overrightarrow{m}$  Group action evaluation  M  S  a  Speedup (%) 
SIMBA$5$$11$  multiplicative  as given in [17]  MCRstyle  0.900  0.297  0.939   
optimal  0.900  0.296  0.939  0.00  
multiplicative  dummyfree  1.309  0.392  1.324    
optimal  1.308  0.392  1.322  0.00  
SIMBA$3$$8$  multiplicative  as given in [22]  OAYTstyle  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  MCRstyle  0.881  0.310  0.956  0.50 
dummyfree  1.280  0.415  1.353  0.35  
SIMBA$3$$8$  OAYTstyle  0.632  0.202  0.663  0.71  
This work  optimal  as given in [17]  MCRstyle  0.930  0.242  0.851  2.09 
dummyfree  1.378  0.335  1.249  0.71  
as given in [22]  OAYTstyle  0.670  0.173  0.626  0.36  
This work  optimal  as given in section 4.4  MCRstyle  0.835  0.231  0.784  10.94 
dummyfree  1.244  0.322  1.158  7.94  
OAYTstyle  0.642  0.172  0.610  3.10  
Public key validation    0.021  0.010  0.030   
Implementation  Group action evaluation  M  S  a  Speedup (%)  
CervantesV#225;zquez et al. [7]  MCRstyle  0.900  0.310  0.964    
OAYTstyle  0.658  0.210  0.691    
dummyfreestyle  1.319  0.423  1.389    
Hutchinsond et al. [14]  OAYTstyle  strategy  0.637  0.212  0.712  2.19 
This work  MCRstyle  0.862  0.255  0.866  7.69  
OAYTstyle  0.666  0.189  0.691  1.50  
dummyfreestyle  1.273  0.346  1.280  7.06 
Implementation  Group action evaluation  M  S  a  Speedup (%)  
CervantesV#225;zquez et al. [7]  MCRstyle  0.900  0.310  0.964    
OAYTstyle  0.658  0.210  0.691    
dummyfreestyle  1.319  0.423  1.389    
Hutchinsond et al. [14]  OAYTstyle  strategy  0.637  0.212  0.712  2.19 
This work  MCRstyle  0.862  0.255  0.866  7.69  
OAYTstyle  0.666  0.189  0.691  1.50  
dummyfreestyle  1.273  0.346  1.280  7.06 
Group action evaluation  M  S  a  Cost 
MCRstyle  0.776  0.191  0.695  0.967 
dummyfree  1.152  0.259  1.011  1.411 
OAYTstyle  0.630  0.152  0.576  0.782 
Public key validation  0.046  0.023  0.067  0.069 
Group action evaluation  M  S  a  Cost 
MCRstyle  0.776  0.191  0.695  0.967 
dummyfree  1.152  0.259  1.011  1.411 
OAYTstyle  0.630  0.152  0.576  0.782 
Public key validation  0.046  0.023  0.067  0.069 
Group action evaluation  M  S  a  Cost 
MCRstyle  1.040  0.239  0.910  1.279 
dummyfree  1.557  0.327  1.337  1.884 
OAYTstyle  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 
Group action evaluation  M  S  a  Cost 
MCRstyle  1.040  0.239  0.910  1.279 
dummyfree  1.557  0.327  1.337  1.884 
OAYTstyle  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, LihChung Wang. Letters for postquantum cryptography standard evaluation. Advances in Mathematics of Communications, 2020, 14 (1) : ii. doi: 10.3934/amc.2020012 
[2] 
Giacomo Micheli. Cryptanalysis of a noncommutative key exchange protocol. Advances in Mathematics of Communications, 2015, 9 (2) : 247253. doi: 10.3934/amc.2015.9.247 
[3] 
Javier de la Cruz, Ricardo VillanuevaPolanco. 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 forwardsecure authenticated key exchange protocol based on symmetric keyevolving schemes. Advances in Mathematics of Communications, 2015, 9 (4) : 471514. doi: 10.3934/amc.2015.9.471 
[5] 
Xinwei Gao. Comparison analysis of Ding's RLWEbased key exchange protocol and NewHope variants. Advances in Mathematics of Communications, 2019, 13 (2) : 221233. 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) : 489507. 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) : 14891500. doi: 10.3934/dcdss.2019102 
[8] 
Gerhard Frey. Relations between arithmetic geometry and public key cryptography. Advances in Mathematics of Communications, 2010, 4 (2) : 281305. 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) : 397413. doi: 10.3934/amc.2020073 
[10] 
Pedro Branco. A postquantum UCcommitment scheme in the global random oracle model from codebased assumptions. Advances in Mathematics of Communications, 2021, 15 (1) : 113130. 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) : 281286. doi: 10.3934/amc.2007.1.281 
[12] 
Ramprasad Sarkar, Mriganka Mandal, Sourav Mukhopadhyay. Quantumsafe identitybased broadcast encryption with provable security from multivariate cryptography. Advances in Mathematics of Communications, 2022 doi: 10.3934/amc.2022026 
[13] 
Anton Stolbunov. Constructing publickey cryptographic schemes based on class group action on a set of isogenous elliptic curves. Advances in Mathematics of Communications, 2010, 4 (2) : 215235. 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) : 161169. doi: 10.3934/amc.2020013 
[15] 
Mohamed Baouch, Juan Antonio LópezRamos, Blas Torrecillas, Reto Schnyder. An active attack on a distributed Group Key Exchange system. Advances in Mathematics of Communications, 2017, 11 (4) : 715717. doi: 10.3934/amc.2017052 
[16] 
Rainer Steinwandt, Adriana Suárez Corona. Attributebased group key establishment. Advances in Mathematics of Communications, 2010, 4 (3) : 381398. doi: 10.3934/amc.2010.4.381 
[17] 
Rainer Steinwandt, Adriana Suárez Corona. Cryptanalysis of a 2party key establishment based on a semigroup action problem. Advances in Mathematics of Communications, 2011, 5 (1) : 8792. doi: 10.3934/amc.2011.5.87 
[18] 
Zoltán Faigl, Miklós Telek. Modeling the signaling overhead in Host Identity Protocolbased secure mobile architectures. Journal of Industrial and Management Optimization, 2015, 11 (3) : 887920. doi: 10.3934/jimo.2015.11.887 
[19] 
Hanyu Cao, Meiying Zhang, Huanxi Cai, Wei Gong, Min Su, Bin Li. A zeroforcing beamforming based time switching protocol for wireless powered internet of things system. Journal of Industrial and Management Optimization, 2020, 16 (6) : 29132922. doi: 10.3934/jimo.2019086 
[20] 
Chiara Spadafora, Riccardo Longo, Massimiliano Sala. A coercionresistant blockchainbased Evoting protocol with receipts. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021005 
2020 Impact Factor: 0.935
Tools
Metrics
Other articles
by authors
[Back to Top]