Welcome to the resource topic for 2023/807
Title:
Towards a constant-time implementation of isogeny-based signature, SQISign
Authors: David Jacquemin, Anisha Mukherjee, Sujoy SINHA ROY, Péter Kutas
Abstract: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.
ePrint: https://eprint.iacr.org/2023/807
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .