{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:36:32Z","timestamp":1764981392941,"version":"3.46.0"},"reference-count":21,"publisher":"Walter de Gruyter GmbH","issue":"1","license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,6,14]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>We present a quantum algorithm which computes group action inverses of the complex multiplication group action on isogenous ordinary elliptic curves, using subexponential time, but only polynomial quantum space. One application of this algorithm is that it can be used to find the private key from the public key in the isogeny-based CRS and CSIDH cryptosystems. Prior claims by Childs, Jao, and Soukharev of such a polynomial quantum space algorithm for this problem are false; our algorithm (along with contemporaneous, independent work by Biasse, Iezzi, and Jacobson) is the first such result.<\/jats:p>","DOI":"10.1515\/jmc-2015-0057","type":"journal-article","created":{"date-parts":[[2020,6,15]],"date-time":"2020-06-15T13:48:20Z","timestamp":1592228900000},"page":"129-138","source":"Crossref","is-referenced-by-count":4,"title":["A subexponential-time, polynomial quantum space algorithm for inverting the CM group action"],"prefix":"10.1515","volume":"14","author":[{"given":"David","family":"Jao","sequence":"first","affiliation":[{"name":"Department of Combinatorics and Optimization , University of Waterloo , Waterloo , Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jason","family":"LeGrow","sequence":"additional","affiliation":[{"name":"Department of Combinatorics and Optimization , University of Waterloo , Waterloo , Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christopher","family":"Leonardi","sequence":"additional","affiliation":[{"name":"Department of Combinatorics and Optimization , University of Waterloo , Waterloo , Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luis","family":"Ruiz-Lopez","sequence":"additional","affiliation":[{"name":"Department of Combinatorics and Optimization , University of Waterloo , Waterloo , Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"374","published-online":{"date-parts":[[2020,6,14]]},"reference":[{"key":"2025120600311350132_j_jmc-2015-0057_ref_001_w2aab3b7e1457b1b6b1ab2b1b1Aa","unstructured":"Jean-Fran\u00e7ois Biasse, Annamaria Iezzi and Michael J. Jacobson Jr., A note on the security of CSIDH, 2018."},{"key":"2025120600311350132_j_jmc-2015-0057_ref_002_w2aab3b7e1457b1b6b1ab2b1b2Aa","doi-asserted-by":"crossref","unstructured":"Avrim Blum, Adam Kalai and Hal Wasserman, Noise-tolerant Learning, the Parity Problem, and the Statistical Query Model, J. ACM50 (2003), 506\u2013519.","DOI":"10.1145\/792538.792543"},{"key":"2025120600311350132_j_jmc-2015-0057_ref_003_w2aab3b7e1457b1b6b1ab2b1b3Aa","unstructured":"Xavier Bonnetain and Andr\u00e9 Schrottenloher, Quantum Security Analysis of CSIDH and Ordinary Isogeny-based Schemes, Cryptology ePrint Archive, Report 2018\/537, 2018, https:\/\/eprint.iacr.org\/2018\/537."},{"key":"2025120600311350132_j_jmc-2015-0057_ref_004_w2aab3b7e1457b1b6b1ab2b1b4Aa","doi-asserted-by":"crossref","unstructured":"Wouter Castryck, Tanja Lange, Chloe Martindale, Lorenz Panny and Joost Renes, CSIDH: An Efficient Post-Quantum Commutative Group Action, Cryptology ePrint Archive, Report 2018\/383, 2018, https:\/\/eprint.iacr.org\/2018\/383.","DOI":"10.1007\/978-3-030-03332-3_15"},{"key":"2025120600311350132_j_jmc-2015-0057_ref_005_w2aab3b7e1457b1b6b1ab2b1b5Aa","doi-asserted-by":"crossref","unstructured":"Denis X. Charles, Kristin E. Lauter and Eyal Z. Goren, Cryptographic Hash Functions from Expander Graphs, Journal of Cryptology22 (2009), 93\u2013113.","DOI":"10.1007\/s00145-007-9002-x"},{"key":"2025120600311350132_j_jmc-2015-0057_ref_006_w2aab3b7e1457b1b6b1ab2b1b6Aa","unstructured":"Andrew Childs, David Jao and Vladimir Soukharev, Constructing elliptic curve isogenies in quantum subexponential time, eprint arXiv:quant-ph\/0406151, 2010, https:\/\/arxiv.org\/abs\/1012.4019v3."},{"key":"2025120600311350132_j_jmc-2015-0057_ref_007_w2aab3b7e1457b1b6b1ab2b1b7Aa","doi-asserted-by":"crossref","unstructured":"Andrew Childs, David Jao and Vladimir Soukharev, Constructing elliptic curve isogenies in quantum subexponential time, J. Math. Cryptol8 (2014), 1\u201329.","DOI":"10.1515\/jmc-2012-0016"},{"key":"2025120600311350132_j_jmc-2015-0057_ref_008_w2aab3b7e1457b1b6b1ab2b1b8Aa","doi-asserted-by":"crossref","unstructured":"Henri Cohen and Hendrik W. Lenstra Jr., Heuristics on class groups of number fields, Number theory, Noordwijkerhout 1983 (Noordwijkerhout, 1983), Lecture Notes in Math. 1068 (1984), 33\u201362.","DOI":"10.1007\/BFb0099440"},{"key":"2025120600311350132_j_jmc-2015-0057_ref_009_w2aab3b7e1457b1b6b1ab2b1b9Aa","unstructured":"Jean-Marc Couveignes, Hard Homogeneous Spaces, Cryptology ePrint Archive, Report 2006\/291, 2006, https:\/\/eprint.iacr.org\/2006\/291."},{"key":"2025120600311350132_j_jmc-2015-0057_ref_010_w2aab3b7e1457b1b6b1ab2b1c10Aa","unstructured":"Luca De Feo, Jean Kieffer and Benjamin Smith, Towards practical key exchange from ordinary isogeny graphs, Cryptology ePrint Archive, Report 2018\/485, 2018, https:\/\/eprint.iacr.org\/2018\/485."},{"key":"2025120600311350132_j_jmc-2015-0057_ref_011_w2aab3b7e1457b1b6b1ab2b1c11Aa","unstructured":"Steven D. Galbraith and Frederik Vercauteren, Computational problems in supersingular elliptic curve isogenies, Cryptology ePrint Archive, Report 2017\/774, 2017, https:\/\/eprint.iacr.org\/2017\/774."},{"key":"2025120600311350132_j_jmc-2015-0057_ref_012_w2aab3b7e1457b1b6b1ab2b1c12Aa","doi-asserted-by":"crossref","unstructured":"David Jao, Stephen D. Miller and Ramarathnam Venkatesan, Expander graphs based on GRH with an application to elliptic curve cryptography, J. Number Theory129 (2009), 1491\u20131504.","DOI":"10.1016\/j.jnt.2008.11.006"},{"key":"2025120600311350132_j_jmc-2015-0057_ref_013_w2aab3b7e1457b1b6b1ab2b1c13Aa","doi-asserted-by":"crossref","unstructured":"Greg Kuperberg, A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem, SIAM Journal on Computing35 (2005), 170\u2013188.","DOI":"10.1137\/S0097539703436345"},{"key":"2025120600311350132_j_jmc-2015-0057_ref_014_w2aab3b7e1457b1b6b1ab2b1c14Aa","unstructured":"Greg Kuperberg, Another Subexponential-time Quantum Algorithm for the Dihedral Hidden Subgroup Problem, in: 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013) (Simone Severini and Fernando Brandao, eds.), Leibniz International Proceedings in Informatics (LIPIcs) 22, pp. 20\u201334, Schloss Dagstuhl, Dagstuhl, Germany, 2013."},{"key":"2025120600311350132_j_jmc-2015-0057_ref_015_w2aab3b7e1457b1b6b1ab2b1c15Aa","doi-asserted-by":"crossref","unstructured":"Arjen K. Lenstra, Hendrik W. Lenstra and L\u00e1szl\u00f3 Lov\u00e1sz, Factoring polynomials with rational coefficients, Mathematische Annalen261 (1982), 515\u2013534 (English).","DOI":"10.1007\/BF01457454"},{"key":"2025120600311350132_j_jmc-2015-0057_ref_016_w2aab3b7e1457b1b6b1ab2b1c16Aa","unstructured":"Oded Regev, A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space, eprint arXiv:quant-ph\/0406151 (2004)."},{"key":"2025120600311350132_j_jmc-2015-0057_ref_017_w2aab3b7e1457b1b6b1ab2b1c17Aa","unstructured":"Oded Regev, A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space, 2004."},{"key":"2025120600311350132_j_jmc-2015-0057_ref_018_w2aab3b7e1457b1b6b1ab2b1c18Aa","unstructured":"Alexander Rostovtsev and Anton Stolbunov, Public-Key Cryptosystem Based on Isogenies, IACR Cryptology ePrint Archive2006 (2006), 145."},{"key":"2025120600311350132_j_jmc-2015-0057_ref_019_w2aab3b7e1457b1b6b1ab2b1c19Aa","doi-asserted-by":"crossref","unstructured":"Claus-Peter Schnorr and M. Euchner, Lattice basis reduction: Improved practical algorithms and solving subset sum problems, Mathematical Programming66 (1994), 181\u2013199.","DOI":"10.1007\/BF01581144"},{"key":"2025120600311350132_j_jmc-2015-0057_ref_020_w2aab3b7e1457b1b6b1ab2b1c20Aa","doi-asserted-by":"crossref","unstructured":"Anton Stolbunov, Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves, Adv. Math. Commun. 4 (2010), 215\u2013235.","DOI":"10.3934\/amc.2010.4.215"},{"key":"2025120600311350132_j_jmc-2015-0057_ref_021_w2aab3b7e1457b1b6b1ab2b1c21Aa","unstructured":"Jacques V\u00e9lu, Isog\u00e9nies entre courbes elliptiques, C. R. Acad. Sci. Paris S\u00e9r. A-B273 (1971), 238\u2013241."}],"container-title":["Journal of Mathematical Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyter.com\/view\/journals\/jmc\/14\/1\/article-p129.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2015-0057\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2015-0057\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:32:46Z","timestamp":1764981166000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2015-0057\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,1]]},"references-count":21,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2020,7,3]]},"published-print":{"date-parts":[[2020,7,3]]}},"alternative-id":["10.1515\/jmc-2015-0057"],"URL":"https:\/\/doi.org\/10.1515\/jmc-2015-0057","relation":{},"ISSN":["1862-2984","1862-2976"],"issn-type":[{"type":"electronic","value":"1862-2984"},{"type":"print","value":"1862-2976"}],"subject":[],"published":{"date-parts":[[2020,1,1]]}}}