Day 0 for the Building of a New World of Trust

Well, after so many years, it is nearly here …
Photo by mohammad alizade on Unsplash

Day 0 for the Building of a New World of Trust

Well, after so many years, it is nearly here …

It is part of NIST’s standardization process for PQC, and which has been running since 2016:

For Public-Key Encryption and KEMs (Key Exchange) we have:

  • Classic McEliece. This has been around for around 40 years, and has been shown to be fairly resistant to attack. It produces a fairly long encryption key, but produces a fairly small amount of ciphertext.
  • CRYSTALS-KYBER (Lattice). Uses LWE (Learning with Errors) with lattice methods. A new lattice attack was discovered within the period of the assessment, but it is hoped that an updated version of KYBER can be produced for the final assessment. NIST have some worried about its side-channel robustness, and is a strong contender for KEM.
  • NTRU (Lattice). This is a traditional structured lattice based approach, and has been around for longer than the other lattice methods — showing that it is perhaps more robust against attack and against intellitecual property claims.
  • SABER (Lattice). This is based on modular learning with rounding, and uses lattice methods. SABER has excellent performance, and is possibly near production ready. NIST’s only recommendation is that updates should perhaps consider side-channel attacks.

and for digital signatures:

  • CRYSTALS-DILITHIUM (Lattice). At present, CRYSTALS (Cryptographic Suite for Algebraic Lattices) supports two quantum robust mechanisms: Kyber for key-encapsulation mechanism (KEM) and key exchange; and Dilithium for a digital signature algorithm. CRYSTALS Dilithium uses lattice-based Fiat-Shamir schemes, and produces one of the smallest signatures of all the post-quantum methods, and with relatively small public and private key sizes.
  • FALCON (Lattice). Falcon is one of the finalists for the NIST standard for PQC (Post Quantum Cryptography), along with NTRU (Nth degree‐truncated polynomial ring units) and CRYSTALS-DILITHIUM. It is derived from NTRU and is a lattice-based methods for quantum robust digital signing. Falcon is based on the Gentry, Peikert and Vaikuntanathan method for generating lattice-based signature schemes, along with a trapdoor sampler — Fast Fourier sampling.
  • Rainbow (Oil and Vinegar). The multivariate polynomial problem is now being applied in quantum robust cryptography, where we create a trap door to allow us to quickly solve the n variables with m equations (which are multivariate polynomials). In the following example we sign a message with the private key and verify with the public key.

These are defined as the finalists, and a winner will be chosen from these, but because CRYSTALS-KYBER, NTRU, and SABER are lattice methods, NIST only wants one winner from a lattice technique. So it has drawn up a list for an alternative of: BIKE; FrodoKEM; HQC; NTRU Prime; and SIKE. And CRYSTALS-DILITHIUM and FALCON are lattice methods for digital signatures, so the alternative list has: GeMSS; Picnic; and SPHINCS+. NIST thus wants to guard against lattice methods being cracked in the future, and thus would like an alternative method as a back-up. A Windows binary for assessing the performance of the NIST finalists is here.

My analysis of the finalists is:

  • NIST Finalists (KEM) Speed Tests. KEM Speed. For KEM, NIST have defined the finalists of CRYSTALS Kyber (Lattice), Saber (Lattice), McEliece (Code-based) and NTRU (Lattice), and with alternative finalists of BIKE (code-based), HQC (code-based), FrodoKEM (Lattice), and SIKE (isogenies). This page provides a performance speed test for these methods.
  • NIST Finalists (Digital Signatures). Sig Speed. For digital signatures, NIST have defined the finalists of CRYSTALS Dilithium (Lattice), Falcon (Lattice), and Rainbow (Multivariate Quadractic). The alterative finalists are: SPHINCS+ (Hash-based stateless), and Picnic (Hash-based ZKP).
  • NIST Finalists Information. PQC Information. For digital signatures, NIST have defined the finalists of CRYSTALS Dilithium (Lattice), Falcon (Lattice), and Rainbow (Multivariate Quadractic). The alterative finalists are: SPHINCS+ (Hash-based stateless), and Picnic (Hash-based ZKP). For KEM, NIST have defined the finalists of CRYSTALS Kyber (Lattice), Saber (Lattice), McEliece (Code-based) and NTRU (Lattice), and with alternative finalists of BIKE (code-based), HQC (code-based), FrodoKEM (Lattice), and SIKE (isogenies).

For KEM, I analysed for key generation, encapsulation time, and decapsulation time, and found that Kyber scored highest in each of the categories:

And for digital signatures, it was Dilithium that scored highest in terms of key generation, signing and verification:

Conclusions

So my predictions is that Kyber will win KEM, and Dilithium will win for digital signatures. Here is the full analysis:

https://asecuritysite.com/pqc/

Once selected for a standard, we will then have the massive task of aging out RSA, ECC and discrete log methods from our existing PKI systems, and hunting down every piece of code that uses these methods.