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

Maria Corte-Real Santos; Craig Costello; Sam Frengley

Paper 2022/1736

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

Maria Corte-Real Santos

, University College London

Craig Costello

, Microsoft Research

Sam Frengley

, University of Cambridge

Abstract

We develop an efficient algorithm to detect whether a superspecial genus 2 Jacobian is optimally $(N, N)$-split for each integer $N \leq 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 $25{\tt x}$; when the underlying prime is 200 bits, the attack is sped up by a factor $42{\tt x}$; and, when the underlying prime is 1000 bits, the attack is sped up by a factor $160{\tt x}$.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: A minor revision of an IACR publication in PKC 2024
DOI: 10.1007/978-3-031-57725-3_6
Keywords: isogenies post-quantum cryptography superspecial abelian surfaces
Contact author(s): maria santos 20 @ ucl ac uk
craigco @ microsoft com
stf32 @ cam ac uk
History: 2024-12-01: last of 4 revisions; 2022-12-17: received; See all versions
Short URL: https://ia.cr/2022/1736
License: CC BY

BibTeX

@misc{cryptoeprint:2022/1736,
      author = {Maria Corte-Real Santos and Craig Costello and Sam Frengley},
      title = {An algorithm for efficient detection of $(N,N)$-splittings and its application to the isogeny problem in dimension 2},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1736},
      year = {2022},
      doi = {10.1007/978-3-031-57725-3_6},
      url = {https://eprint.iacr.org/2022/1736}
}