Paper 2024/760

SQIsign2D-West: The Fast, the Small, and the Safer

Andrea Basso, University of Bristol, IBM Research - Zurich
Luca De Feo, IBM Research - Zurich
Pierrick Dartois, Inria Bordeaux - Sud-Ouest Research Centre, Institut de Mathématiques de Bordeaux
Antonin Leroux, Direction Générale de l'Armement, Université de Rennes
Luciano Maino, University of Bristol
Giacomo Pope, NCC Group, University of Bristol
Damien Robert, Inria Bordeaux - Sud-Ouest Research Centre, Institut de Mathématiques de Bordeaux
Benjamin Wesolowski, École Normale Supérieure de Lyon
Abstract

We introduce SQIsign2D-West, a variant of SQIsign using two-dimensional isogeny representations. SQIsignHD was the first variant of SQIsign to use higher dimensional isogeny representations. Its eight-dimensional variant is geared towards provable security but is deemed unpractical. Its four-dimensional variant is geared towards efficiency and has significantly faster signing times than SQIsign, but slower verification owing to the complexity of the four-dimensional representation. Its authors commented on the apparent difficulty of getting any improvement over SQIsign by using two-dimensional representations. In this work, we introduce new algorithmic tools that make two-dimensional representations a viable alternative. These lead to a signature scheme with sizes comparable to SQIsignHD, slightly slower signing than SQIsignHD but still much faster than SQIsign, and the fastest verification of any known variant of SQIsign. We achieve this without compromising on the security proof: the assumptions behind SQIsign2D-West are similar to those of the eight-dimensional variant of SQIsignHD. Additionally, like SQIsignHD, SQIsign2D-West favourably scales to high levels of security Concretely, for NIST level I we achieve signing times of 80 ms and verifying times of 4.5 ms, using optimised arithmetic based on intrinsics available to the Ice Lake architecture. For NIST level V, we achieve 470 ms for signing and 31 ms for verifying.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
IsogeniesPost-quantumSignatures
Contact author(s)
andrea basso @ ibm com
pierrick dartois @ u-bordeaux fr
antonin leroux @ polytechnique org
luciano maino @ bristol ac uk
giacomo pope @ nccgroup com
damien robert @ inria fr
benjamin wesolowski @ ens-lyon fr
History
2024-05-20: approved
2024-05-17: received
See all versions
Short URL
https://ia.cr/2024/760
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/760,
      author = {Andrea Basso and Luca De Feo and Pierrick Dartois and Antonin Leroux and Luciano Maino and Giacomo Pope and Damien Robert and Benjamin Wesolowski},
      title = {{SQIsign2D}-West: The Fast, the Small, and the Safer},
      howpublished = {Cryptology ePrint Archive, Paper 2024/760},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/760}},
      url = {https://eprint.iacr.org/2024/760}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.