Paper 2026/1031

Compact Quaternion Algorithms for SQIsign

Abstract

SQIsign is an isogeny-based post-quantum signature scheme whose public keys and signatures are remarkably compact. However, since SQIsign relies on arithmetic in quaternion algebras over the field of rational numbers, no fixed-precision integer arithmetic for SQIsign had been established until recently, hindering constant-time implementation and deployment on memory-constrained devices. Recent work by Kim et al. instantiated an SQIsign implementation with fixed-precision integer arithmetic by deriving uniform worst-case bounds for the quaternion algorithms used in key generation and signing. Nevertheless, the resulting precision budget remains large, exceeding 13~times the public key size. Consequently, this forces implementations to reserve wide integer buffers throughout the computation. This increases the memory footprint and reduces the suitability of fixed-precision SQIsign for constrained platforms. In this work, we present compact quaternion algorithms that substantially reduce the fixed-precision memory requirements of SQIsign. First, we modify and analyze quaternion algorithms for SQIsign, in which large intermediate integer values appear. Then, we derive the improved uniform worst-case size bound on integers during the key generation and signing procedures. As a result, we reduce the required precision budgets from 7026/10713/14150 bits to 1774/2696/3555 bits for the NIST-I/III/V security levels, respectively, corresponding to improvements of 74.75%, 74.83%, and 74.88%. We also provide a fixed-precision implementation of SQIsign applying these improved precision budgets. Compared with the previous fixed-precision implementation, our implementation achieves performance improvements of 41.36%/17.49% for key generation and 67.27%/55.26% for signing at the NIST-I/III security levels, respectively.