eprint.iacr.org will be offline for approximately an hour
for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between
April 12 and April 14, and some authors have been notified that they need to resubmit their papers.
Paper 2022/1736
An algorithm for efficient detection of $(N,N)$-splittings and its application to the isogeny problem in dimension 2
, University College London, Microsoft Research, University of CambridgeAbstract
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
- Keywords
- isogeniespost-quantum cryptographysuperspecial abelian surfaces
- Contact author(s)
-
maria santos 20 @ ucl ac uk
craigco @ microsoft com
stf32 @ cam ac uk - History
- 2024-02-02: revised
- 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},
note = {\url{https://eprint.iacr.org/2022/1736}},
url = {https://eprint.iacr.org/2022/1736}
}
