Skip to Main content Skip to Navigation
Conference papers

The supersingular isogeny problem in genus 2 and beyond

Craig Costello 1 Benjamin Smith 2
2 GRACE - Geometry, arithmetic, algorithms, codes and encryption
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
Abstract : Let $A/\overline{\mathbb{F}}_p$ and $A'/\overline{\mathbb{F}}_p$ be supersingular principally polarized abelian varieties of dimension $g>1$. For any prime $\ell \ne p$, we give an algorithm that finds a path $\phi \colon A \rightarrow A'$ in the $(\ell, \dots , \ell)$-isogeny graph in $\widetilde{O}(p^{g-1})$ group operations on a classical computer, and $\widetilde{O}(\sqrt{p^{g-1}})$ calls to the Grover oracle on a quantum computer. The idea is to find paths from $A$ and $A'$ to nodes that correspond to products of lower dimensional abelian varieties, and to recurse down in dimension until an elliptic path-finding algorithm (such as Delfs--Galbraith) can be invoked to connect the paths in dimension $g=1$. In the general case where $A$ and $A'$ are any two nodes in the graph, this algorithm presents an asymptotic improvement over all of the algorithms in the current literature. In the special case where $A$ and $A'$ are a known and relatively small number of steps away from each other (as is the case in higher dimensional analogues of SIDH), it gives an asymptotic improvement over the quantum claw finding algorithms and an asymptotic improvement over the classical van Oorschot--Wiener algorithm.
Complete list of metadata

Cited literature [70 references]  Display  Hide  Download

https://hal.inria.fr/hal-02389073
Contributor : Benjamin Smith <>
Submitted on : Monday, January 27, 2020 - 10:29:52 AM
Last modification on : Friday, April 30, 2021 - 9:59:33 AM
Long-term archiving on: : Tuesday, April 28, 2020 - 2:31:40 PM

Files

pq.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02389073, version 2
  • ARXIV : 1912.00701

Citation

Craig Costello, Benjamin Smith. The supersingular isogeny problem in genus 2 and beyond. PQCrypto 2020 - 11th International Conference on Post-Quantum Cryptography, Apr 2020, Paris, France. ⟨hal-02389073v2⟩

Share

Metrics

Record views

158

Files downloads

530