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;
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Keywords
- Elliptic CurvesIsogeniesQuotient GroupsStrategiessuperspecial PPAS
- Contact author(s)
-
jesus dominguez @ tii ae
amalia pizarro @ uv cl
edriquelme @ ubiobio cl - History
- 2023-04-17: last of 2 revisions
- 2023-04-08: received
- See all versions
- Short URL
- https://ia.cr/2023/508
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/508, author = {Jesús-Javier Chi-Domínguez and Amalia Pizarro-Madariaga and Edgardo Riquelme}, title = {Computing Quotient Groups of Smooth Order with Applications to Isogenies over Higher-Dimensional Abelian Varieties}, howpublished = {Cryptology ePrint Archive, Paper 2023/508}, year = {2023}, note = {\url{https://eprint.iacr.org/2023/508}}, url = {https://eprint.iacr.org/2023/508} }