Paper 2025/147

Efficient algorithms for the detection of $(N,N)$-splittings and endomorphisms

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 (due to Costello and Smith) 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 of $25$; when the underlying prime is 200 bits, the attack is sped up by a factor of $42$; and, when the underlying prime is 1000 bits, the attack is sped up by a factor of $160$. Furthermore, we describe a more general algorithm to find endomorphisms of superspecial genus 2 Jacobians.

Note: This article is an extended version of the PKC 2024 article "An algorithm for efficient detection of (N,N)-splittings and its application to the isogeny problem in dimension 2" (eprint 2022/1736), in which we additionally present an algorithm to detect superspecial Jacobians that have real multiplication by a maximal order in a real quadratic field using similar techniques.