Paper 2023/436

SQISignHD: New Dimensions in Cryptography

Pierrick Dartois, Inria Bordeaux - Sud-Ouest Research Centre, Institut de Mathématiques de Bordeaux
Antonin Leroux, Direction Générale de l'Armement
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 SQISignHD, a new post-quantum digital signature scheme inspired by SQISign. SQISignHD exploits the recent algorithmic breakthrough underlying the attack on SIDH, which allows to efficiently represent isogenies of arbitrary degrees as components of a higher dimensional isogeny. SQISignHD overcomes the main drawbacks of SQISign. First, it scales well to high security levels, since the public parameters for SQISignHD are easy to generate: the characteristic of the underlying field needs only be of the form $2^{f}3^{f'}-1$. Second, the signing procedure is simpler and more efficient. Third, the scheme is easier to analyse, allowing for a much more compelling security reduction. Finally, the signature sizes are even more compact than (the already record-breaking) SQISign, with compressed signatures as small as 116 bytes for the post-quantum NIST-1 level of security. These advantages may come at the expense of the verification, which now requires the computation of an isogeny in dimension $4$, a task whose optimised cost is still uncertain, as it has been the focus of very little attention.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Post-quantum cryptographyIsogeniesSQISignSIDHKani's lemma
Contact author(s)
pierrick dartois @ u-bordeaux fr
History
2023-05-26: last of 3 revisions
2023-03-25: received
See all versions
Short URL
https://ia.cr/2023/436
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/436,
      author = {Pierrick Dartois and Antonin Leroux and Damien Robert and Benjamin Wesolowski},
      title = {SQISignHD: New Dimensions in Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2023/436},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/436}},
      url = {https://eprint.iacr.org/2023/436}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.