{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T04:22:35Z","timestamp":1778127755589,"version":"3.51.4"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,8,31]],"date-time":"2021-08-31T00:00:00Z","timestamp":1630368000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,8,31]],"date-time":"2021-08-31T00:00:00Z","timestamp":1630368000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["804476"],"award-info":[{"award-number":["804476"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010360","name":"St. Cross College, University of Oxford","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100010360","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003141","name":"Consejo Nacional de Ciencia y Tecnolog\u00eda","doi-asserted-by":"publisher","award":["313572"],"award-info":[{"award-number":["313572"]}],"id":[{"id":"10.13039\/501100003141","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptogr Eng"],"published-print":{"date-parts":[[2022,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Recent independent analyses by Bonnetain\u2013Schrottenloher and Peikert in Eurocrypt 2020 significantly reduced the estimated quantum security of the isogeny-based commutative group action key-exchange protocol CSIDH. This paper refines the estimates of a resource-constrained quantum collimation sieve attack to give a precise quantum security to CSIDH. Furthermore, we optimize large CSIDH parameters for performance while still achieving the NIST security levels 1, 2, and 3. Finally, we provide a C-code constant-time implementation of those CSIDH large instantiations using the square-root-complexity V\u00e9lu\u2019s formulas recently proposed by Bernstein, De Feo, Leroux and Smith.\n<\/jats:p>","DOI":"10.1007\/s13389-021-00271-w","type":"journal-article","created":{"date-parts":[[2021,8,31]],"date-time":"2021-08-31T10:02:49Z","timestamp":1630404169000},"page":"349-368","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":49,"title":["The SQALE of CSIDH: sublinear V\u00e9lu quantum-resistant isogeny action with low exponents"],"prefix":"10.1007","volume":"12","author":[{"given":"Jorge","family":"Ch\u00e1vez-Saab","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jes\u00fas-Javier","family":"Chi-Dom\u00ednguez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0966-8114","authenticated-orcid":false,"given":"Samuel","family":"Jaques","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Francisco","family":"Rodr\u00edguez-Henr\u00edquez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,8,31]]},"reference":[{"key":"271_CR1","doi-asserted-by":"publisher","unstructured":"Adj, G., Cervantes-V\u00e1zquez, D., Chi-Dom\u00ednguez, J., Menezes, A., Rodr\u00edguez-Henr\u00edquez, F.: On the cost of computing isogenies between supersingular elliptic curves. In: C.\u00a0Cid, M.J.J. Jr. (eds.) Selected Areas in Cryptography\u2014SAC 2018, Lecture Notes in Computer Science, vol. 11349, pp. 322\u2013343. Springer (2018). https:\/\/doi.org\/10.1007\/978-3-030-10970-7_15","DOI":"10.1007\/978-3-030-10970-7_15"},{"key":"271_CR2","unstructured":"Adj, G., Chi-Dom\u00ednguez, J., Rodr\u00edguez-Henr\u00edquez, F.: On new V\u00e9lu\u2019s formulae and their applications to CSIDH and B-SIDH constant-time implementations. IACR Cryptol. ePrint Arch. 2020, 1109 (2020). https:\/\/eprint.iacr.org\/2020\/1109"},{"key":"271_CR3","unstructured":"Azarderakhsh, R., Campagna, M., Costello, C., De Feo, L., Hess, B., Jalali, A., Jao, D., Koziel, B., LaMacchia, B., Longa, P., Naehrig, M., Pereira, G., Renes, J., Soukharev, V., Urbanik, D.: Supersingular isogeny key encapsulation. second round candidate of the NIST\u2019s post-quantum cryptography standardization process (2017). https:\/\/sike.org\/"},{"key":"271_CR4","doi-asserted-by":"publisher","first-page":"041015","DOI":"10.1103\/PhysRevX.8.041015","volume":"8","author":"R Babbush","year":"2018","unstructured":"Babbush, R., Gidney, C., Berry, D.W., Wiebe, N., McClean, J., Paler, A., Fowler, A., Neven, H.: Encoding electronic spectra in quantum circuits with linear t complexity. Phys. Rev. X 8, 041015 (2018). https:\/\/doi.org\/10.1103\/PhysRevX.8.041015","journal-title":"Phys. Rev. X"},{"key":"271_CR5","unstructured":"(https:\/\/stats.stackexchange.com\/users\/173082\/ben) Ben O.N.: Distribution of urns for non-uniform distribution. Cross Validated. https:\/\/stats.stackexchange.com\/q\/463916. (version: 2020-05-06)"},{"key":"271_CR6","unstructured":"Bernstein, D.J., De Feo, L., Leroux, A., Smith, B.: Faster computation of isogenies of large prime degree. IACR Cryptol. ePrint Arch. 2020, 341 (2020). https:\/\/eprint.iacr.org\/2020\/341"},{"key":"271_CR7","doi-asserted-by":"publisher","unstructured":"Bernstein, D.J., Lange, T., Martindale, C., Panny, L.: Quantum circuits for the CSIDH: optimizing quantum evaluation of isogenies. In: Ishai, Y., Rijmen, V. (eds.) Advances in Cryptology - EUROCRYPT 2019 - Part II, Lecture Notes in Computer Science, vol. 11477, pp. 409\u2013441. Springer (2019). https:\/\/doi.org\/10.1007\/978-3-030-17656-3_15","DOI":"10.1007\/978-3-030-17656-3_15"},{"key":"271_CR8","doi-asserted-by":"crossref","unstructured":"Berry, D.W., Gidney, C., Motta, M., McClean, J.R., Babbush, R.: Qubitization of arbitrary basis quantum chemistry leveraging sparsity and low rank factorization. Quantum 3, 208 (2019)","DOI":"10.22331\/q-2019-12-02-208"},{"key":"271_CR9","doi-asserted-by":"publisher","unstructured":"Beullens, W., Kleinjung, T., Vercauteren, F.: Csi-fish: efficient isogeny based signatures through class group computations. In: Galbraith, S.D., Moriai, S (eds.) Advances in Cryptology - ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Kobe, Japan, December 8-12, 2019, Proceedings, Part I, Lecture Notes in Computer Science, vol. 11921, pp. 227\u2013247. Springer (2019). https:\/\/doi.org\/10.1007\/978-3-030-34578-5_9","DOI":"10.1007\/978-3-030-34578-5_9"},{"key":"271_CR10","doi-asserted-by":"crossref","unstructured":"Biasse, J.F., Bonnetain, X., Pring, B., Schrottenloher, A., Youmans, W.: A trade-off between classical and quantum circuit size for an attack against CSIDH. J. Math. Cryptol. 1\u201316 (2019). (https:\/\/hal.inria.fr\/hal-02423394)","DOI":"10.1515\/jmc-2020-0070"},{"key":"271_CR11","unstructured":"Bonnetain, X.: Improved Low-qubit Hidden Shift Algorithms (2019). https:\/\/hal.inria.fr\/hal-02400414. Working paper or preprint"},{"key":"271_CR12","doi-asserted-by":"publisher","unstructured":"Bonnetain, X., Schrottenloher, A.: Quantum security analysis of CSIDH. In: Canteaut, A., Ishai, Y. (eds.) Advances in Cryptology - EUROCRYPT 2020-Part II, Lecture Notes in Computer Science, vol. 12106, pp. 493\u2013522. Springer (2020). https:\/\/doi.org\/10.1007\/978-3-030-45724-2_17","DOI":"10.1007\/978-3-030-45724-2_17"},{"key":"271_CR13","doi-asserted-by":"publisher","unstructured":"Castryck, W., Lange, T., Martindale, C., Panny, L., Renes, J.: CSIDH: an efficient post-quantum commutative group action. In: Peyrin, T., Galbraith, S.D. (eds.) Advances in Cryptology - ASIACRYPT 2018 -Part III, Lecture Notes in Computer Science, vol. 11274, pp. 395\u2013427. Springer (2018). https:\/\/doi.org\/10.1007\/978-3-030-03332-3_15","DOI":"10.1007\/978-3-030-03332-3_15"},{"key":"271_CR14","doi-asserted-by":"publisher","unstructured":"Cervantes-V\u00e1zquez, D., Chenu, M., Chi-Dom\u00ednguez, J., De Feo, L., Rodr\u00edguez-Henr\u00edquez, F., Smith, B.: Stronger and faster side-channel protections for CSIDH. In: Schwabe, P., Th\u00e9riault, N. (eds.) Progress in Cryptology\u2014LATINCRYPT 2019, Lecture Notes in Computer Science, vol. 11774, pp. 173\u2013193. Springer (2019). https:\/\/doi.org\/10.1007\/978-3-030-30530-7_9","DOI":"10.1007\/978-3-030-30530-7_9"},{"key":"271_CR15","unstructured":"Chi-Dom\u00ednguez, J., Rodr\u00edguez-Henr\u00edquez, F.: Optimal strategies for CSIDH. IACR Cryptol. ePrint Arch. 2020, 417 (2020). https:\/\/eprint.iacr.org\/2020\/417"},{"issue":"1","key":"271_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1515\/jmc-2012-0016","volume":"8","author":"AM Childs","year":"2014","unstructured":"Childs, A.M., Jao, D., Soukharev, V.: Constructing elliptic curve isogenies in quantum subexponential time. J. Math. Cryptol. 8(1), 1\u201329 (2014). https:\/\/doi.org\/10.1515\/jmc-2012-0016","journal-title":"J. Math. Cryptol."},{"key":"271_CR17","doi-asserted-by":"publisher","unstructured":"Costello, C., Hisil, H.: A simple and compact algorithm for SIDH with arbitrary degree isogenies. In: Takagi, T., Peyrin, T. (eds.) Advances in Cryptology\u2014ASIACRYPT 2017, Part II, Lecture Notes in Computer Science, vol. 10625, pp. 303\u2013329. Springer (2017). https:\/\/doi.org\/10.1007\/978-3-319-70697-9_11","DOI":"10.1007\/978-3-319-70697-9_11"},{"key":"271_CR18","doi-asserted-by":"crossref","unstructured":"Davenport, J.H., Pring, B.: Improvements to quantum search techniques for block-ciphers, with applications to AES. In: Jacobson, M.J. Jr., Dunkelman, O., O\u2019Flynn, C. (eds.) Selected Areas in Cryptography - SAC 2020, Lecture Notes in Computer Science. Springer (2020)","DOI":"10.1007\/978-3-030-81652-0_14"},{"key":"271_CR19","doi-asserted-by":"crossref","unstructured":"De Feo, L., Galbraith, S.D.: Seasign: compact isogeny signatures from class group actions. In: Ishai, Y., Rijmen, V. (eds.) Advances in Cryptology - EUROCRYPT 2019, Part III, Lecture Notes in Computer Science, vol. 11478, pp. 759\u2013789. Springer (2019)","DOI":"10.1007\/978-3-030-17659-4_26"},{"issue":"2","key":"271_CR20","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1007\/s10623-014-0010-1","volume":"78","author":"C Delfs","year":"2016","unstructured":"Delfs, C., Galbraith, S.D.: Computing isogenies between supersingular elliptic curves over $$\\mathbb{f}_{\\text{ p }}$$. Des. Codes Cryptogr. 78(2), 425\u2013440 (2016). https:\/\/doi.org\/10.1007\/s10623-014-0010-1","journal-title":"Des. Codes Cryptogr."},{"issue":"9","key":"271_CR21","doi-asserted-by":"publisher","first-page":"4452","DOI":"10.1063\/1.1499754","volume":"43","author":"E Dennis","year":"2002","unstructured":"Dennis, E., Kitaev, A., Landahl, A., Preskill, J.: Topological quantum memory. J. Math. Phys. 43(9), 4452\u20134505 (2002). https:\/\/doi.org\/10.1063\/1.1499754","journal-title":"J. Math. Phys."},{"key":"271_CR22","unstructured":"Gidney, C.: Spooky pebble games and irreversible uncomputation. https:\/\/algassert.com\/post\/1905. (2019, Aug 19)"},{"key":"271_CR23","unstructured":"Gidney, C., Eker\u00e5, M.: How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2019). arxiv:1905.09749"},{"key":"271_CR24","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1007\/978-3-030-44223-1_23","volume-title":"Post-Quantum Cryptography","author":"T H\u00e4ner","year":"2020","unstructured":"H\u00e4ner, T., Jaques, S., Naehrig, M., Roetteler, M., Soeken, M.: Improved Quantum Circuits for Elliptic Curve Discrete Logarithms. In: Ding, J., Tillich, J.P. (eds.) Post-Quantum Cryptography, pp. 425\u2013444. Springer International Publishing, Cham (2020)"},{"key":"271_CR25","doi-asserted-by":"publisher","unstructured":"Jaques, S., Naehrig, M., Roetteler, M., Virdia, F.: Implementing grover oracles for quantum key search on AES and LowMC. In: Canteaut, A., Ishai, Y. (eds.) Advances in Cryptology - EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10-14, 2020, Proceedings, Part II, Lecture Notes in Computer Science, vol. 12106, pp. 280\u2013310. Springer (2020). https:\/\/doi.org\/10.1007\/978-3-030-45724-2_10","DOI":"10.1007\/978-3-030-45724-2_10"},{"key":"271_CR26","doi-asserted-by":"publisher","unstructured":"Jaques, S., Schanck, J.M.: Quantum cryptanalysis in the RAM model: claw-finding attacks on SIKE. In: Boldyreva, A., Micciancio, D. (eds.) Advances in Cryptology - CRYPTO 2019 - 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2019, Proceedings, Part I, Lecture Notes in Computer Science, vol. 11692, pp. 32\u201361. Springer (2019). https:\/\/doi.org\/10.1007\/978-3-030-26948-7_2","DOI":"10.1007\/978-3-030-26948-7_2"},{"key":"271_CR27","unstructured":"Knill, E.: An analysis of Bennett\u2019s pebble game, arXiv:math\/9508218 (1992)"},{"key":"271_CR28","unstructured":"Kohel, D.R.: Endomorphism rings of elliptic curves over finite fields. Ph.D. thesis, University of California at Berkeley, The address of the publisher (1996). http:\/\/iml.univ-mrs.fr\/~kohel\/pub\/thesis.pdf"},{"key":"271_CR29","doi-asserted-by":"publisher","unstructured":"Kuperberg, G.: A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. SIAM J. Comput. 35(1), 170\u2013188 (2005). https:\/\/doi.org\/10.1137\/S0097539703436345","DOI":"10.1137\/S0097539703436345"},{"key":"271_CR30","doi-asserted-by":"publisher","unstructured":"Kuperberg, G.: Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem. In: TQC 2013, LIPIcs 22, pp. 20\u201334 (2013). https:\/\/doi.org\/10.4230\/LIPIcs.TQC.2013.20","DOI":"10.4230\/LIPIcs.TQC.2013.20"},{"key":"271_CR31","unstructured":"Longa, P.: Practical quantum-resistant key exchange from supersingular isogenies and its efficient implementation. Latincrypt 2019 Invited Talk. http:\/\/latincrypt2019.cryptojedi.org\/slides\/latincrypt2019-patrick-longa.pdf (2019)"},{"key":"271_CR32","doi-asserted-by":"publisher","unstructured":"Meyer, M., Campos, F., Reith, S.: In: Ding, J., Steinwandt, R. (eds.) Post-Quantum Cryptography, vol. 11505, pp. 307\u2013325. (Springer (2019).). https:\/\/doi.org\/10.1007\/978-3-030-25510-7_17","DOI":"10.1007\/978-3-030-25510-7_17"},{"key":"271_CR33","doi-asserted-by":"publisher","unstructured":"Meyer, M., Reith, S.: A faster way to the CSIDH. In: Chakraborty, D., Iwata, T. (eds.) Progress in cryptology\u2014INDOCRYPT 2018\u201419th International Conference on Cryptology in India, New Delhi, India, December 9-12, 2018, Proceedings, Lecture Notes in Computer Science, vol. 11356, pp. 137\u2013152. Springer (2018). https:\/\/doi.org\/10.1007\/978-3-030-05378-9_8","DOI":"10.1007\/978-3-030-05378-9_8"},{"key":"271_CR34","doi-asserted-by":"publisher","unstructured":"Moody, D., Shumow, D.: Analogues of V\u00e9lu\u2019s formulas for isogenies on alternate models of elliptic curves. Math. Comput. 85(300), 1929\u20131951 (2016). https:\/\/doi.org\/10.1090\/mcom\/3036","DOI":"10.1090\/mcom\/3036"},{"key":"271_CR35","doi-asserted-by":"publisher","unstructured":"Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information: 10th Anniversary Edition, 10th edn. Cambridge University Press, USA (2011). https:\/\/doi.org\/10.5555\/1388394","DOI":"10.5555\/1388394"},{"key":"271_CR36","unstructured":"NIST: NIST Post-Quantum: Cryptography Standardization Process. Third Round Candidates , http:\/\/csrc.nist.gov\/projects\/post-quantum-cryptography\/round-3-submissions (2020)"},{"key":"271_CR37","doi-asserted-by":"publisher","unstructured":"Onuki, H., Aikawa, Y., Yamazaki, T., Takagi, T.: (short paper) A faster constant-time algorithm of CSIDH keeping two points. In: N.\u00a0Attrapadung, T.\u00a0Yagi (eds.) Advances in Information and Computer Security - 14th International Workshop on Security, IWSEC 2019, Lecture Notes in Computer Science, vol. 11689, pp. 23\u201333. Springer (2019). https:\/\/doi.org\/10.1007\/978-3-030-26834-3_2","DOI":"10.1007\/978-3-030-26834-3_2"},{"key":"271_CR38","doi-asserted-by":"publisher","unstructured":"Peikert, C.: He gives c-sieves on the CSIDH. In: Canteaut, A., Ishai, Y. (eds.) Advances in Cryptology - EUROCRYPT 2020 - Part II, Lecture Notes in Computer Science, vol. 12106, pp. 463\u2013492. Springer (2020). https:\/\/doi.org\/10.1007\/978-3-030-45724-2_16","DOI":"10.1007\/978-3-030-45724-2_16"},{"key":"271_CR39","unstructured":"Regev, O.: A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space 0406151,(2004)"},{"key":"271_CR40","unstructured":"Schanck, J.M.: Improving post-quantum cryptography through cryptanalysis, p. jmschanck.info\/papers\/20200703-phd-thesis.pdf. University of Waterloo, Waterloo, Ontario, Canada (2020). (Ph.D. thesis)"},{"key":"271_CR41","doi-asserted-by":"publisher","unstructured":"van Oorschot, P.C., Wiener, M.J.: Parallel collision search with cryptanalytic applications. J. Cryptol. 12(1), 1\u201328 (1999). https:\/\/doi.org\/10.1007\/PL00003816","DOI":"10.1007\/PL00003816"},{"key":"271_CR42","doi-asserted-by":"publisher","unstructured":"Washington, L.C.: Elliptic Curves: Number Theory and Cryptography, Second Edition, 2 edn. Chapman & Hall\/CRC (2008). https:\/\/doi.org\/10.5555\/1388394","DOI":"10.5555\/1388394"}],"container-title":["Journal of Cryptographic Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13389-021-00271-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s13389-021-00271-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13389-021-00271-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,10]],"date-time":"2022-09-10T13:20:10Z","timestamp":1662816010000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s13389-021-00271-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,31]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["271"],"URL":"https:\/\/doi.org\/10.1007\/s13389-021-00271-w","relation":{},"ISSN":["2190-8508","2190-8516"],"issn-type":[{"value":"2190-8508","type":"print"},{"value":"2190-8516","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,31]]},"assertion":[{"value":"18 January 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 July 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 August 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"This project has received funding from the European Research Council (ERC) under the European Union\u2019s Horizon 2020 research and innovation programme (grant agreement No 804476). S. Jaques was supported by the University of Oxford Clarendon fund.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Funding"}},{"value":"The authors have no conflicts of interest to declare.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of interest"}},{"value":"Run-time data is not available.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Availability of data and material"}},{"value":"Code for quantum security estimates and a software library for key exchange is available at .","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code availability"}}]}}