Welcome to the resource topic for 2024/778
Title:
Ideal-to-isogeny algorithm using 2-dimensional isogenies and its application to SQIsign
Authors: Hiroshi Onuki, Kohei Nakagawa
Abstract:The Deuring correspondence is a correspondence between supersingular elliptic curves and quaternion orders. Under this correspondence, an isogeny between elliptic curves corresponds to a quaternion ideal. This correspondence plays an important role in isogeny-based cryptography and several algorithms to compute an isogeny corresponding to a quaternion ideal (ideal-to-isogeny algorithms) have been proposed. In particular, SQIsign is a signature scheme based on the Deuring correspondence and uses an ideal-to-isogeny algorithm. In this paper, we propose a novel ideal-to-isogeny algorithm using isogenies of dimension 2. Our algorithm is based on Kani’s reducibility theorem, which gives a connection between isogenies of dimension 1 and 2. By using the characteristic p of the base field of the form 2^fg - 1 for a small odd integer g, our algorithm works by only 2-isogenies and (2, 2)-isogenies in the operations in \mathbb{F}_{p^2}. We apply our algorithm to SQIsign and compare the efficiency of the new algorithm with the existing one. Our analysis shows that the key generation and the signing in our algorithm are at least twice as fast as those in the existing algorithm at the NIST security level 1. This advantage becomes more significant at higher security levels. In addition, our algorithm also improves the efficiency of the verification in SQIsign.
ePrint: https://eprint.iacr.org/2024/778
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 .