{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T04:09:04Z","timestamp":1781582944481,"version":"3.54.5"},"reference-count":0,"publisher":"Walter de Gruyter GmbH","issue":"1","license":[{"start":{"date-parts":[[2013,10,23]],"date-time":"2013-10-23T00:00:00Z","timestamp":1382486400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/3.0\/"}],"funder":[{"DOI":"10.13039\/501100004489","name":"MITACS","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004489","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Ontario Ministry of Research and Innovation"},{"name":"QuantumWorks"},{"name":"US ARO\/DTO"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014,2,1]]},"abstract":"<jats:title>Abstract.<\/jats:title>\n                  <jats:p>Given two ordinary elliptic curves over a finite field\nhaving the same cardinality and endomorphism ring, it is known that\nthe curves admit a nonzero isogeny between them, but finding such an\nisogeny is believed to be computationally difficult. The fastest\nknown classical algorithm takes exponential time, and prior to our\nwork no faster quantum algorithm was known. Recently, public-key\ncryptosystems based on the presumed hardness of this problem have\nbeen proposed as candidates for post-quantum cryptography. In this\npaper, we give a new subexponential-time quantum algorithm for\nconstructing nonzero isogenies between two such elliptic curves,\nassuming the Generalized Riemann Hypothesis (but with no other\nassumptions). Our algorithm is based on a reduction to a hidden\nshift problem, and represents the first nontrivial application of\nKuperberg's quantum algorithm for finding hidden shifts. This\nresult suggests that isogeny-based cryptosystems may be\nuncompetitive with more mainstream quantum-resistant cryptosystems\nsuch as lattice-based cryptosystems. As part of this work, we also\npresent the first classical algorithm for evaluating isogenies\nhaving provably subexponential running time in the cardinality\nof the base field under GRH.<\/jats:p>","DOI":"10.1515\/jmc-2012-0016","type":"journal-article","created":{"date-parts":[[2013,10,23]],"date-time":"2013-10-23T18:24:04Z","timestamp":1382552644000},"page":"1-29","source":"Crossref","is-referenced-by-count":189,"title":["Constructing elliptic curve isogenies in quantum subexponential time"],"prefix":"10.1515","volume":"8","author":[{"given":"Andrew","family":"Childs","sequence":"first","affiliation":[{"name":"Department of Combinatorics & Optimization and Institute for Quantum Computing, University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Jao","sequence":"additional","affiliation":[{"name":"Department of Combinatorics & Optimization, University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vladimir","family":"Soukharev","sequence":"additional","affiliation":[{"name":"Department of Combinatorics & Optimization, University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"374","published-online":{"date-parts":[[2013,10,23]]},"container-title":["Journal of Mathematical Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2012-0016\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2012-0016\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:24:36Z","timestamp":1764980676000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2012-0016\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,10,23]]},"references-count":0,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2014,1,16]]},"published-print":{"date-parts":[[2014,2,1]]}},"alternative-id":["10.1515\/jmc-2012-0016"],"URL":"https:\/\/doi.org\/10.1515\/jmc-2012-0016","relation":{},"ISSN":["1862-2984","1862-2976"],"issn-type":[{"value":"1862-2984","type":"electronic"},{"value":"1862-2976","type":"print"}],"subject":[],"published":{"date-parts":[[2013,10,23]]}}}