A subexponential-time, polynomial quantum space algorithm for inverting the CM group action
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 th...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
De Gruyter
2020-06-01
|
| Series: | Journal of Mathematical Cryptology |
| Subjects: | |
| Online Access: | https://doi.org/10.1515/jmc-2015-0057 |
| _version_ | 1798039974540476416 |
|---|---|
| author | Jao David LeGrow Jason Leonardi Christopher Ruiz-Lopez Luis |
| author_facet | Jao David LeGrow Jason Leonardi Christopher Ruiz-Lopez Luis |
| author_sort | Jao David |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-11T22:02:00Z |
| format | Article |
| id | doaj.art-2d897826772d441e8227b65078b2a646 |
| institution | Directory Open Access Journal |
| issn | 1862-2976 1862-2984 |
| language | English |
| last_indexed | 2024-04-11T22:02:00Z |
| publishDate | 2020-06-01 |
| publisher | De Gruyter |
| record_format | Article |
| series | Journal of Mathematical Cryptology |
| spelling | doaj.art-2d897826772d441e8227b65078b2a6462022-12-22T04:00:54ZengDe GruyterJournal of Mathematical Cryptology1862-29761862-29842020-06-0114112913810.1515/jmc-2015-0057jmc-2015-0057A subexponential-time, polynomial quantum space algorithm for inverting the CM group actionJao David0LeGrow Jason1Leonardi Christopher2Ruiz-Lopez Luis3Department of Combinatorics and Optimization, University of Waterloo, Waterloo, CanadaDepartment of Combinatorics and Optimization, University of Waterloo, Waterloo, CanadaDepartment of Combinatorics and Optimization, University of Waterloo, Waterloo, CanadaDepartment of Combinatorics and Optimization, University of Waterloo, Waterloo, CanadaWe 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.https://doi.org/10.1515/jmc-2015-0057isogeny-based cryptographyquantum algorithmsquantum cryptanalysis68q1294a6014k02 |
| spellingShingle | Jao David LeGrow Jason Leonardi Christopher Ruiz-Lopez Luis A subexponential-time, polynomial quantum space algorithm for inverting the CM group action Journal of Mathematical Cryptology isogeny-based cryptography quantum algorithms quantum cryptanalysis 68q12 94a60 14k02 |
| title | A subexponential-time, polynomial quantum space algorithm for inverting the CM group action |
| title_full | A subexponential-time, polynomial quantum space algorithm for inverting the CM group action |
| title_fullStr | A subexponential-time, polynomial quantum space algorithm for inverting the CM group action |
| title_full_unstemmed | A subexponential-time, polynomial quantum space algorithm for inverting the CM group action |
| title_short | A subexponential-time, polynomial quantum space algorithm for inverting the CM group action |
| title_sort | subexponential time polynomial quantum space algorithm for inverting the cm group action |
| topic | isogeny-based cryptography quantum algorithms quantum cryptanalysis 68q12 94a60 14k02 |
| url | https://doi.org/10.1515/jmc-2015-0057 |
| work_keys_str_mv | AT jaodavid asubexponentialtimepolynomialquantumspacealgorithmforinvertingthecmgroupaction AT legrowjason asubexponentialtimepolynomialquantumspacealgorithmforinvertingthecmgroupaction AT leonardichristopher asubexponentialtimepolynomialquantumspacealgorithmforinvertingthecmgroupaction AT ruizlopezluis asubexponentialtimepolynomialquantumspacealgorithmforinvertingthecmgroupaction AT jaodavid subexponentialtimepolynomialquantumspacealgorithmforinvertingthecmgroupaction AT legrowjason subexponentialtimepolynomialquantumspacealgorithmforinvertingthecmgroupaction AT leonardichristopher subexponentialtimepolynomialquantumspacealgorithmforinvertingthecmgroupaction AT ruizlopezluis subexponentialtimepolynomialquantumspacealgorithmforinvertingthecmgroupaction |