Paper 2026/1031

Compact Quaternion Algorithms for SQIsign

Changmin Lee, Korea University

Hyunwoo Yoo, Korea University

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 1832/2754/3613 bits for the NIST-I/III/V security levels, respectively, corresponding to improvements of $73.93\%$, $74.29\%$, and $74.47\%$. We also provide a fixed-precision implementation of SQIsign applying these improved precision budgets and accelerating previous inefficient implementation of fixed-precision integer arithmetic. Compared with the previous fixed-precision implementation, our implementation achieves performance improvements larger than $99\%$ for both key generation and signing procedures at each security level.

@misc{cryptoeprint:2026/1031,
      author = {Won Kim and Changmin Lee and Hyunwoo Yoo},
      title = {Compact Quaternion Algorithms for {SQIsign}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/1031},
      year = {2026},
      url = {https://eprint.iacr.org/2026/1031}
}