Algorithms for solving the isogeny problem with oriented elliptic curves

Résumé fourni par la source

We introduce WayFinder, a framework for generalizing the Delfs-Galbraith and SuperSolver algorithms for the supersingular isogeny problem.Our framework extends the search for elliptic curves with an orientation by an order containing Z[ℓ √ -p] to more general orders, and we derive a cost model for such generalisations.Our cost model not only works in a more general context, but also provides more accurate predictions when applied to SuperSolver.We instantiate WayFinder for orders containing Z[ℓ1 √ -ℓ2p] where ℓi are 1 or primes such that the modular curve X0(ℓ2) has genus 0. We then introduce a low-storage algorithm for computing an isogeny between two oriented supersingular elliptic curves, even when the curves are oriented by distinct orders.Together, these provide an algorithm that improves on the state of the art for solving the isogeny problem, and a cost model with potential applications to parameter selection in isogeny-based cryptography.

Ce résumé expose les affirmations des auteurs. BNTIC ne l’interprète pas comme une validation indépendante des résultats.