International Association
for Cryptologic Research

Isogeny-based cryptographic constructions are well-known in the domain of post-quantum security. One such instance is SQISign, that boasts the most compact key and signature sizes among all post-quantum signature schemes. However, its current implementation is not free from side-channel vulnerabilities. At certain steps within the signing proce- dure, 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’ sub- routine that is based on a non-constant time version of the Euclidean algorithm. We show that if inputs of Cornacchia’s algorithm leaks, then one can retrieve the signing key in polynomial time. We propose two timing attack-resistant versions of Cornacchia’s algorithm. The first ver- sion is based on a lattice reduction algorithm. We show that randomising the starting basis with a unimodular matrix would make the execution time independent of the input. The second version uses a constant-time ‘half-GCD’ algorithm that runs a fixed number of times for a given upper bound on the size of inputs.