International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

An algorithm for efficient detection of (N,N)-splittings and its application to the isogeny problem in dimension 2

Authors:
Maria Corte-Real Santos , University College London
Craig Costello , Microsoft Research
Sam Frengley , University of Cambridge
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: PKC 2024
Abstract: We develop an efficient algorithm to detect whether a superspecial genus 2 Jacobian is optimally (N,N)-split for each integer N <=11. Incorporating this algorithm into the best-known attack against the superspecial isogeny problem in dimension 2 gives rise to significant cryptanalytic improvements. Our implementation shows that when the underlying prime p is 100 bits, the attack is sped up by a factor 25x; when the underlying prime is 200 bits, the attack is sped up by a factor 42x; and, when the underlying prime is 1000 bits, the attack is sped up by a factor 160x.
BibTeX
@inproceedings{pkc-2024-33783,
  title={An algorithm for efficient detection of (N,N)-splittings and its application to the isogeny problem in dimension 2},
  publisher={Springer-Verlag},
  author={Maria Corte-Real Santos and Craig Costello and Sam Frengley},
  year=2024
}