| Title: |
PEGASIS: Practical Effective Class Group Action using 4-Dimensional Isogenies |
| Authors: |
Dartois, Pierrick; Eriksen, Jonathan Komada; Fouotsa, Tako Boris; Herlédan Le Merdy, Arthur; Invernizzi, Riccardo; Robert, Damien; Rueger, Ryan; Vercauteren, Frederik; Wesolowski, Benjamin |
| Contributors: |
Institut de Mathématiques de Bordeaux (IMB); Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS); Analyse cryptographique et arithmétique (CANARI); Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Centre Inria de l'Université de Bordeaux; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS); Computer Security and Industrial Cryptography KU Leuven (KU-ESAT-COSIC); Department of Electrical Engineering KU Leuven (KU-ESAT); Catholic University of Leuven = Katholieke Universiteit Leuven (KU Leuven)-Catholic University of Leuven = Katholieke Universiteit Leuven (KU Leuven); Unité de Mathématiques Pures et Appliquées (UMPA-ENSL); École normale supérieure de Lyon (ENS de Lyon); Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS); Laboratoire de l'Informatique du Parallélisme (LIP); Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL); Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS); Centre Inria de l'Université de Bordeaux; Institut National de Recherche en Informatique et en Automatique (Inria); IBM Research Zurich; Technische Universität Munchen = Technical University Munich = Université Technique de Munich (TUM); Department of Electrical Engineering Leuven (ESAT); Catholic University of Leuven = Katholieke Universiteit Leuven (KU Leuven); ANR-22-PNCQ-0002,HQI – R&D et Support,Initiative Nationale Hybride HPC Quantique – R&D et Support des communautés(2022); ANR-22-PETQ-0008,PQ-TLS,Post-quantum padlock for web browser(2022); European Project: 101020788,ERC-2020-ADG,ERC-2020-ADG,ISOCRYPT(2022); European Project: 101116169,ERC-2023-STG,ERC-2023-STG,AGATHA CRYPTY(2024) |
| Source: |
Advances in Cryptology – CRYPTO 2025 ; CRYPTO 2025 ; https://hal.science/hal-04987747 ; CRYPTO 2025, Aug 2025, Santa Barbara, United States. pp.67-99, ⟨10.1007/978-3-032-01855-7_3⟩ |
| Publisher Information: |
CCSD; Springer Nature Switzerland |
| Publication Year: |
2025 |
| Collection: |
HAL Lyon 1 (University Claude Bernard Lyon 1) |
| Subject Terms: |
[MATH]Mathematics [math]; [INFO]Computer Science [cs] |
| Subject Geographic: |
Santa Barbara; United States |
| Description: |
International audience ; In this paper, we present the first practical algorithm to compute an effective group action of the class group of any imaginary quadratic order O on a set of supersingular elliptic curves primitively oriented by O. Effective means that we can act with any element of the class group directly, and are not restricted to acting by products of ideals of small norm, as for instance in CSIDH. Such restricted effective group actions often hamper cryptographic constructions, e.g. in signature or MPC protocols. Our algorithm is a refinement of the Clapoti approach by Page and Robert, and uses 4-dimensional isogenies. As such, it runs in polynomial time, does not require the computation of the structure of the class group, nor expensive lattice reductions, and our refinements allows it to be instantiated with the orientation given by the Frobenius endomorphism. This makes the algorithm practical even at security levels as high as CSIDH-4096. Our implementation in SageMath takes 1.5s to compute a group action at the CSIDH-512 security level, 21s at CSIDH-2048 level and around 2 minutes at the CSIDH-4096 level. This marks the first instantiation of an effective cryptographic group action at such high security levels. For comparison, the recent KLaPoTi approach requires around 200s at the CSIDH-512 level in SageMath and 2s in Rust. |
| Document Type: |
conference object |
| Language: |
English |
| Relation: |
info:eu-repo/grantAgreement//101020788/EU/Isogeny-based Toolbox for Post-quantum Cryptography/ISOCRYPT; info:eu-repo/grantAgreement//101116169/EU/Algebraic groups at the heart of post-quantum cryptography/AGATHA CRYPTY |
| DOI: |
10.1007/978-3-032-01855-7_3 |
| Availability: |
https://hal.science/hal-04987747; https://hal.science/hal-04987747v1/document; https://hal.science/hal-04987747v1/file/2025-401.pdf; https://doi.org/10.1007/978-3-032-01855-7_3 |
| Rights: |
https://creativecommons.org/licenses/by-nc/4.0/ ; info:eu-repo/semantics/OpenAccess |
| Accession Number: |
edsbas.278EF1A5 |
| Database: |
BASE |