A subexponential-time, polynomial quantum space algorithm for inverting the CM group action
| Autor: | Jao David, LeGrow Jason, Leonardi Christopher, Ruiz-Lopez Luis |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: | |
| Zdroj: | Journal of Mathematical Cryptology, Vol 14, Iss 1, Pp 129-138 (2020) |
| Druh dokumentu: | article |
| ISSN: | 1862-2976 1862-2984 |
| DOI: | 10.1515/jmc-2015-0057 |
| Popis: | 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. |
| Databáze: | Directory of Open Access Journals |
| Externí odkaz: |
|