In posts of September 25 and 28 we described several optimizations to SPHINCS, a signature algorithm that only relies on hash functions’ security, as opposed to RSA or DSA algorithms that rely on arithmetic problems—factoring and discrete logarithm, respectively. This makes a big difference if a scalable quantum computer is ever built: whereas a quantum computer would solve the factoring and discrete logarithm problems efficiently, it would be powerless against hash functions. SPHINCS therefore deserves the qualificative of post-quantum, meaning that it wouldn’t be broken by a quantum computer.
We don’t know when or even whether a scalable quantum computer will be built, so you can see post-quantum crypto as an insurance. And to allow government organization and business to subscribe to this kind of insurance, NIST is organizing a public competition to standardize post-quantum crypto algorithm, the same kind of process that gave us the AES block cipher in 2000 and the SHA-3 hash function in 2012. The deadline for submitting to NIST’s post-quantum project was yesterday, and I’d like to present our submission, Gravity-SPHINCS.
Gravity-SPHINCS is the fruit of Guillaume Endignoux‘s master’s thesis in our research team, supervised by yours truly, between February and July 2017. We called it Gravity because we saw the problem to improve SPHINCS as ambitious as the physics problem of solving quantum gravity. But turned out we did find a couple of improvements, and that’s why we ended up submitting Gravity-SPHINCS to NIST ‘s contest. These improvements are outlined in the aforementioned posts, and aim to simplify the algorithm, reduce the signature and key sizes, and make the signature and verification faster.
Our submission package is available in the repository https://github.com/gravity-postquantum/gravity-sphincs, which includes
- The complete specification of Gravity-SPHINCS
- Open-source implementations (under Apache 2.0 license)
- Debug values and known-answer tests, as required by NIST
- A script to compute the security level given a set of parameters
We’ve proposed three actual instances of Gravity-SPHINCS to NIST, which all offer 128-bit security—both against classical and quantum computers. These are described below in a copy of our documentation:
In terms of performance, Gravity-SPHINCS is not the fastest signature scheme ever, but should be fast enough for most applications. The slowest is key generation, which takes hundreds of thousands of milliseconds, and up to seconds on a typical laptop CPU. Signature takes a couple hundreds of microseconds, while verification takes a few microseconds. Internally, Gravity-SPHINCS consists mostly of AES rounds computation—because of the hash tree computation that use the hash function Haraka, based on AES.
The reference implementation is in C, but we also have a Rust version, coded by Guillaume. Let us know if you find any bug in these!
All submissions to NIST’s contest should be available soon on https://nist.gov/pqcrypto, and I’ll also update the unofficial list on https://post-quantum.ch/.
Kudelski Security Research 