Paper 2024/1563

Optimized One-Dimensional SQIsign Verification on Intel and Cortex-M4

Marius A. Aardal, Aarhus University
Gora Adj, Technology Innovation Institute
Arwa Alblooshi, Technology Innovation Institute
Diego F. Aranha, Aarhus University
Isaac A. Canales-Martínez, Technology Innovation Institute
Jorge Chavez-Saab, Technology Innovation Institute
Décio Luiz Gazzoni Filho, Universidade Estadual de Campinas, State University of Londrina
Krijn Reijnders, Radboud University Nijmegen
Francisco Rodríguez-Henríquez, Technology Innovation Institute
Abstract

SQIsign is a well-known post-quantum signature scheme due to its small combined signature and public-key size. However, SQIsign suffers from notably long signing times, and verification times are not short either. To improve this, recent research has explored both one-dimensional and two-dimensional variants of SQIsign, each with distinct characteristics. In particular, SQIsign2D's efficient signing and verification times have made it a focal point of recent research. However, the absence of an optimized one-dimensional verification implementation hampers a thorough comparison between these different variants. This work bridges this gap in the literature: we provide a state-of-the-art implementation of one-dimensional SQIsign verification, including novel optimizations. We report a record-breaking one-dimensional SQIsign verification time of 8.55 Mcycles on a Raptor Lake Intel processor, closely matching SQIsign2D on the same processor. For uncompressed signatures, the signature size doubles and we verify in only 5.6 Mcycles. Taking advantage of the inherent parallelism available in isogeny computations, we present 5-core variants that can go as low as 1.3 Mcycles. Furthermore, we present the first implementation that supports both 32-bit and 64-bit processors. It includes optimized assembly code for the Cortex-M4 and has been integrated with the pqm4 project. Our results motivate further research into one-dimensional SQIsign, as it boasts unique features among isogeny-based schemes.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
post-quantum cryptographyisogenySQIsignverificationARM
Contact author(s)
maardal @ cs au dk
gora adj @ tii ae
arwa alblooshi @ tii ae
dfaranha @ cs au dk
isaac canales @ tii ae
jorge saab @ tii ae
decio gazzoni @ ic unicamp br
krijn @ q1q1 nl
francisco rodriguez @ tii ae
History
2024-10-13: revised
2024-10-04: received
See all versions
Short URL
https://ia.cr/2024/1563
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1563,
      author = {Marius A. Aardal and Gora Adj and Arwa Alblooshi and Diego F. Aranha and Isaac A. Canales-Martínez and Jorge Chavez-Saab and Décio Luiz Gazzoni Filho and Krijn Reijnders and Francisco Rodríguez-Henríquez},
      title = {Optimized One-Dimensional {SQIsign} Verification on Intel and Cortex-M4},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1563},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1563}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.