Cryptology ePrint Archive: Report 2022/234
New algorithms for the Deuring correspondence: SQISign twice as fast
Luca De Feo and Antonin Leroux and Benjamin Wesolowski
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 twofold speed-up in key generation and signing. Verification time is not directly impacted by the change, however we also achieve a twofold speed-up through various other improvements.
In a second part of the article, we advance cryptanalysis by showing a very simple distinguisher against one of the assumptions used in SQISign. We present a way to impede the distinguisher through a few changes to the generic KLPT algorithm. We formulate a new assumption capturing these changes, and provide an analysis together with experimental evidence for its validity.
Category / Keywords: public-key cryptography / Isogeny-based cryptography, Deuring correspondence
Date: received 23 Feb 2022
Contact author: antonin leroux at polytechnique org, luca at defeo lu, benjamin wesolowski at math u-bordeaux fr
Available format(s): PDF | BibTeX Citation
Version: 20220225:080834 (All versions of this report)
Short URL: ia.cr/2022/234
[ Cryptology ePrint archive ]