TY - GEN
T1 - The Supersingular Isogeny Problem in Genus 2 and Beyond
AU - Costello, Craig
AU - Smith, Benjamin
N1 - Publisher Copyright:
© 2020, Springer Nature Switzerland AG.
PY - 2020/1/1
Y1 - 2020/1/1
N2 - Let (Formula Presented) be superspecial principally polarized abelian varieties of dimension (Formula Presented). For any prime (Formula Presented), we give an algorithm that finds a path (Formula Presented) in the (Formula Presented)-isogeny graph in (Formula Presented) group operations on a classical computer, and (Formula Presented) 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.
AB - Let (Formula Presented) be superspecial principally polarized abelian varieties of dimension (Formula Presented). For any prime (Formula Presented), we give an algorithm that finds a path (Formula Presented) in the (Formula Presented)-isogeny graph in (Formula Presented) group operations on a classical computer, and (Formula Presented) 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.
U2 - 10.1007/978-3-030-44223-1_9
DO - 10.1007/978-3-030-44223-1_9
M3 - Conference contribution
AN - SCOPUS:85083984086
SN - 9783030442224
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 151
EP - 168
BT - Post-Quantum Cryptography - 11th International Conference, PQCrypto 2020, Proceedings
A2 - Ding, Jintai
A2 - Tillich, Jean-Pierre
PB - Springer
T2 - 11th International Conference on Post-Quantum Cryptography, PQCrypto 2020
Y2 - 15 April 2020 through 17 April 2020
ER -