Paper 2025/2075

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, Fuoutsa and Panny at EUROCRYPT'24. In a LIPH instance we are tasked to recover a secret isogeny \(\varphi\) given masked torsion point images \(M\cdot(\varphi(P),\varphi(Q))^\top\) for some \((P,Q)\) of order \(N\) and unknown \(M\in GL_2(N)\). Additionally, we are provided a \emph{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 \emph{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 the 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^{\sqrt{n}})$ with probability of $84\%$ when $50\%$ of the bits of $M$ leak at random.