KLPT²: Algebraic Pathfinding in Dimension Two and Applications
Wouter Castryck, KU Leuven
Thomas Decru, KU Leuven
Péter Kutas, Eötvös Loránd University, University of Birmingham
Abel Laval, Université Libre de Bruxelles
Christophe Petit, Université Libre de Bruxelles, University of Birmingham
Yan Bo Ti, DSO National Laboratories, National University of Singapore
Abstract
Following Ibukiyama, Katsura and Oort, all principally polarized superspecial abelian surfaces over can be represented by a certain type of matrix , having entries in the quaternion algebra . We present a heuristic polynomial-time algorithm which, upon input of two such matrices , finds a "connecting matrix" representing a polarized isogeny of smooth degree between the corresponding surfaces. Our algorithm should be thought of as a two-dimensional analog of the KLPT algorithm from 2014 due to Kohel, Lauter, Petit and Tignol for finding a connecting ideal of smooth norm between two given maximal orders in .
The KLPT algorithm has proven to be a versatile tool in isogeny-based cryptography, and our analog has similar applications; we discuss two of them in detail. First, we show that it yields a polynomial-time solution to a two-dimensional analog of the so-called constructive Deuring correspondence: given a matrix representing a superspecial principally polarized abelian surface, realize the latter as the Jacobian of a genus- curve (or, exceptionally, as the product of two elliptic curves if it concerns a product polarization). Second, we show that, modulo a plausible assumption, Charles-Goren-Lauter style hash functions from superspecial principally polarized abelian surfaces require a trusted set-up. Concretely, if the matrix associated with the starting surface is known then collisions can be produced in polynomial time. We deem it plausible that all currently known methods for generating a starting surface indeed reveal the corresponding matrix. As an auxiliary tool, we present an explicit table for converting -isogenies into the corresponding connecting matrix, a step for which a previous method by Chu required super-polynomial (but sub-exponential) time.
wouter castryck @ esat kuleuven be thomas decru @ esat kuleuven be kuppabt @ inf elte hu abel laval @ ulb be christophe petit @ ulb be yanbo ti @ gmail com
@misc{cryptoeprint:2025/372,
author = {Wouter Castryck and Thomas Decru and Péter Kutas and Abel Laval and Christophe Petit and Yan Bo Ti},
title = {{KLPT²}: Algebraic Pathfinding in Dimension Two and Applications},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/372},
year = {2025},
url = {https://eprint.iacr.org/2025/372}
}
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.