Paper 2023/508 Original: eprint.iacr.org/2023/508 ↗

Computing Isogenies of Power-Smooth Degrees Between PPAVs

Abstract

The wave of attacks by Castryck and Decru (Eurocrypt, 2023), Maino, Martindale, Panny, Pope and Wesolowski (Eurocrypt, 2023) and Robert (Eurocrypt, 2023), highlight the destructive facet of calculating power-smooth degree isogenies between higher-dimensional abelian varieties in isogeny-based cryptography. Despite those recent attacks, there is still interest in using isogenies but for building protocols on top of higher-dimensional abelian varieties. Examples of such protocols are Public-Key Encryption, Key Encapsulation Mechanism, Verifiable Delay Function, Verifiable Random Function, and Digital Signatures. This work abstracts and proposes a generalization of the strategy technique by Jao, De Feo and Plût (Journal of Mathematical Cryptology, 2014) to give an efficient generic algorithm for computing isogenies between higher-dimensional abelian varieties with kernels being maximal isotropic of power-smooth degree. To illustrate the impact of using such strategy technique, we draft our experiments on the computation of isogenies over two-dimensional abelian varieties determined by a maximal isotropic subgroup of torsion with a power of two or three. Our experiments illustrate a speed-up of 1.25x faster than the state-of-the-art (about 20% of savings).