CM action / Quantum · cyclic class group · polynomial qubits

A subexponential-time, polynomial quantum space algorithm for inverting the CM group action

David Jao · Jason LeGrow · Christopher Leonardi · Luis Ruiz-Lopez

Journal of Mathematical Cryptology 2020

PublishedSource checked

Time bound: Subexponential time in log N, with N=|Cl(O)|
Space bound: Polynomial quantum space; subexponential classical precomputation/storage

Source / version date: 14 Jun 2020
Comparison variant: Quantum · cyclic class group · polynomial qubits
Cost scale: Parameter-dependent
restriction: Cyclic class group
application: CRS and CSIDH CM group-action inversion
method: BKW-like classical precomputation

Assumptions and source notes

The checked analysis assumes the class group is cyclic. It uses classical subexponential precomputation and storage, but polynomial quantum space for the online action-inversion computation. Extension to non-cyclic groups is conjectured in Section 3.1.

Source location

Abstract; Sections 3.1 and 4.4
Version: Checked 2026-11-08; see linked source version/date

Primary source ↗

BibTeXDownload .bib

@misc{jllr20,
  author = {David Jao and Jason LeGrow and Christopher Leonardi and Luis Ruiz-Lopez},
  title = {{A subexponential-time, polynomial quantum space algorithm for inverting the CM group action}},
  year = {2020},
  doi = {10.1515/jmc-2015-0057},
  url = {https://www.degruyterbrill.com/document/doi/10.1515/jmc-2015-0057/html},
  keywords = {CSIDH, CM group action, polynomial quantum space, BKW},
  cr_date = {2020-06-14},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {Journal of Mathematical Cryptology 14(1):129–138},
  cr_author_ids = {david-jao; jason-legrow; christopher-leonardi; luis-ruiz-lopez}
}