Paper 2026/2172 Original: eprint.iacr.org/2026/2172 ↗

A New Prime-Norm Ideal Sampling for SQIsign

Abstract

SQIsign samples a random ideal of odd prime norm at every key generation and every signature through $\mathbf{PrimeNormIdealInertSampling}$. We revisit this step from a new perspective: the inert ideals of a given norm form a circle modulo the norm, and drawing lines through a fixed point of this circle turns a single random parameter into an ideal, hitting each ideal exactly once. Compared with the reference implementation, the new algorithm requires one modular inversion and a handful of additions and multiplications. It achieves $13.76\times$ speed-up at NIST security level I in SQIsign while producing an uniform output.