eprint.iacr.orgpaper

RM-KLPT: Algebraic Pathfinding for Superspecial Abelian Surfaces with Maximal Real Multiplication

The paper presents RM-KLPT, an algorithm that solves the algebraic pathfinding problem in isogeny graphs of superspecial abelian surfaces with maximal real multiplication. It does this by solving a norm equation in ideals of a quaternion algebra over a real quadratic field. The authors implement it and revisit the RM-CGL hash function of Charles, Goren and Lauter. They show that if the initial surface's algebraic description is known, RM-KLPT gives a second-preimage attack on the hash. Paths are much shorter (~p^3) than with KLPT^2, because a higher-dimensional Deuring correspondence exists in the RM setting. The paper also discusses cryptographic constructions that could be built on RM-KLPT.