{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T17:49:16Z","timestamp":1648662556571},"reference-count":42,"publisher":"Walter de Gruyter GmbH","issue":"1","license":[{"start":{"date-parts":[[2020,6,14]],"date-time":"2020-06-14T00:00:00Z","timestamp":1592092800000},"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":"Abstract<\/jats:title>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-15T17:48:20Z","timestamp":1592243300000},"page":"129-138","source":"Crossref","is-referenced-by-count":2,"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"}]},{"given":"Jason","family":"LeGrow","sequence":"additional","affiliation":[{"name":"Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada"}]},{"given":"Christopher","family":"Leonardi","sequence":"additional","affiliation":[{"name":"Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada"}]},{"given":"Luis","family":"Ruiz-Lopez","sequence":"additional","affiliation":[{"name":"Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada"}]}],"member":"374","reference":[{"key":"ref121","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1137\/S0097539703436345","article-title":"A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem","volume":"35","year":"2005","journal-title":"SIAM Journal on Computing"},{"key":"ref381","article-title":"Public-Key Cryptosystem Based on Isogenies","volume":"2006","year":"2006","journal-title":"IACR Cryptology ePrint Archive"},{"key":"ref351","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1007\/BF01457454","article-title":"Factoring polynomials with rational coefficients","volume":"261","year":"1982","journal-title":"Mathematische Annalen"},{"key":"ref71","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/BFb0099440","article-title":"Heuristics on class groups of number fields","volume":"1068","year":"1984","journal-title":"Number theory, Noordwijkerhout 1983 (Noordwijkerhout, 1983), Lecture Notes in Math."},{"key":"ref301","volume-title":"Towards practical key exchange from ordinary isogeny graphs","year":"2018"},{"key":"ref401","doi-asserted-by":"crossref","first-page":"215","DOI":"10.3934\/amc.2010.4.215","article-title":"Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves","volume":"4","year":"2010","journal-title":"Adv. Math. Commun."},{"key":"ref281","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/BFb0099440","article-title":"Heuristics on class groups of number fields","volume":"1068","year":"1984","journal-title":"Number theory, Noordwijkerhout 1983 (Noordwijkerhout, 1983), Lecture Notes in Math."},{"key":"ref411","first-page":"238","article-title":"Isog\u00e9nies entre courbes elliptiques","volume":"273","year":"1971","journal-title":"C. R. Acad. Sci. Paris S\u00e9r. A-B"},{"key":"ref181","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/BF01581144","article-title":"Lattice basis reduction: Improved practical algorithms and solving subset sum problems","volume":"66","year":"1994","journal-title":"Mathematical Programming"},{"key":"ref51","volume-title":"Constructing elliptic curve isogenies in quantum subexponential time","year":"2010"},{"key":"ref261","volume-title":"Constructing elliptic curve isogenies in quantum subexponential time","year":"2010"},{"key":"ref361","article-title":"A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space","year":"2004","journal-title":"eprint arXiv:quant-ph\/0406151"},{"key":"ref01","year":"2018","journal-title":"A note on the security of CSIDH"},{"key":"ref61","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1515\/jmc-2012-0016","article-title":"Constructing elliptic curve isogenies in quantum subexponential time","volume":"8","year":"2014","journal-title":"J. Math. Cryptol"},{"key":"ref231","volume-title":"Quantum Security Analysis of CSIDH and Ordinary Isogeny-based Schemes","year":"2018"},{"key":"ref271","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1515\/jmc-2012-0016","article-title":"Constructing elliptic curve isogenies in quantum subexponential time","volume":"8","year":"2014","journal-title":"J. Math. Cryptol"},{"key":"ref151","article-title":"A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space","year":"2004","journal-title":"eprint arXiv:quant-ph\/0406151"},{"key":"ref171","article-title":"Public-Key Cryptosystem Based on Isogenies","volume":"2006","year":"2006","journal-title":"IACR Cryptology ePrint Archive"},{"key":"ref161","year":"2004","journal-title":"A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space"},{"key":"ref41","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1007\/s00145-007-9002-x","article-title":"Cryptographic Hash Functions from Expander Graphs","volume":"22","year":"2009","journal-title":"Journal of Cryptology"},{"key":"ref91","volume-title":"Towards practical key exchange from ordinary isogeny graphs","year":"2018"},{"key":"ref201","first-page":"238","article-title":"Isog\u00e9nies entre courbes elliptiques","volume":"273","year":"1971","journal-title":"C. R. Acad. Sci. Paris S\u00e9r. A-B"},{"key":"ref191","doi-asserted-by":"crossref","first-page":"215","DOI":"10.3934\/amc.2010.4.215","article-title":"Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves","volume":"4","year":"2010","journal-title":"Adv. Math. Commun."},{"key":"ref331","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1137\/S0097539703436345","article-title":"A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem","volume":"35","year":"2005","journal-title":"SIAM Journal on Computing"},{"key":"ref141","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1007\/BF01457454","article-title":"Factoring polynomials with rational coefficients","volume":"261","year":"1982","journal-title":"Mathematische Annalen"},{"key":"ref211","year":"2018","journal-title":"A note on the security of CSIDH"},{"key":"ref311","volume-title":"Computational problems in supersingular elliptic curve isogenies","year":"2017"},{"key":"ref341","first-page":"20","volume-title":"8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)","volume":"22","year":"2013"},{"key":"ref21","volume-title":"Quantum Security Analysis of CSIDH and Ordinary Isogeny-based Schemes","year":"2018"},{"key":"ref111","doi-asserted-by":"crossref","first-page":"1491","DOI":"10.1016\/j.jnt.2008.11.006","article-title":"Expander graphs based on GRH with an application to elliptic curve cryptography","volume":"129","year":"2009","journal-title":"J. Number Theory"},{"key":"ref241","volume-title":"CSIDH: An Efficient Post-Quantum Commutative Group Action","year":"2018"},{"key":"ref391","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/BF01581144","article-title":"Lattice basis reduction: Improved practical algorithms and solving subset sum problems","volume":"66","year":"1994","journal-title":"Mathematical Programming"},{"key":"ref11","doi-asserted-by":"crossref","first-page":"506","DOI":"10.1145\/792538.792543","article-title":"Noise-tolerant Learning, the Parity Problem, and the Statistical Query Model","volume":"50","year":"2003","journal-title":"J. ACM"},{"key":"ref221","doi-asserted-by":"crossref","first-page":"506","DOI":"10.1145\/792538.792543","article-title":"Noise-tolerant Learning, the Parity Problem, and the Statistical Query Model","volume":"50","year":"2003","journal-title":"J. ACM"},{"key":"ref131","first-page":"20","volume-title":"8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)","volume":"22","year":"2013"},{"key":"ref291","volume-title":"Hard Homogeneous Spaces","year":"2006"},{"key":"ref101","volume-title":"Computational problems in supersingular elliptic curve isogenies","year":"2017"},{"key":"ref321","doi-asserted-by":"crossref","first-page":"1491","DOI":"10.1016\/j.jnt.2008.11.006","article-title":"Expander graphs based on GRH with an application to elliptic curve cryptography","volume":"129","year":"2009","journal-title":"J. Number Theory"},{"key":"ref371","year":"2004","journal-title":"A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space"},{"key":"ref31","volume-title":"CSIDH: An Efficient Post-Quantum Commutative Group Action","year":"2018"},{"key":"ref81","volume-title":"Hard Homogeneous Spaces","year":"2006"},{"key":"ref251","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1007\/s00145-007-9002-x","article-title":"Cryptographic Hash Functions from Expander Graphs","volume":"22","year":"2009","journal-title":"Journal of Cryptology"}],"container-title":["Journal of Mathematical Cryptology"],"original-title":[],"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.degruyter.com\/document\/doi\/10.1515\/jmc-2015-0057\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,22]],"date-time":"2021-04-22T01:16:54Z","timestamp":1619054214000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/jmc-2015-0057\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,14]]},"references-count":42,"journal-issue":{"issue":"1"},"URL":"http:\/\/dx.doi.org\/10.1515\/jmc-2015-0057","relation":{},"ISSN":["1862-2984","1862-2976"],"issn-type":[{"value":"1862-2984","type":"electronic"},{"value":"1862-2976","type":"print"}],"subject":["Applied Mathematics","Computational Mathematics","Computer Science Applications"],"published":{"date-parts":[[2020,6,14]]}}}