×

A subexponential-time, polynomial quantum space algorithm for inverting the CM group action. (English) Zbl 1452.81087

Summary: 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 A. Childs et al. [J. Math. Cryptol. 8, No. 1, 1–29 (2014; Zbl 1283.81046)] of such a polynomial quantum space algorithm for this problem are false; our algorithm (along with contemporaneous, independent work by J.-F. Biasse et al. [Lect. Notes Comput. Sci. 11356, 153–168 (2018; Zbl 1407.81083)]) is the first such result.

MSC:

81P94 Quantum cryptography (quantum-theoretic aspects)
68Q12 Quantum algorithms and complexity in the theory of computing
94A60 Cryptography
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Jean-François Biasse, Annamaria Iezzi and Michael J. Jacobson Jr., A note on the security of CSIDH, 2018. · Zbl 1407.81083
[2] Avrim Blum, Adam Kalai and Hal Wasserman, Noise-tolerant Learning, the Parity Problem, and the Statistical Query Model, J. ACM50 (2003), 506-519. · Zbl 1325.68114
[3] Xavier Bonnetain and André Schrottenloher, Quantum Security Analysis of CSIDH and Ordinary Isogeny-based Schemes, Cryptology ePrint Archive, Report 2018/537, 2018, https://eprint.iacr.org/2018/537.
[4] 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. · Zbl 1407.81084
[5] Denis X. Charles, Kristin E. Lauter and Eyal Z. Goren, Cryptographic Hash Functions from Expander Graphs, Journal of Cryptology22 (2009), 93-113. · Zbl 1166.94006
[6] 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. · Zbl 1283.81046
[7] Andrew Childs, David Jao and Vladimir Soukharev, Constructing elliptic curve isogenies in quantum subexponential time, J. Math. Cryptol8 (2014), 1-29. · Zbl 1283.81046
[8] 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-62. · Zbl 0558.12002
[9] Jean-Marc Couveignes, Hard Homogeneous Spaces, Cryptology ePrint Archive, Report 2006/291, 2006, https://eprint.iacr.org/2006/291.
[10] 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. · Zbl 1447.94029
[11] 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. · Zbl 1400.81083
[12] 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-1504. · Zbl 1228.05167
[13] Greg Kuperberg, A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem, SIAM Journal on Computing35 (2005), 170-188. · Zbl 1084.81019
[14] 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-34, Schloss Dagstuhl, Dagstuhl, Germany, 2013. · Zbl 1356.68076
[15] Arjen K. Lenstra, Hendrik W. Lenstra and László Lovász, Factoring polynomials with rational coefficients, Mathematische Annalen261 (1982), 515-534 (English). · Zbl 0488.12001
[16] Oded Regev, A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space, eprint arXiv:quant-ph/0406151 (2004).
[17] Oded Regev, A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space, 2004.
[18] Alexander Rostovtsev and Anton Stolbunov, Public-Key Cryptosystem Based on Isogenies, IACR Cryptology ePrint Archive2006 (2006), 145.
[19] Claus-Peter Schnorr and M. Euchner, Lattice basis reduction: Improved practical algorithms and solving subset sum problems, Mathematical Programming66 (1994), 181-199. · Zbl 0829.90099
[20] 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-235. · Zbl 1213.94136
[21] Jacques Vélu, Isogénies entre courbes elliptiques, C. R. Acad. Sci. Paris Sér. A-B273 (1971), 238-241. · Zbl 0225.14014
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.