Under Starters Orders: It’s A Three Horse Race — Dilithium, Rainbow and Falcon … But Who Will Win…

Under Starters Orders: It’s A Three Horse Race — Dilithium, Rainbow and Falcon … But Who Will Win The Cyber Stakes?

And so we see the rise of the quantum computer, and where our cybersecurity world will change in a disruptive way. At the core of cybersecurity is trust, and at the core of digital trust is the digital signature. This magical operation proves identity, it protects integrity and it defines (near) certainty. Presently, we are probably just at the start of our journey to make every transaction trustworthy, and so we need to understand how our existing methods can be made secure into the future.

Our existing methods for digital signing include DSA (/RSA), ECDSA and EdDSA. DSA uses RSA, and ECDSA and EdDSA use ECC (Elliptic Curve Cryptography). Within digital certificates, we typically still use RSA to provide a trustworthy digital signature, but in most other applications, such as with embedded device and blockchain, we use ECC methods. But the basic methods of implementing RSA and ECC are not hard problems in a quantum computer era, and so, with quantum computers, every Bitcoin wallet could be revealed, and every digital certificate could be cracked. If this happens, our existing Internet infrastructure will completely crash.

So, if your company uses trusted digital signatures, what’s the migration path? Well, just as with AES and SHA-3, NIST is looking to shorten the field of contenders for a post-quantum method, and, in 2022, will announce the winner. At present, there are only three in the final. Two of these are lattice methods (CRYSTALS-Dilithium and Falcon) and the third uses an oil-and-vinegar approach (RAINBOW).

The main assessments will be around the performance, signature sizes and key sizes. For ECC and RSA we have relatively small public and private keys, and a small signature. For RAINBOW, we see relatively large key sizes, but a relatively small digital signature. On the other hand, the two lattice methods produce relatively small key sizes, but a larger digital signature. Here are the main methods, and I have running code for each:

• 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.
• FALCON — Digital Signature. FALCON. Implementation of FALCON in C, and which uses Lattice and defined as a method where Alice can sign a message.
• 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.

So, let’s race …

We have two stables for our race: the Lattice Stable (establed in 2005 by O.Regev). In STOC, 2005, and the Oil-and-Vinegar Stable (created in 1997 by J.Patarin). For the Lattice Stable we have Dilithium and Falcon, and from the Oil-and-Vinegar Stable we have Rainbow. We will now race them and give them points for each race, and see if we can find the winner. The Lattice Stable is the talk of the town, with a great buzz about it, and so the early betting puts their horses in equal first place:

• Falcon: 6/4 (co-fav).
• Dilithium: 6/4 (co-fav).
• Rainbow: 12/1.

Could we end up with a dead-heat? The Lattice Stable has some great trainers, and they have been around for a while and have trained their horses for the course. For the Oil-and-Vineger Stable, they have an eight year advantage in experience and with a proven track record.

Our first races will look at the key and signature sizes. In terms of the public and private key size, the lattice methods finish the race before Rainbow can even get out of the blocks [here]:

Winner (Key size race): Falcon. It is a close call on the lattice methods, but, in the end, Falcon pushes ahead against Dilithium. Rainbow produces much larger keys. So we will give Falcon 10 points for winning this race, Dilithium gets 6 points, and Rainbow just one point.

For the signature size, the contenders are all in a good place, but it is Rainbow in 1st place, followed by Falcon and Dilithium.

Winner (Signature size race): Rainbow. In this the Oil-and-Vinegar always knew they would win, and so Rainbow gets 10 points, Falcon gets 6 points and Dilithium gets 4 points.

And so, after two races, Falcon leads with 16 points, and Dilithium and Rainbow in equal second place with 10 points. It’s still a close race, but Falcon has shown good attributes for key sizes and signatures in the PQC race.

But now things will get more challenging, and we’ll measure them in their actual performance:

Winner (Key generation race): Dilithium. For the first time, Dilithium pushes through with a win in the key generation race, and much faster than its lattice stablemate (Falcon). So, Dilithium gets 10 points, Rainbow gets 3 points and Falcon gets 1 points. A really poor showing by Falcon this time out.

Winner (Signing race): Dilithium. It’s Dilithium again, but Falcon gets nearer, and Rainbow ends up in last place. So, Dilithium gets 10 points, Falcon gets 3 points and Rainbow gets 1 point. A really poor showing by Falcon and Rainbow this time out.

Winner (Signing race): Falcon. And just when things were looking difficult for Falcon, it comes through in the verification race and proves to be much faster than Dilithium. Rainbow is way behind. So, Falcon gets 10 points, Dilithium gets 3 points and Rainbow gets 1 point.

So up to now, we have:

1st: Falcon: 40 points.
2nd: Dilithium: 33 points
3rd: Rainbow: 16 points

Up to now, it is a two-horse race, with the Lattice stable winning big time over the Oil-and-Vinegar stable. Let’s now go to the memory stakes.

It’s a poor showing by Dilithium here, and the other two are just much more efficient in their memory.

Winner (Key generation memory race): Falcon. In this race, it was a two-horse race, with Dilithium struggling to keep up with the others. So, Falcon gets 10 points, Rainbow gets 6 points and Dilithium gets 2 points.

1st: Falcon: 50 points.
2nd: Dilithium: 35 points.
3rd: Rainbow: 22 points.

Winner (Sign and verify memory race): Falcon. The same as the last race, Falcon well in front, and followed by Rainbow, but Dilithum way behind. So, Falcon gets 10 points, Rainbow gets 6 points and Dilithium gets 2 points.

1st: Falcon: 60 points.
2nd: Dilithium: 37 points.
3rd: Rainbow: 28 points.

And now for the final race — the code size stakes. After our initial set of races, Falcon looks unbeatable overall, so it would have to fall at this fence to be beaten overall. For this, we first measure the memory footprint for the code:

Winner (Sign and verify memory race): Dilithium. And, finally, Dilithium recovers in this race and wins by a long way. It’s Falcon in second place, a long way back, and Rainbow in third. So, Dilithium gets 10 points, Falcon gets 5 points and Rainbow gets 2 points.

1st: Falcon: 65 points.
2nd: Dilithium: 47 points
3rd: Rainbow: 30 points

And so the winner — and winning four races (key size, key generation race, signing key size race, and sign/verify race— is Falcon. Based on these races, I would say the betting is probably now:

Falcon: 4/6 (Fav)
Dilithium: 2/1
Rainbow: 50/1

But it all depends on what NIST see as being important. So here is Falcon:

and Rainbow:

And Dilithium: