Paper 2022/234

New algorithms for the Deuring correspondence: SQISign twice as fast

Luca De Feo, 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Isogeny-based cryptographyDeuring correspondence
Contact author(s)
antonin leroux @ polytechnique org
luca @ defeo lu
benjamin wesolowski @ math u-bordeaux fr
History
2022-02-25: received
Short URL
https://ia.cr/2022/234
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/234,
      author = {Luca De Feo and Antonin Leroux and Benjamin Wesolowski},
      title = {New algorithms for the Deuring correspondence: SQISign twice as fast},
      howpublished = {Cryptology ePrint Archive, Paper 2022/234},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/234}},
      url = {https://eprint.iacr.org/2022/234}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.