(KLPT)^2: Algebraic Pathfinding in Dimension Two and Applications
  • Metaadatok
Tartalom: https://real.mtak.hu/224642/
Archívum: REAL
Gyűjtemény: Status = Published
Subject = Q Science / természettudomány: QA Mathematics / matematika
Type = Article
Cím:
(KLPT)^2: Algebraic Pathfinding in Dimension Two and Applications
Létrehozó:
Castryck, Wouter
Decru, Thomas
Kutas, Péter
Laval, Abel
Petit, Christophe
Ti, Yan Bo
Dátum:
2025
Téma:
QA Mathematics / matematika
Tartalmi leírás:
Following Ibukiyama, Katsura and Oort, all principally polarized superspecial abelian surfaces over Fp can be represented by a certain type of 2 × 2 matrix g, having entries in the quaternion algebra Bp,∞. We present a heuristic polynomial-time algorithm which, upon input of two such matrices g1, g2, 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 Bp,∞. 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 g representing a superspecial principally polarized abelian surface, realize the latter as the Jacobian of a genus-2 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 g 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 efficient method for converting polarized isogenies of powersmooth degree into the corresponding connecting matrix, a step for which a previous approach by Chu required super-polynomial (but sub-exponential) time.
Nyelv:
angol
Típus:
Article
PeerReviewed
info:eu-repo/semantics/article
Formátum:
text
Azonosító:
Castryck, Wouter and Decru, Thomas and Kutas, Péter and Laval, Abel and Petit, Christophe and Ti, Yan Bo (2025) (KLPT)^2: Algebraic Pathfinding in Dimension Two and Applications. LECTURE NOTES IN COMPUTER SCIENCE, 16000. pp. 167-200. ISSN 0302-9743
Kapcsolat:
MTMT:36316472 10.1007/978-3-032-01855-7_6