Leveled Isogeny Problems with Hints

Abstract

We define and analyze the Leveled Isogeny Problem with Hints (LIPH), which is a generalization of the Isogeny Problem with Level Structure first introduced by De Feo, Fouotsa and Panny at EUROCRYPT’24. In a LIPH instance, we are tasked to recover a secret isogeny ϕ given masked torsion point images M ·(ϕ(P ) , ϕ(Q)) for some (P, Q ) of order N and unknown M ∈ GL2(N ). Additionally, we are provided a hint on M , revealing some bits of its entries. Instances of LIPH occur naturally in the case of modern isogeny-based key exchanges that use masked torsion points as part of their public key, when additionally some parts of the masking matrix M are revealed due to, for instance, a side-channel attack.

We provide efficient algorithms that solve various instances of LIPH, leading to efficient partial key recovery attacks in practice. More specifically, we present Coppersmith-type attacks that are able to recover an M-SIDH/POK´E secret key given 50% (resp. 86%) of the most-significant bits of an entry of M , and a FESTA secret key given 67% of the most- significant bits of M . In the case of FESTA we also present a tailored combinatorial attack running in subexponential time O(2√n) with a probability of 84% when 50% of the bits of M leak at random.