Welcome to the resource topic for 2025/2075
Title:
Leveled Isogeny Problems with Hints
Authors: Subham Das, Riccardo Invernizzi, Péter Kutas, Jonas Meers
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 (\Gamma\cdot(\varphi(P),\varphi(Q))^\top) for some ((P,Q)) of order (N) and unknown (\Gamma\in GL_2(N)). Additionally, we are provided a \emph{hint} on (\Gamma), 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 (\Gamma) 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É secret key given (50%) (resp. (86%)) of the most-significant bits of an entry of (\Gamma), and a FESTA secret key given the 67% of the most-significant bits of (\Gamma).
In the case of FESTA we also present a tailored combinatorial attack running in subexponential time O(2^{\sqrt{n}}) when 50\% of the bits of \Gamma leak at random.
ePrint: https://eprint.iacr.org/2025/2075
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .