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 in order to sample uniformly from the group as is done in the CSI-FiSh signature scheme from Beullens, Kleinjung and Vercauteren. The algorithm used to compute the class-group structure for CSI-FiSh has complexity L(1/2) and it is currently infeasible to scale the parameters to security levels much higher than CSIDH-512, an issue that is particularly problematic in light of the ongoing debate regarding the quantum security levels reached by CSIDH. 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. By carefully choosing the conductor, this family of quadratic orders allows us to easily determine, and even exercise significant control on, the class number — in particular supporting highly smooth choices. While the resulting group action still has an asymptotic complexity of L(1/2), these choices (with a careful choice of parameters) lead to a practical speedup in the construction of the lattice of relations, the foremost bottleneck in CSI-FiSh. To illustrate the improvement, we demonstrate that computing the resulting group action for any element of the class group is practically feasible for a security level equivalent to CSIDH-1024, which is currently firmly out of reach using the CSI-FiSh approach. However, our implementation takes 35 seconds resp. 12.5 minutes for a single group-action evaluation at the security level of CSIDH-512 resp. CSIDH-1024, thus showing that while feasible, the SCALLOP group action does not achieve realistically usable performance yet.