Leveled Isogeny Problems with Hints

Zusammenfassung

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 φ$$\varphi $$ given masked torsion point images M·(φ(P),φ(Q))⊤$$M\cdot (\varphi (P),\varphi (Q))^\top $$ for some (P,Q)$$(P,Q)$$ of order N$$N$$ and unknown M∈GL2(N)$$M\in \textrm{GL}_2(N)$$. Additionally, we are provided a hint on M$$ 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$$ 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É secret key given 50%$$50\%$$ (resp. 86%$$86\%$$) of the most-significant bits of an entry of M$$ M $$, and a FESTA secret key given 67%$$67\%$$ of the most-significant bits of M$$ M $$. In the case of FESTA we also present a tailored combinatorial attack running in subexponential time O(2n)$$O(2^{\sqrt{n}})$$ with a probability of 84%$$84\%$$ when 50%$$50\%$$ of the bits of M$$M$$ leak at random.