Welcome to the resource topic for 2025/1859
Title:
qt-Pegasis: Simpler and Faster Effective Class Group Actions
Authors: Pierrick Dartois, Jonathan Komada Eriksen, Riccardo Invernizzi, Frederik Vercauteren
Abstract: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\times for the 500-bit parameters and 2.6\times for the 4000-bit parameters.
ePrint: https://eprint.iacr.org/2025/1859
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 .