International Association for Cryptologic Research

International Association
for Cryptologic Research


SQIsignHD: New Dimensions in Cryptography

Pierrick Dartois , INRIA, IMB, UMR 5251, F-33400, Talence, France
Antonin Leroux , DGA-MI, Bruz, France
Damien Robert , INRIA, IMB, UMR 5251, F-33400, Talence, France
Benjamin Wesolowski , ENS de Lyon, CNRS, UMPA, UMR 5669, Lyon, France
Search ePrint
Search Google
Conference: EUROCRYPT 2024
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. Our signing procedure implemented in C runs in 28 ms, which is a significant improvement compared to SQISign. 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 109 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. Our experimental \verb+sagemath+ implementation of the verification runs in 850 ms, indicating the potential cryptographic interest of dimension $4$ isogenies after optimisations and low level implementation.
  title={SQIsignHD: New Dimensions in Cryptography},
  author={Pierrick Dartois and Antonin Leroux and Damien Robert and Benjamin Wesolowski},