Paper 2026/2427

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

Abstract

The isogeny graphs of superspecial abelian surfaces with maximal real multiplication were first studied by Charles, Goren, and Lauter in 2009, when they constructed the RM-CGL hash function on these graphs and proved that they are Ramanujan. As a consequence, these graphs enjoy optimal expansion properties, which are either absent or difficult to establish in other higher-dimensional isogeny graphs. In this paper, we take a closer look at these graphs from a cryptographic perspective, and attempt to demonstrate that they are the natural generalization of the supersingular $\ell$-isogeny graph to dimension two. To this end, we tackle two algorithmic problems: We design and implement the RM-KLPT algorithm to solve the algebraic pathfinding problem in these isogeny graphs by solving a norm equation in ideals of a quaternion algebra over a real quadratic field. Further, we revisit the RM-CGL hash function, provide a proof-of-concept implementation, and showcase that knowledge of the initial surface's algebraic description leads to a second-preimage attack on the hash function through our RM-KLPT algorithm. RM-KLPT resembles the one-dimensional KLPT algorithm much more closely than KLPT$^2$ does. This is due to the existence of a higher-dimensional analogue of the Deuring correspondence in the RM setting, which yields significantly shorter paths ($\sim p^{3}$) compared to KLPT$^2$. Finally, we conclude by discussing potential cryptographic constructions that may be built from RM-KLPT.

Note: Comments welcome.