SCALLOP-HD: group action from 2-dimensional isogenies

Mingjie Chen; Antonin Leroux; Lorenz Panny

Paper 2023/1488

SCALLOP-HD: group action from 2-dimensional isogenies

Mingjie Chen

, Université Libre de Bruxelles

Antonin Leroux, DGA-MI, Bruz, France, IRMAR, UMR 6625, Université de Rennes

Lorenz Panny, Technical University of Munich

Abstract

We present SCALLOP-HD, a novel group action that builds upon the recent SCALLOP group action introduced by De Feo, Fouotsa, Kutas, Leroux, Merz, Panny and Wesolowski in 2023. While our group action uses the same action of the class group $Cl (O)$ on $O$ -oriented curves where $O = Z [f \sqrt{- 1}]$ for a large prime $f$ and small $d$ as SCALLOP, we introduce a different orientation representation: The new representation embeds an endomorphism generating $O$ in a $2^{e}$ -isogeny between abelian varieties of dimension with Kani's Lemma, and this representation comes with a simple algorithm to compute the class group action. Our new approach considerably simplifies the SCALLOP framework, potentially surpassing it in efficiency — a claim supported by preliminary implementation results in SageMath. Additionally, our approach streamlines parameter selection. The new representation allows us to select efficiently a class group of smooth order, enabling polynomial-time generation of the lattice of relation, hence enhancing scalability in contrast to SCALLOP. To instantiate our SCALLOP-HD group action, we introduce a new technique to apply Kani's Lemma in dimension 2 with an isogeny diamond obtained from commuting endomorphisms. This method allows one to represent arbitrary endomorphisms with isogenies in dimension 2, and may be of independent interest.

Note: Updated author list and contact information.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A minor revision of an IACR publication in PKC 2024
DOI: 10.1007/978-3-031-57725-3_7
Keywords: isogeny group action post-quantum cryptography Kani's lemma
Contact author(s): mjchennn555 @ gmail com
antonin leroux @ polytechnique org
lorenz @ yx7 cc
History: 2024-04-15: last of 2 revisions; 2023-09-29: received; See all versions
Short URL: https://ia.cr/2023/1488
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1488,
      author = {Mingjie Chen and Antonin Leroux and Lorenz Panny},
      title = {{SCALLOP}-{HD}: group action from 2-dimensional isogenies},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1488},
      year = {2023},
      doi = {10.1007/978-3-031-57725-3_7},
      url = {https://eprint.iacr.org/2023/1488}
}