Paper 2023/508

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

Jesús-Javier Chi-Domínguez, Technology Innovation Institute
Amalia Pizarro-Madariaga, University of Valparaíso
Edgardo Riquelme, University of Bío-Bío
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.