Paper 2023/508

Computing Quotient Groups of Smooth Order with Applications to Isogenies over Higher-Dimensional Abelian Varieties

Abstract

There is an increasing interest in efficiently computing isogenies with a kernel of large-smooth size, for instance, as a building block for building secure Proof-of-Knowledge (PoK) with isogenies of degree equals a power of a small prime number. Another example corresponded to the attacks started by Castryck and Decru and followed up by Maino-Martindale and Robert, which require calculating isogenies over superspecial principally polarized abelian surfaces (superspecial PPAS). On the opposite side of cryptanalysis, some of the current state-of-the-art on safe isogeny-based PoK constructions extends to the case of superspecial PPAS, with the property that one could use smaller fields (e.g., 128, 192, and 256 bits). This work presents a general framework that generalizes the situation of computing isogenies of the large-smooth degree to the context of quotient groups. More precisely, we abstract and propose a generalization of the strategy technique by Jao, De Feo, and Plût. Such a framework provides an efficient generic algorithm that easily applies to computing isogenies over superspecial PPAS when given the isogeny kernel. Additionally, our algorithm induces an efficient algorithm to perform the KernelToIsogeny procedure required in SQISignHD. To illustrate the impact of optimal strategies, we draft our experiments on the isogenies over superspecial PPAS required in the Castryck-Decru attack (powers of two and three). Our experiments illustrate a decent speed up of 1.25x faster than the state-of-the-art (about 20% of savings). Our results should be viewed as proof-of-concept implementation and considered for optimized C-language implementations.

Note: Preliminary version; Fix typos in the abstract; Fix a few typos in the body; Extend Acknowledgements;