Paper 2023/807

Ready to SQI? Safety First! Towards a constant-time implementation of isogeny-based signature, SQIsign

Abstract

NIST has already published the first round of submissions for additional post-quantum signature schemes and the only isogeny-based candidate is SQIsign. It boasts the most compact key and signature sizes among all post-quantum signature schemes. However, its current implementation does not address side-channel resistance. This work is the first to identify a potential side-channel vulnerability in SQIsign. At certain steps within the signing procedure, it relies on Cornacchia’s algorithm to represent an integer as a sum of squares of two integers. This algorithm in turn uses a ‘half-GCD’ (half-greatest common divisor) sub-routine based on Euclid’s division algorithm which has often been exploited for side-channel attacks. We show that if the inputs of Cornacchia’s algorithm leak, then one can retrieve the signing key in polynomial time. Also, since there is no constant-time implementation for SQIsign, we propose two timing attack-resistant versions of Cornacchia’s algorithm. The first version uses a constant-time ‘half-GCD’ algorithm that runs a fixed number of times for a given upper bound based on the bit-size of the inputs. The second version is based on the two-dimensional lattice reduction algorithm. We show that randomizing the starting basis with an unimodular matrix would make the execution time independent of the input.