Paper 2022/234
New algorithms for the Deuring correspondence: Towards practical and secure SQISign signatures
Abstract
The Deuring correspondence defines a bijection between isogenies of supersingular elliptic curves and ideals of maximal orders in a quaternion algebra.
We present a new algorithm to translate ideals of prime-power norm to their corresponding isogenies ---
a central task of the effective Deuring correspondence.
The new method improves upon the algorithm introduced in 2021 by De Feo, Kohel, Leroux, Petit and Wesolowski as a building-block of the SQISign signature scheme. SQISign is the most compact post-quantum signature scheme currently known, but is several orders of magnitude slower than competitors, the main bottleneck of the computation being the ideal-to-isogeny translation. We implement the new algorithm and apply it to SQISign, achieving a more than two-fold speedup in key generation and signing with a new choice of parameter.
Moreover, after adapting the state-of-the-art
Note: Fixed metadata
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published by the IACR in EUROCRYPT 2023
- Keywords
- Post-quantum cryptographyIsogeniesGroup actions.
- Contact author(s)
-
eurocrypt23 @ defeo lu
antonin leroux @ polytechnique org
plonga @ microsoft com
benjamin wesolowski @ math u-bordeaux fr - History
- 2023-04-06: last of 3 revisions
- 2022-02-25: received
- See all versions
- Short URL
- https://ia.cr/2022/234
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/234, author = {Luca De Feo and Antonin Leroux and Patrick Longa and Benjamin Wesolowski}, title = {New algorithms for the Deuring correspondence: Towards practical and secure {SQISign} signatures}, howpublished = {Cryptology {ePrint} Archive, Paper 2022/234}, year = {2022}, url = {https://eprint.iacr.org/2022/234} }