It’s a Lattice Bake-off and is there a Show-stopper?

As you should already know, our existing public key methods, such as RSA and ECC, are on the way out. Peter Shor showed that quantum…

Photo by Dan-Cristian Pădureț on Unsplash

It’s a Lattice Bake-off and is there a Show-stopper?

As you should already know, our existing public key methods, such as RSA and ECC, are on the way out. Peter Shor showed that quantum computers will make sure they are not based on a hard problem anymore. We may be looking at five to 10 years before the computers will be built at scale, so NIST has been looking to standardize on a digital signature method and also a key exchange mechanism (KEM)/public key method. Whichever method wins these will be integrated into the core security of our digital work, as the concept of having a public key and an associated private key is fundamental in identifying identities and in protecting our secrets.

The contenders

One of the most respected companies around cryptography is Cloudfare, and who have generally invested in pushing forward good practice in the area. Overall they have been evaluating the three short-list contenders for PQC (Post Quantum Cryptography) and have found [here]:

We see that there are three finalists: Dilithium, Falcon and Rainbow, and three alternatives: SPHINCS, Picnic and GeMMS. If you are interested, I have implemented these in C code here:

CRYSTALS-Dilithium (Lattice) — Digital Signature. CRYSTALS Dilithium. Implementation of CRYSTALS Dilithium in C, and which uses Lattice defined as a method where Alice can sign a message.
CRYSTALS-Dilithium (Lattice) — Digital Signature — speed test. CRYSTALS Dilithium. Implementation of CRYSTALS Dilithium in C, and which uses Lattice and defined as a method where Alice can sign a message. This page proves a benchmark test.
RAINBOW — Digital Signature — speed test. RAINBOW. Implementation of RAINBOW in C, and which uses the Oil-and-Vinegar method and defined as a method where Alice can sign a message.
FALCON — Digital Signature. FALCON. Implementation of FALCON in C, and which uses Lattice and defined as a method where Alice can sign a message.
SPHINCS+ — Digital Signature. SPHINCS+. Implementation of SPHINCS+ in C, and which uses a stateless hash-based signature method and defined as a method where Alice can sign a message.
Picnic — Digital Signature. Picnic. Implementation of Picnic in C, and which uses Zero-knowledge proofs (ZKPs) as a signature method and defined as a method where Alice can sign a message.
GeMSS. GeMSS. Implementation of GeMSS (Great Multivariate Short Signature) and which has short signatures and private keys, but a large public key.

If we refer to Cloudflare’s assessment we see that the lattice methods (Dilithium and FALCON) are generally better than the other method (Rainbow) because they have much smaller public key sizes, although Rainbow has a smaller private key size. When looking at a head-to-head for the lattice methods, there is not much between them with FALCON generally having smaller key and signature sizes, but losing out on the signing performance test. A good deal of the evaluation will possibly boil down to how the metrics stack up and how the scoring will weight these. Just now, it’s difficult to separate the two, but one thing that is likely is that a lattice method will win.

In Cloudflare’s assessment, FALCON looks like a good contender and adds an additional 5KB of space within a handshake operation, whereas Dilithium2 will need 17KB extra. This extra space relates to the overhead of the digital signing processing in the TLS handshake.

Performance assessment of PQC overhead

The one downside that Cloudflare has identified is the FALCON requires constant-time 64-bit floating-point arithmetic, and which is not likely to be supported on more limited performance devices. Without this, the private key could be leaked over time — just by measuring the time it took to perform a digital signature. This — perhaps — is a showstopper, and might hand the win to Dilithium2, as it will be seen as a more general-purpose method.

To investigate this impact on connections, Cloudflare set up tests with dummy certificates that added the additional data. Overall they found that the number of connections dropped increased as the amount of data that was added to the dummy certificates (as shown on the graph on the right-hand side). Cloudflare outline that the bump between 10KB and 30KB added, could identify that some clients dropped the connection as they could not handle the extra data:

In terms of the time taken to perform the handshake, we see that there is generally a considerable slowdown overall with 50KB added almost doubling the connection time:

Conclusions

It looks like a lattice method will win the PCQ digital challenge, but there’s a show-stopper in there. While FALCON512 performs the best overall, it has a security weakness that could leak the private key on limited processing devices — such as those found in IoT. Thus, perhaps it’s Dilithium2 that is heading for a win. For performance, there is a considerable increase in the handshake time for the additional data, but it’s likely the security will trump performance, so my tip for the winner is … Dilithium2.

Here’s the master talking about his theory: