Planning for a Quantum Robust Digital World
Planning for a Quantum Robust Digital World
So one of the most fundamental questions in cybersecurity is how we will replace our existing public key methods with something that cannot be cracked by quantum computers. We rely so much on RSA, Diffie Hellman and ECC methods, for our key exchange methods in TLS and VPN (ECDH), within the encryption of secret keys (ECIES), in digital signatures (ECDSA and DSA) and in the proof of identity. It is a core part of our secure digital world. As quantum computers will crack our existing key exchange methods, our public key encryption and our digital signatures, we need to plan towards the future and start to integrate methods that are still secure in an era of quantum computers.
And so NIST has been working on defining a standard for the best method to replace these, and yesterday they made their announcement on the final of the PQC (Post Quantum Cryptography) standardization process. 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 worries 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 intellectual 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 method 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 alterative 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 backup.
Here is a quick overview of the most serious of contenders:
and which uses the Learning With Errors (LWE) method:
But, if you are interested, I have outlined many of the methods here:
Conclusions
The replacement of our existing public key methods needs to be planned now, so if your company uses secure tunnels, digital signatures, secure key exchange, and so on, start planning soon.