Welcome to the resource topic for 2023/058
Title:
SCALLOP: scaling the CSI-FiSh
Authors: Luca De Feo, Tako Boris Fouotsa, Péter Kutas, Antonin Leroux, Simon-Philipp Merz, Lorenz Panny, Benjamin Wesolowski
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 seconds (resp. 12.5 minutes) 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.
ePrint: https://eprint.iacr.org/2023/058
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .