sfqt-sfPegasis: Simpler and Faster Effective Class Group Actions

In this paper, we revisit the recent Pegasis algorithm that computes an effective group action of the class group of any imaginary quadratic order R on a set of supersingular elliptic curves primitively oriented by R. Although Pegasis was the first algorithm showing the practicality of computing unrestricted class group actions at higher security levels, it is complicated and prone to failures, which leads to many rerandomizations. In this work, we present a new algorithm, qt-Pegasis, which is much simpler, but at the same time faster and removes the need for rerandomization of the ideal we want to act with, since it never fails. It leverages the main technique of the recent Qlapoti approach. However, Qlapoti solves a norm equation in a quaternion algebra, which corresponds to the full endomorphism ring of a supersingular elliptic curve. We show that the algorithm still applies in the quadratic setting, by embedding the quadratic ideal into a quaternion ideal using a technique similar to the one applied in KLaPoTi. This way, we can reinterpret the output of Qlapoti as four equivalent quadratic ideals, instead of two equivalent quaternion ideals. We then show how to construct a Clapoti-like diagram in dimension 2, which embeds the action of the ideal in a 4-dimensional isogeny. We implemented our qt-Pegasis algorithm in SageMath for the CSURF group action, and we achieve a speedup over Pegasis of 1.8× for the 500-bit parameters and 2.6× for the 4000-bit parameters.