Introduction
Squirrels is a digital signature scheme submitted to the NIST Call for Additional Post-Quantum Signature Schemes. It is designed by Thomas Espitau, Guilhem Niot, Chao Sun and Mehdi Tibouchi.
A short description of Squirrels for the cognoscenti is that it follows the hash-and-sign paradigm of Gentry, Peikert and Vaikuntanathan (GPV), instantiated over unstructured co-cyclic integer lattices. In that sense, it is close in spirit to schemes like Falcon, but avoids the reliance on lattices with an algebraic structure.
This design choice is generally considered more conservative for long term security, as structured lattices may suffer from specific vulnerabilities. This higher security confidence comes at a cost, since unstructured lattices do not admit the very compact description that structured lattices enjoy: this makes keys larger, and signing somewhat less efficient. Nevertheless, our trapdoor generation algorithm mitigates this drawback, and ensures that we reach a high level of security in moderate lattice dimensions.
Design Highlights
Squirrels offers the following features:
Conservative security assumptions: we rely on unstructured co-cyclic lattices, which are a particularly conservative choice (most lattices are unstructured and co-cyclic, and lattice problems for this class are easily shown to be at least as hard as in any lattice of the same dimension).
Tailored parameter selection: our five parameter sets are selected to precisely match each of the NIST security level (and not undershoot them, as is unfortunately common in constructions based on structured lattices, that have limited freedom in their parameter choices).
Secure, leakage-free signing: our signing algorithm uses lattice Gaussian sampling to prevent statistical leakage from signatures.
Compact signatures: despite the unstructured nature of our scheme, we achieve a signature size that is quite reasonable. It is for example around twice as small as NIST selected signature Dilithium for equal security levels.
Performance
On a single core of a Ryzen Pro 7 5850U-based @ 3GHz based laptop, Squirrels achieves the following performance:
| Parameter set | keygen (s) | sign/s | vrfy/s | pub size | sig size |
|---|---|---|---|---|---|
| Squirrels-I | 34 | 601.6 | 13099 | 666 kB | 1019 B |
| Squirrels-II | 52 | 509.0 | 11872 | 854 kB | 1147 B |
| Squirrels-III | 127 | 266.2 | 6594 | 1591 kB | 1554 B |
| Squirrels-IV | 179 | 208.7 | 5766 | 1844 kB | 1676 B |
| Squirrels-V | 351 | 177.9 | 3937 | 2721 kB | 2025 B |