{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,16]],"date-time":"2026-08-16T11:32:35Z","timestamp":1786879955526,"version":"3.56.0"},"reference-count":20,"publisher":"International Association for Cryptologic Research","license":[{"start":{"date-parts":[[2024,6,14]],"date-time":"2024-06-14T00:00:00Z","timestamp":1718323200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2024,9,2]]},"abstract":" This work introduces several algorithms related to the computation of orientations in endomorphism rings of supersingular elliptic curves. This problem is at the heart of several results regarding the security of oriented-curves in isogeny-based cryptography. Under the Deuring correspondence, it can be expressed purely in terms of quaternion and boils down to representing integers by ternary quadratic forms. Our main contribution is to show that there exist efficient algorithms to solve this problem for quadratic orders of discriminant \n \n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math> up to \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n p<\/mml:mi>\n \n 4<\/mml:mn>\n \/<\/mml:mo>\n 3<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>. Our approach improves upon previous results by increasing this bound from \n \n O<\/mml:mi>\n (<\/mml:mo>\n p<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math> to \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n p<\/mml:mi>\n \n 4<\/mml:mn>\n \/<\/mml:mo>\n 3<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math> and removing some heuristics. We introduce several variants of our new algorithm and provide a careful analysis of their asymptotic running time (without heuristic when it is possible). The best proven asymptotic complexity of one of our variants is \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n \n 3<\/mml:mn>\n \/<\/mml:mo>\n 4<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \/<\/mml:mo>\n p<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math> in average. The best heuristic variant has a complexity of \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n p<\/mml:mi>\n \n 1<\/mml:mn>\n \/<\/mml:mo>\n 3<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math> for big enough \n \n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>. We then introduce several results regarding the computation of ideals between oriented orders. The first application of this is a simplification of the known reduction from vectorization to computing the endomorphism ring, removing the assumption on the factorization of the discriminant. As a second application, we relate the problem of computing fixed-degree isogenies between supersingular curves to the problem of computing orientations in endomorphism rings, and we show that for a large range of degree \n \n d<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>, our new algorithms improve on the state-of-the-art, and in important special cases, the range of degree \n \n d<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math> for which there exist a polynomial-time algorithm is increased. In the most special case we consider, when both curves are oriented by a small degree endomorphism, we show heuristically that our techniques allow the computation of isogenies of any degree, assuming they exist. <\/jats:p>","DOI":"10.62056\/ae0fhbmo","type":"journal-article","created":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T15:13:33Z","timestamp":1728314013000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":5,"title":["Computing Orientations from the Endomorphism Ring of Supersingular Curves and Applications"],"prefix":"10.62056","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-3040-2965","authenticated-orcid":false,"given":"Jonathan","family":"Eriksen","sequence":"first","affiliation":[{"name":"Norwegian University of Science and Technology","place":["Trondheim, Norway"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-3737-0075","authenticated-orcid":false,"given":"Antonin","family":"Leroux","sequence":"additional","affiliation":[{"name":"DGA-MI","place":["France"]},{"name":"Universit\u00e9 de Rennes","place":["France"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"48349","published-online":{"date-parts":[[2024,10,7]]},"reference":[{"key":"ref1:CSIDH","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/978-3-030-03332-3_15","article-title":"CSIDH: An Efficient Post-Quantum Commutative Group\n Action","volume":"11274","author":"Wouter Castryck","year":"2018"},{"key":"ref2:OSIDH","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1515\/JMC-2019-0034","article-title":"Orienting supersingular isogeny graphs","volume":"14","author":"Leonardo Col\u00f2","year":"2020","journal-title":"J. Math. Cryptol."},{"key":"ref3:SCALLOP","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/978-3-031-31368-4_13","article-title":"SCALLOP: Scaling the CSI-FiSh","volume":"13940","author":"Luca De Feo","year":"2023"},{"key":"ref4:onuki","doi-asserted-by":"publisher","first-page":"101777","DOI":"10.1016\/J.FFA.2020.101777","article-title":"On oriented supersingular elliptic curves","volume":"69","author":"Hiroshi Onuki","year":"2021","journal-title":"Finite Fields Their Appl."},{"key":"ref5:wesolowski2022orientations","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/978-3-031-07082-2_13","article-title":"Orientations and the Supersingular Endomorphism Ring\n Problem","volume":"13277","author":"Benjamin Wesolowski","year":"2022"},{"key":"ref6:de2021seta","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/978-3-030-92068-5_9","article-title":"S\u00e9ta: Supersingular Encryption from Torsion Attacks","volume":"13093","author":"Luca De Feo","year":"2021"},{"key":"ref7:arpin2023finding","doi-asserted-by":"publisher","DOI":"10.1007\/s10623-024-01435-5","article-title":"Finding orientations of supersingular elliptic curves and\n quaternion orders","author":"Sarah Arpin","year":"2024","journal-title":"Designs, Codes and Cryptography","ISSN":"https:\/\/id.crossref.org\/issn\/1573-7586","issn-type":"electronic"},{"key":"ref8:leroux2022effective","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/978-3-031-58411-4_12","article-title":"An Effective Lower Bound on the Number of Orientable\n Supersingular Elliptic Curves","volume":"13742","author":"Antonin Leroux","year":"2022"},{"key":"ref9:KLPT14","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1112\/S1461157014000151","article-title":"On the quaternion $\\ell$-isogeny path problem","volume":"17","author":"David Kohel","year":"2014","journal-title":"LMS J. Comput. Math."},{"key":"ref10:EHLMP18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/978-3-319-78372-7_11","article-title":"Supersingular Isogeny Graphs and Endomorphism Rings:\n Reductions and Solutions","volume":"10822","author":"Kirsten Eisentr\u00e4ger","year":"2018"},{"key":"ref11:FKLPW20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1007\/978-3-030-64837-4_3","article-title":"SQISign: Compact Post-quantum Signatures from Quaternions\n and Isogenies","volume":"12491","author":"Luca De Feo","year":"2020"},{"key":"ref12:fixed-degree-isogenies","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/978-3-031-68388-6_8","article-title":"Improved Algorithms for Finding Fixed-Degree Isogenies\n Between Supersingular Elliptic Curves","volume":"14924","author":"Benjamin Bencina","year":"2024"},{"key":"ref13:sage","volume-title":"SageMath, the Sage Mathematics Software System\n (version 9.7)","author":"The Sage Developers","year":"2022"},{"key":"ref14:K96","volume-title":"Endomorphism rings of elliptic curves over finite fields","author":"D. Kohel","year":"1996"},{"key":"ref15:BL19","doi-asserted-by":"publisher","first-page":"7","DOI":"10.2140\/obs.2020.4.7","article-title":"Supersingular curves with small noninteger endomorphisms","volume":"4","author":"Jonathan Love","year":"2020","journal-title":"Open Book Series","ISSN":"https:\/\/id.crossref.org\/issn\/2329-9061","issn-type":"electronic"},{"key":"ref16:voight","volume-title":"Quaternion Algebras","author":"John Voight","year":"2018"},{"key":"ref17:leroux2022new","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-031-22966-4_1","article-title":"A New Isogeny Representation and Applications to\n Cryptography","volume":"13792","author":"Antonin Leroux","year":"2022"},{"key":"ref18:wigert1907ordre","volume-title":"Sur l'ordre de grandeur du nombre des diviseurs d'un\n entier","author":"Carl Severin Wigert","year":"1907"},{"key":"ref19:CVP20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1007\/978-3-030-45724-2_18","article-title":"Rational Isogenies from Irrational Endomorphisms","volume":"12106","author":"Wouter Castryck","year":"2020"},{"key":"ref20:clapotis","first-page":"1766","article-title":"Introducing Clapoti(s): Evaluating the isogeny class group\n action in polynomial time","author":"Aurel Page","year":"2023","journal-title":"IACR Cryptol. ePrint Arch."}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T21:28:07Z","timestamp":1733866087000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/1\/3\/5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,7]]},"references-count":20,"URL":"https:\/\/doi.org\/10.62056\/ae0fhbmo","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,7]]},"assertion":[{"value":"2024-06-14","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc1-3-7"}}