SQIsign with Fixed-Precision Integer Arithmetic
摘要
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.