COSIC Seminar "Leveled Isogeny Problems with Hints" (Riccardo Invernizzi, COSIC)

COSIC Seminar – Leveled Isogeny Problems with Hints – Riccardo Invernizzi (COSIC) 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 given masked torsion point images M(\phi(P), \phi(Q)) for some (P, Q) of order N and unknown M \in GL_2(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 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.