In this paper, we revisit the recent \(\textsf{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 \(\textsf{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. We present a new algorithm, \(\textsf{qt}\) - \(\textsf{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 \(\textsf{Qlapoti}\) approach. However, \(\textsf{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 \(\textsf{KLaPoTi}\) . This way, we can reinterpret the output of \(\textsf{Qlapoti}\) as four equivalent quadratic ideals, instead of two equivalent quaternion ideals. We then show how to construct a \(\textsf{Clapoti}\) -like diagram in dimension 2, which embeds the action of the ideal in a 4-dimensional isogeny. We implemented our \(\textsf{qt}\) - \(\textsf{Pegasis}\) algorithm in SageMath for the CSURF group action, and we achieve a speedup over \(\textsf{Pegasis}\) of \(1.8\times \) for the 500-bit parameters and \(2.6\times \) for the 4000-bit parameters.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

\(\textsf{qt}\) - \(\textsf{Pegasis}\) : Simpler and Faster Effective Class Group Actions

  • Pierrick Dartois,
  • Jonathan Komada Eriksen,
  • Riccardo Invernizzi,
  • Frederik Vercauteren

摘要

In this paper, we revisit the recent \(\textsf{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 \(\textsf{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. We present a new algorithm, \(\textsf{qt}\) - \(\textsf{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 \(\textsf{Qlapoti}\) approach. However, \(\textsf{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 \(\textsf{KLaPoTi}\) . This way, we can reinterpret the output of \(\textsf{Qlapoti}\) as four equivalent quadratic ideals, instead of two equivalent quaternion ideals. We then show how to construct a \(\textsf{Clapoti}\) -like diagram in dimension 2, which embeds the action of the ideal in a 4-dimensional isogeny. We implemented our \(\textsf{qt}\) - \(\textsf{Pegasis}\) algorithm in SageMath for the CSURF group action, and we achieve a speedup over \(\textsf{Pegasis}\) of \(1.8\times \) for the 500-bit parameters and \(2.6\times \) for the 4000-bit parameters.