Paper 2022/234

New algorithms for the Deuring correspondence: Towards practical and secure SQISign signatures

Luca De Feo, IBM Research Europe, Zürich, Switzerland
Antonin Leroux, DGA-MI, Bruz , France, IRMAR, Université de Rennes, France, LIX, CNRS, Ecole Polytechnique, Institut Polytechnique de Paris, Inria Saclay - Île-de-France Research Centre
Patrick Longa, Microsoft Research, Redmond, USA
Benjamin Wesolowski, Univ. Bordeaux, CNRS, Bordeaux, France, INRIA, IMB, UMR 5251, F-33400, Talence, France, ENS de Lyon, CNRS, UMPA, UMR 5669, Lyon, France

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 $\mathbb{F}_{p^2}$ multiplication algorithms by Longa to implement SQISign's underlying extension field arithmetic and adding various improvements, we push the total speedups to over three times for signing and four times for verification. 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.

Note: Fixed metadata

Available format(s)
Public-key cryptography
Publication info
Published by the IACR in EUROCRYPT 2023
Post-quantum cryptographyIsogeniesGroup actions.
Contact author(s)
eurocrypt23 @ defeo lu
antonin leroux @ polytechnique org
plonga @ microsoft com
benjamin wesolowski @ math u-bordeaux fr
2023-04-06: last of 3 revisions
2022-02-25: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.