Paper 2025/1649

SQIsign with Fixed-Precision Integer Arithmetic

Abstract

SQIsign is an isogeny‑based post‑quantum signature scheme over supersingular elliptic curves that represents isogenies as elements of a quaternion algebra, enabling highly compact signatures and efficient computation. However, because SQIsign performs quaternion arithmetic over $\mathbb{Q}$, no explicit, uniform worst‑case bound is available for the integer coefficients used to represent quaternion algebra elements. Hence, existing implementations require multi-precision integer arithmetic which hinders portability and complicates memory management, disabling constant-time and embedded-friendly implementations. In this work, we perform a complete analysis of all routines in the Round-2 SQIsign specification that manipulate quaternion elements and establish an explicit uniform worst‑case size bound, with a hypothesis to make all intermediate quaternion computations provably bounded. This proof removes the need for multi-precision arithmetic, enabling the first implementation of SQIsign with fixed-precision integer arithmetic, further presenting possibility of constant-time and memory-friendly implementation. We further tighten this bound by introducing a modified ideal multiplication algorithm, which is a subroutine of SQisign. By modifying the ideal multiplication, we derived the improvement of the size of uniform bound compared with the experimental maximum bit of original Round-$2$ SQIsign, as $45\%/44\%/44.5\%$, for NIST-I/III/V security levels, respectively. Relying on the reduced uniform bound, we build a fixed-precision C implementation of SQIsign.