
Previous Article
Further results on 2uniform states arising from irredundant orthogonal arrays
 AMC Home
 This Issue

Next Article
Some subfield codes from MDS codes
Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.
Readers can access Online First articles via the “Online First” tab for the selected journal.
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 Google Scholar 
[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. 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 CryptologyEUROCRYPT 2019, LNCS, 11477, 2019,409–441. doi: 10.1007/9783030176563_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, PostQuantum Cryptography  11th International Conference, LNCS, 12100, 2020,111–129. doi: 10.1007/9783030442231_7. Google Scholar 
[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. Google Scholar 
[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. Google Scholar 
[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) Google Scholar 
[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) 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/9783319706979_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 quantumresistant cryptosystems from supersingular elliptic curve isogenies, Journal of Mathematical Cryptology, 8 (2014), 209247. doi: 10.1515/jmc20120015. Google Scholar 
[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. 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 constanttime CSIDH on embedded devices, Constructive SideChannel Analysis and Secure DesignCOSADE 2019, LNCS, 11421, 2019,215–231. doi: 10.1007/9783030163501_12. Google Scholar 
[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 Google Scholar 
[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. Google Scholar 
[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. Google Scholar 
[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. Google Scholar 
[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. 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 constanttime algorithm of CSIDH keeping two points, Advances in Information and Computer Security IWSEC, LNCS 11689, 23–33. doi: 10.1007/9783030268343_2. Google Scholar 
[23] 
A. Rostovtsev and A. Stolbunov, Publickey cryptosystem based on isogenies, Cryptology ePrint Archive, Report 2006/145 (2006) Google Scholar 
[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. Google Scholar 
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 Google Scholar 
[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. 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 CryptologyEUROCRYPT 2019, LNCS, 11477, 2019,409–441. doi: 10.1007/9783030176563_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, PostQuantum Cryptography  11th International Conference, LNCS, 12100, 2020,111–129. doi: 10.1007/9783030442231_7. Google Scholar 
[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. Google Scholar 
[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. Google Scholar 
[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) Google Scholar 
[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) 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/9783319706979_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 quantumresistant cryptosystems from supersingular elliptic curve isogenies, Journal of Mathematical Cryptology, 8 (2014), 209247. doi: 10.1515/jmc20120015. Google Scholar 
[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. 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 constanttime CSIDH on embedded devices, Constructive SideChannel Analysis and Secure DesignCOSADE 2019, LNCS, 11421, 2019,215–231. doi: 10.1007/9783030163501_12. Google Scholar 
[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 Google Scholar 
[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. Google Scholar 
[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. Google Scholar 
[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. Google Scholar 
[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. 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 constanttime algorithm of CSIDH keeping two points, Advances in Information and Computer Security IWSEC, LNCS 11689, 23–33. doi: 10.1007/9783030268343_2. Google Scholar 
[23] 
A. Rostovtsev and A. Stolbunov, Publickey cryptosystem based on isogenies, Cryptology ePrint Archive, Report 2006/145 (2006) Google Scholar 
[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. Google Scholar 
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] 
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 
[4] 
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 
[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] 
Jie Xu, Lanjun Dang. An efficient RFID anonymous batch authentication protocol based on group signature. Discrete & Continuous Dynamical Systems  S, 2019, 12 (4&5) : 14891500. doi: 10.3934/dcdss.2019102 
[7] 
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 
[8] 
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 
[9] 
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 
[10] 
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 
[11] 
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 
[12] 
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 
[13] 
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 
[14] 
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 
[15] 
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 
[16] 
Zoltán Faigl, Miklós Telek. Modeling the signaling overhead in Host Identity Protocolbased secure mobile architectures. Journal of Industrial & Management Optimization, 2015, 11 (3) : 887920. doi: 10.3934/jimo.2015.11.887 
[17] 
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 & Management Optimization, 2020, 16 (6) : 29132922. doi: 10.3934/jimo.2019086 
[18] 
Chiara Spadafora, Riccardo Longo, Massimiliano Sala. A coercionresistant blockchainbased Evoting protocol with receipts. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021005 
[19] 
Diego F. Aranha, Ricardo Dahab, Julio López, Leonardo B. Oliveira. Efficient implementation of elliptic curve cryptography in wireless sensors. Advances in Mathematics of Communications, 2010, 4 (2) : 169187. doi: 10.3934/amc.2010.4.169 
[20] 
Andreas Klein. How to say yes, no and maybe with visual cryptography. Advances in Mathematics of Communications, 2008, 2 (3) : 249259. doi: 10.3934/amc.2008.2.249 
2020 Impact Factor: 0.935
Tools
Article outline
Figures and Tables
[Back to Top]