The Supersingular Isogeny Problem in Genus 2 and Beyond
| Autor: | Craig Costello, Benjamin Smith |
|---|---|
| Přispěvatelé: | Microsoft Research [Redmond], Microsoft Corporation [Redmond, Wash.], Geometry, arithmetic, algorithms, codes and encryption (GRACE), Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), ANR-19-CE48-0008,CIAO,Cryptographie, isogenies et variété abéliennes surpuissantes(2019), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France |
| Rok vydání: | 2020 |
| Předmět: |
FOS: Computer and information sciences
Isogeny Computer Science - Cryptography and Security Mathematics - Number Theory 0102 computer and information sciences 02 engineering and technology 01 natural sciences [MATH.MATH-NT]Mathematics [math]/Number Theory [math.NT] Graph Combinatorics [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR] 010201 computation theory & mathematics FOS: Mathematics 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Number Theory (math.NT) Abelian group Cryptography and Security (cs.CR) Mathematics Quantum computer |
| Zdroj: | Post-Quantum Cryptography ISBN: 9783030442224 PQCrypto PQCrypto 2020-11th International Conference on Post-Quantum Cryptography PQCrypto 2020-11th International Conference on Post-Quantum Cryptography, Apr 2020, Paris, France HAL |
| Popis: | International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|