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\operatorname{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.