The United States Institute for Standards and Technology (NIST) announced earlier this week the full list of algorithms that have been submitted to the first round of the additional NIST call for post-quantum signature schemes.
Prior to this new round of post-quantum signatures, there was a first call for proposed standards for post-quantum signature schemes (and algorithms for key exchange), which started in 2016. The first results from that standardization process are Dilithium, Falcon, and SPHINCS+: the draft versions of the final standards are expected to appear soon. Dilithium and Falcon are based on structured lattices, while SPHINCS+ is based on cryptographic hash functions.
To diversify the portfolio, NIST announced an “on-ramp” for new signature submissions. 40 schemes have been admitted in total, spread over 7 categories: Code-based (5 schemes), Isogenies (1 scheme), Lattices (7 schemes), MPC-in-the-Head (7 schemes), Multivariate (11 schemes), symmetric (4 schemes), and other (5 schemes). PQShield Research team members are participating in 4 submissions: HAWK, LESS, Squirrels, and Raccoon.
All together, these schemes have 297 distinct parameter sets across 5 NIST security levels. Public key sizes range from 32 bytes to 13.5 MB, while signature sizes range between 21 bytes and 5 MB. Many schemes make severe trade-offs and have either very small public keys and very large signatures (MQOM, MIRA, CROSS), or vice versa (UOV). Performance of the schemes also has a large variance: based on the metrics reported by the submission teams, cycle counts for signature generation range from 50,000 cycles (DME-Sign) to over 1 trillion cycles (PREON). Assuming a 2.5 GHz desktop CPU, this translates to an estimated range from 17 microseconds to 7 minutes. Sometimes, this also illustrates a tradeoff between size and computation time: for example, isogeny-based scheme SQIsign has the smallest sums of public keys and signatures, but signing requires 5.5 billion cycles, or around 2.25 seconds (assuming the same CPU).
To help make sense of the wide variety of signature schemes and their parameter sets, and to help investigate their applicability to use cases, we have created an open-source comparison tool. This tool, which helps explore the post-quantum signatures “zoo” is available at https://pqshield.github.io/nist-sigs-zoo/.
We show the categories for all submissions to NIST’s call for additional signature schemes, as well as the public key sizes, signature sizes, and performance characteristics. Our tool allows you to select those schemes and security levels that you are interested in, as well as restrict the list of algorithms based on minimum and maximum key sizes, signature sizes, and signing or verification performance. Pro-tip: the public key vs. signature size scatter plot, which is a useful tool to gain an overview of the schemes, will update based on the selected algorithms.
Follow PQShield on GitHub via https://github.com/PQShield/. For further guidance on how to prepare your existing systems for the transition to post-quantum cryptography, please refer to our white papers, such as Cryptography Modernization Part 1: Where is your Cryptography?
Link to Press Release