SCALLOP: Scaling the CSI-FiSh

Luca De Feo, Tako Boris Fouotsa, Péter Kutas, Antonin Leroux, Simon Philipp Merz, Lorenz Panny, Benjamin Wesolowski

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

12 Zitate (Scopus)

Abstract

We present SCALLOP: SCALable isogeny action based on Oriented supersingular curves with Prime conductor, a new group action based on isogenies of supersingular curves. Similarly to CSIDH and OSIDH, we use the group action of an imaginary quadratic order’s class group on the set of oriented supersingular curves. Compared to CSIDH, the main benefit of our construction is that it is easy to compute the class-group structure; this data is required to uniquely represent — and efficiently act by — arbitrary group elements, which is a requirement in, e.g., the CSI-FiSh signature scheme by Beullens, Kleinjung and Vercauteren. The index-calculus algorithm used in CSI-FiSh to compute the class-group structure has complexity L(1/2), ruling out class groups much larger than CSIDH-512, a limitation that is particularly problematic in light of the ongoing debate regarding the quantum security of cryptographic group actions. Hoping to solve this issue, we consider the class group of a quadratic order of large prime conductor inside an imaginary quadratic field of small discriminant. This family of quadratic orders lets us easily determine the size of the class group, and, by carefully choosing the conductor, even exercise significant control on it — in particular supporting highly smooth choices. Although evaluating the resulting group action still has subexponential asymptotic complexity, a careful choice of parameters leads to a practical speedup that we demonstrate in practice for a security level equivalent to CSIDH-1024, a parameter currently firmly out of reach of index-calculus-based methods. However, our implementation takes 35 s (resp. 12.5 min) for a single group-action evaluation at a CSIDH-512-equivalent (resp. CSIDH-1024-equivalent) security level, showing that, while feasible, the SCALLOP group action does not achieve realistically usable performance yet.

OriginalspracheEnglisch
TitelPublic-Key Cryptography – PKC 2023 - 26th IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings
Redakteure/-innenAlexandra Boldyreva, Vladimir Kolesnikov
Herausgeber (Verlag)Springer Science and Business Media Deutschland GmbH
Seiten345-375
Seitenumfang31
ISBN (Print)9783031313677
DOIs
PublikationsstatusVeröffentlicht - 2023
Extern publiziertJa
Veranstaltung26th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2023 - Atlanta, USA/Vereinigte Staaten
Dauer: 7 Mai 202310 Mai 2023

Publikationsreihe

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Band13940 LNCS
ISSN (Print)0302-9743
ISSN (elektronisch)1611-3349

Konferenz

Konferenz26th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2023
Land/GebietUSA/Vereinigte Staaten
OrtAtlanta
Zeitraum7/05/2310/05/23

Fingerprint

Untersuchen Sie die Forschungsthemen von „SCALLOP: Scaling the CSI-FiSh“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren