NIST’s Post-Quantum Signature On-Ramp Process: Round 1 Overview and Insights

We will soon get an update from the National Institute of Standards and Technology (NIST) about its latest efforts to select and standardize quantum-safe signature schemes. While the end of the first round of this process has not yet been announced, NIST has indicated that it will happen sometime after the Fifth NIST PQC Standardization Conference, being held April 10-12, 2024. With this in mind, we wanted to summarize the submitted signature schemes to date and share our opinions on some of the candidates.
 
But first, a little background. In September 2022, shortly after announcing the post-quantum key encapsulation mechanisms (KEMs) and digital signature schemes they selected for standardization, NIST issued a Call for Proposals for additional signature candidates. Three signature schemes had previously been accepted for standardization: CRYSTALS-Dilithium, Falcon, and SPHINCS+. However, both CRYSTALS-Dilithium and Falcon have their security based on the difficulty of solving problems on structured lattices, and SPHINCS+ is only practical for a relatively limited number of applications as compared to the other two signature schemes.
 
When it comes to security, it is important not to put all your eggs into one basket. Hence, the goal of NIST’s signature "on-ramp" process is to find other suitable quantum-safe signature schemes based on different hard mathematical problems than the schemes selected in 2022 (i.e., to diversify the suite of standardized algorithms). In addition, NIST has stated that it is interested in submissions with "short signatures and fast verification."
 
In July 2023, 40 submissions were made available for public scrutiny, having been deemed "complete and proper" by NIST. The cryptographic community has already posted a lot of its thoughts and cryptanalysis, resulting in 13 total breaks already as of this write-up, and many other schemes requiring minor adjustments to avoid insecurity pitfalls.

 

Figure 1: Status of the NIST Signature Submissions

The mathematical family that received the greatest number of submissions are the multivariate-based schemes, receiving 10 submissions in total. These schemes typically prove their knowledge of a secret way to invert a multivariate quadratic function. If the public function is some , then the signature of some message  would be a vector  satisfying . These schemes are known for fast computations and small signatures, but usually fall short of the mark in public key size. However, two submissions, MAYO and SNOVA, have addressed this brilliantly and can boast public keys as small as 1KB for the first level of security. This improvement comes with a computational overhead for SNOVA, but not for MAYO. For these reasons we think MAYO is an early front-runner.
 
Code-based schemes are one of the oldest families of cryptographic schemes. Unfortunately, they can be large and computationally demanding. The four (currently unbroken) code-based submissions have vastly different profiles: CROSS has public keys under 100B, and signatures in the 10KB range, while the Wave submission has public keys over 3MB, and signatures under 1KB. The other two in the family are LESS and MEDS which both fall in between these two extremes.
 
Multi-Party Computation in-the-Head (MPCitH) is a newer paradigm, formed by taking an Identification (ID) scheme (such as a Code- or Multivariate-based scheme) and transforming it into a secure signature scheme. This category had seven submissions, each formed by choosing different underlying ID schemes. All MPCitH schemes have incredibly large public keys, ranging from 47KB to 150KB, and moderately sized signatures, between 5KB and 8KB. The costs of signing and verification can vary between almost two orders of magnitude among these schemes, with RYDE performing the best here. The fact that there are a wide variety of mathematical problems in this family is fascinating, and it is going to be interesting to see what happens. We would be happy to see a majority of these schemes progress to the next round.
 
In its Call for Proposals, NIST said, "NIST is primarily interested in additional general-purpose signature schemes that are not based on structured lattices...NIST is open to receiving additional submissions based on structured lattices, but is intent on diversifying the post-quantum signature standards. As such, any structured lattice-based signature proposal would need to significantly outperform CRYSTALS-Dilithium and Falcon in relevant applications and/or ensure substantial additional security properties to be considered for standardization." That being said, seven lattice-based submissions were accepted into the first round. Currently, there are three unbroken submissions based on structured lattices, and only one based on unstructured lattices. We think the unstructured lattice submission SQUIRRELS might have public keys too large for wide deployment but note that they do satisfy the requirements for short signatures (1KB) and fast verification that NIST is seeking. The structured lattice submissions HAWK and Raccoon do have a lot to offer, with HAWK being similar to Falcon but without the need for floating point arithmetic, and Raccoon being a variant of Dilithium where side-channel protection is much cheaper.
 
Asymmetric cryptography can be achieved using symmetric cryptography, and the submissions in this category are mostly stateless hash-based, similar to SPHINCS+, which is currently being standardized. Other than the impressive submission FAEST, which uses a homomorphic commitment scheme, all (unbroken) submissions in this family are slight variations of SPHINCS+.
 
For schemes based on some other computationally problem, the only one of great interest is SQIsign. SQIsign is an isogeny-based submission, but it is not susceptible to the attack of Castryk and Decru that broke SIKE (the KEM submission to NIST's original PQC standardization process) because it does not need to reveal torsion point information. Most impressively, it is the lone submission with both public keys and signatures smaller than the classically-secure RSA-2048. This comes at a computational cost, with verification taking around a hundred million cycles, and signing over a billion. However, improvements are continually being made on this front.
 
Keep checking back on the blog, as we continue to keep a close eye on the latest developments in PQC standards. Want more insights? Feel free to contact us directly.