### Parallel Isogeny Path Finding with Limited Memory

##### Abstract

The security guarantees of most isogeny-based protocols rely on the computational hardness of finding an isogeny between two supersingular isogenous curves defined over a prime field $\mathbb{F}_q$ with $q$ a power of a large prime $p$. In most scenarios, the isogeny is known to be of degree $\ell^e$ for some small prime $\ell$. We call this problem the Supersingular Fixed-Degree Isogeny Path (SIPFD) problem. It is believed that the most general version of SIPFD is not solvable faster than in exponential time by classical as well as quantum attackers. In a classical setting, a meet-in-the-middle algorithm is the fastest known strategy for solving the SIPFD. However, due to its stringent memory requirements, it quickly becomes infeasible for moderately large SIPFD instances. In a practical setting, one has therefore to resort to time-memory trade-offs to instantiate attacks on the SIPFD. This is particularly true for GPU platforms, which are inherently more memory-constrained than CPU architectures. In such a setting, a van Oorschot-Wiener-based collision finding algorithm offers a better asymptotic scaling. Finding the best algorithmic choice for solving instances under a fixed prime size, memory budget and computational platform remains so far an open problem. To answer this question, we present a precise estimation of the costs of both strategies considering most recent algorithmic improvements. As a second main contribution, we substantiate our estimations via optimized software implementations of both algorithms. In this context, we provide the first optimized GPU implementation of the van Oorschot-Wiener approach for solving the SIPFD. Based on practical measurements we extrapolate the running times for solving different-sized instances. Finally, we give estimates of the costs of computing a degree-$2^{88}$ isogeny using our CUDA software library running on an NVIDIA A100 GPU server.

Available format(s)
Category
Attacks and cryptanalysis
Publication info
Published elsewhere. INDOCRYPT 2022
Keywords
isogenies cryptanalysis GPU golden collision search meet-in-the-middle time-memory trade-offs implementation
Contact author(s)
emanuele bellini @ tii ae
jorge saab @ tii ae
jesus dominguez @ tii ae
andre esser @ tii ae
sorina ionica @ u-picardie fr
luis zamarripa @ tii ae
francisco rodriguez @ tii ae
monika trimoska @ ru nl
floyd zweydinger @ rub de
History
2022-10-26: approved
See all versions
Short URL
https://ia.cr/2022/1464

CC BY

BibTeX

@misc{cryptoeprint:2022/1464,
author = {Emanuele Bellini and Jorge Chavez-Saab and Jesús-Javier Chi-Domínguez and Andre Esser and Sorina Ionica and Luis Rivera-Zamarripa and Francisco Rodríguez-Henríquez and Monika Trimoska and Floyd Zweydinger},
title = {Parallel Isogeny Path Finding with Limited Memory},
howpublished = {Cryptology ePrint Archive, Paper 2022/1464},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/1464}},
url = {https://eprint.iacr.org/2022/1464}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.