{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,30]],"date-time":"2026-07-30T18:23:55Z","timestamp":1785435835671,"version":"3.56.0"},"reference-count":49,"publisher":"International Association for Cryptologic Research","issue":"1","license":[{"start":{"date-parts":[[2024,10,9]],"date-time":"2024-10-09T00:00:00Z","timestamp":1728432000000},"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":[[2025,3,11]]},"abstract":"<jats:p>Given a supersingular elliptic curve E and a non-scalar endomorphism \u03b1 of E, we prove that the endomorphism ring of E can be computed in classical time about disc(Z[\u03b1])^1\/4, and in quantum subexponential time, assuming the generalised Riemann hypothesis. Previous results either had higher complexities, or relied on heuristic assumptions.<\/jats:p>\n                  <jats:p>Along the way, we describe and analyse a general algorithm to divide isogenies in polynomial time, and to solve the Primitivisation problem in polynomial time. Following the attacks on SIDH, isogenies in high dimension are a central ingredient of our results.<\/jats:p>","DOI":"10.62056\/akgyivrzn","type":"journal-article","created":{"date-parts":[[2025,4,8]],"date-time":"2025-04-08T17:23:17Z","timestamp":1744132997000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":2,"title":["The supersingular endomorphism ring problem given one endomorphism"],"prefix":"10.62056","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-6116-6863","authenticated-orcid":false,"given":"Arthur","family":"Le Merdy","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05n21n105","id-type":"ROR","asserted-by":"publisher"}],"name":"ENS de Lyon, CNRS, UMPA, UMR 5669","place":["Lyon, France"]},{"id":[{"id":"https:\/\/ror.org\/04msnz457","id-type":"ROR","asserted-by":"publisher"}],"name":"ENS de Lyon, LIP (CNRS, U. Lyon, ENS de Lyon, Inria, UCBL), UMR 5668","place":["Lyon, France"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1249-6077","authenticated-orcid":false,"given":"Benjamin","family":"Wesolowski","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05n21n105","id-type":"ROR","asserted-by":"publisher"}],"name":"ENS de Lyon, CNRS, UMPA, UMR 5669","place":["Lyon, France"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"48349","published-online":{"date-parts":[[2025,4,8]]},"reference":[{"key":"ref1:EC: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":"ref2:wesolowski_supersingular_2022","doi-asserted-by":"publisher","first-page":"1100","DOI":"10.1109\/FOCS52979.2021.00109","article-title":"The supersingular isogeny path and endomorphism ring\n  problems are equivalent","author":"Benjamin Wesolowski","year":"2022"},{"key":"ref3:charles_cryptographic_2009","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/s00145-007-9002-x","article-title":"Cryptographic hash functions from expander graphs","volume":"22","author":"Denis X Charles","year":"2009","journal-title":"Journal of CRYPTOLOGY"},{"key":"ref4:AC:CLMPR18","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":"ref5:EC:CasPanVer20","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":"ref6:EC:Wesolowski22","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":"ref7:AC:DKLPW20","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":"ref8:chenu_higher-degree_2022","first-page":"85","article-title":"Higher-degree supersingular group actions","volume":"1","author":"Mathilde Chenu","year":"2022","journal-title":"Mathematical Cryptology"},{"key":"ref9:PKC:DFKLMP23","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":"ref10:arpin_orienteering_2023","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1007\/s44007-023-00053-2","article-title":"Orienteering with one endomorphism","volume":"2","author":"Sarah Arpin","year":"2023","journal-title":"Matematica","ISSN":"https:\/\/id.crossref.org\/issn\/2730-9657","issn-type":"electronic"},{"key":"ref11:colo_orienting_2020","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1515\/jmc-2019-0034","article-title":"Orienting supersingular isogeny graphs","volume":"14","author":"Leonardo Colo","year":"2020","journal-title":"Journal of Mathematical Cryptology"},{"key":"ref12:couveignes_hard_2006","first-page":"291","article-title":"Hard homogeneous spaces","author":"Jean-Marc Couveignes","year":"2006","journal-title":"Cryptology ePrint Archive"},{"key":"ref13:rostovtsev_public-key_2006","first-page":"145","article-title":"Public-key cryptosystem based on isogenies","author":"Alexander Rostovtsev","year":"2006","journal-title":"Cryptology ePrint Archive"},{"key":"ref14:silverman_arithmetic_1986","series-title":"Graduate texts in mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-1920-8","volume-title":"The arithmetic of elliptic curves","volume":"106","author":"Joseph H. Silverman","year":"1986","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540962038"},{"key":"ref15:eisentrager_computing_2020","doi-asserted-by":"publisher","first-page":"215","DOI":"10.2140\/obs.2020.4.215","article-title":"Computing endomorphism rings of supersingular elliptic\n  curves and connections to path-finding in isogeny graphs","volume":"4","author":"Kirsten Eisentr\u00e4ger","year":"2020","journal-title":"Open Book Series"},{"key":"ref16:INDOCRYPT:BiaJaoSan14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1007\/978-3-319-13039-2_25","article-title":"A Quantum Algorithm for Computing Isogenies between\n  Supersingular Elliptic Curves","volume":"8885","author":"Jean-Fran\u00e7ois Biasse","year":"2014"},{"key":"ref17:AC:BeuKleVer19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/978-3-030-34578-5_9","article-title":"CSI-FiSh: Efficient Isogeny Based Signatures Through\n  Class Group Computations","volume":"11921","author":"Ward Beullens","year":"2019"},{"key":"ref18:PQCRYPTO:CasDec20","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/978-3-030-44223-1_7","article-title":"CSIDH on the Surface","author":"Wouter Castryck","year":"2020"},{"key":"ref19:DCC:DelGal16","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1007\/s10623-014-0010-1","article-title":"Computing isogenies between supersingular elliptic curves\n  over $\\mathbb{F}_p$","volume":"78","author":"Christina Delfs","year":"2016","journal-title":"Designs, Codes and Cryptography"},{"key":"ref20:robert_applications_2022","first-page":"1704","article-title":"Some applications of higher dimensional isogenies to\n  elliptic curves (preliminary version)","author":"Damien Robert","year":"2022","journal-title":"Cryptology ePrint Archive"},{"key":"ref21:childs_constructing_2014","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1515\/jmc-2012-0016","article-title":"Constructing elliptic curve isogenies in quantum\n  subexponential time","volume":"8","author":"Andrew Childs","year":"2014","journal-title":"Journal of Mathematical Cryptology"},{"key":"ref22:voight_quaternion_2021","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-030-56694-4","volume-title":"Quaternion algebras","author":"John Voight","year":"2021"},{"key":"ref23:onuki_oriented_2021","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 and Their Applications"},{"key":"ref24:wesolowski_random_2024","volume-title":"Random Walks in Number-theoretic Cryptology","author":"Benjamin Wesolowski","year":"2024"},{"key":"ref25:EC:Robert23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"472","DOI":"10.1007\/978-3-031-30589-4_17","article-title":"Breaking SIDH in Polynomial Time","volume":"14008","author":"Damien Robert","year":"2023"},{"key":"ref26:robert_efficient_2024","first-page":"1071","article-title":"On the efficient representation of isogenies (a survey)","author":"Damien Robert","year":"2024","journal-title":"Cryptology ePrint Archive"},{"key":"ref27:EC:PagWes24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1007\/978-3-031-58751-1_14","article-title":"The Supersingular Endomorphism Ring and One Endomorphism\n  Problems are Equivalent","volume":"14656","author":"Aurel Page","year":"2024"},{"key":"ref28:kohel_endomorphism_1996","isbn-type":"print","first-page":"117","volume-title":"Endomorphism rings of elliptic curves over finite fields","author":"David Russell Kohel","year":"1996","ISBN":"https:\/\/id.crossref.org\/isbn\/9780591321234"},{"key":"ref29:milne_abelian_1986","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1007\/978-1-4613-8655-1_5","article-title":"Abelian varieties","author":"James S Milne","year":"1986","journal-title":"Arithmetic geometry"},{"key":"ref30:EC:CasDec23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1007\/978-3-031-30589-4_15","article-title":"An Efficient Key Recovery Attack on SIDH","volume":"14008","author":"Wouter Castryck","year":"2023"},{"key":"ref31:lubicz_computing_2012","doi-asserted-by":"publisher","first-page":"1483","DOI":"10.1112\/S0010437X12000243","article-title":"Computing isogenies between abelian varieties","volume":"148","author":"David Lubicz","year":"2012","journal-title":"Compositio Mathematica"},{"key":"ref32:robert_evaluating_2022","first-page":"1068","article-title":"Evaluating isogenies in polylogarithmic time","author":"Damien Robert","year":"2022","journal-title":"Cryptology ePrint Archive"},{"key":"ref33:EC:DLRW24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-031-58716-0_1","article-title":"SQIsignHD: New Dimensions in Cryptography","volume":"14651","author":"Pierrick Dartois","year":"2024"},{"key":"ref34:robert_efficient_2021","volume-title":"Efficient algorithms for abelian varieties and their moduli\n  spaces","author":"Damien Robert","year":"2021"},{"key":"ref35:velu_isogenies_1971","first-page":"238","article-title":"Isog\u00e9nies entre courbes elliptiques","volume":"t. 273","author":"Jacques V\u00e9lu","year":"1971","journal-title":"C. R. Acad. Sc. Paris, S\u00e9rie A"},{"key":"ref36:kani_number_1997","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1515\/crll.1997.485.93","article-title":"The number of curves of genus two with elliptic\n  differentials.","volume":"485","author":"Ernst Kani","year":"1997","journal-title":"Journal f\u00fcr die reine und angewandte Mathematik"},{"key":"ref37:EC:MMPPW23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1007\/978-3-031-30589-4_16","article-title":"A Direct Key Recovery Attack on SIDH","volume":"14008","author":"Luciano Maino","year":"2023"},{"key":"ref38:lubicz_fast_2023","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1007\/s40993-022-00407-9","article-title":"Fast change of level and applications to isogenies","volume":"9","author":"David Lubicz","year":"2023","journal-title":"Research in Number Theory"},{"key":"ref39:zarhin_remark_1974","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1070\/IM1974v008n03ABEH002115","article-title":"A remark on endomorphisms of abelian varieties over function\n  fields of finite characteristic","volume":"8","author":"Ju G Zarhin","year":"1974","journal-title":"Mathematics of the USSR-Izvestiya"},{"key":"ref40:david_mumford_abelian_1970","volume-title":"Abelian Varieties","author":"David Mumford","year":"1970"},{"key":"ref41:pollack_finding_2018","first-page":"7","article-title":"Finding the Four Squares in Lagrange's Theorem.","volume":"18","author":"Paul Pollack","year":"2018","journal-title":"Integers"},{"key":"ref42:PKC:CheLerPan24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1007\/978-3-031-57725-3_7","article-title":"SCALLOP-HD: Group Action from 2-Dimensional Isogenies","volume":"14603","author":"Mingjie Chen","year":"2024"},{"key":"ref43:page_introducing_2023","first-page":"1766","article-title":"Introducing Clapoti (s): Evaluating the isogeny class\n  group action in polynomial time","author":"Aurel Page","year":"2023","journal-title":"Cryptology ePrint Archive"},{"key":"ref44:AC:DDFKLP21","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":"ref45:DCC:BisSut12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10623-011-9527-8","article-title":"A low-memory algorithm for finding short product\n  representations in finite groups","volume":"63","author":"Gaetan Bisson","year":"2012","journal-title":"Designs, Codes and Cryptography"},{"key":"ref46:arpin_orientations_2024","series-title":"Assoc. Women Math. Ser.","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/978-3-031-51677-1_2","article-title":"Orientations and cycles in supersingular isogeny graphs","volume":"33","author":"Sarah Arpin","year":"2024"},{"key":"ref47:pomerance_fast_1987","series-title":"Perspect. Comput.","first-page":"119","article-title":"Fast, rigorous factorization and discrete logarithm\n  algorithms","volume":"15","author":"Carl Pomerance","year":"1987"},{"key":"ref48:kuperberg_subexponential-time_2005","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1137\/S0097539703436345","article-title":"A subexponential-time quantum algorithm for the dihedral\n  hidden subgroup problem","volume":"35","author":"Greg Kuperberg","year":"2005","journal-title":"SIAM Journal on Computing"},{"key":"ref49:biasse_efficient_2016","isbn-type":"print","doi-asserted-by":"publisher","first-page":"893","DOI":"10.1137\/1.9781611974331.ch64","article-title":"Efficient quantum algorithms for computing class groups and\n  solving the principal ideal problem in arbitrary degree number fields","author":"Jean-Fran\u00e7ois Biasse","year":"2016","ISBN":"https:\/\/id.crossref.org\/isbn\/9781611974331"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,4,8]],"date-time":"2025-04-08T17:23:37Z","timestamp":1744133017000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/2\/1\/6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,8]]},"references-count":49,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,4,8]]}},"URL":"https:\/\/doi.org\/10.62056\/akgyivrzn","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,8]]},"assertion":[{"value":"2024-10-09","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-11","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc1-4-73"}}