Beam Me Up Scotty … It’s a Whole New Crypto World

Passing symmetric keys in a post-quantum world with Kyber-CRYSTALS

As if you didn’t know, quantum computers will put an end to all of our popular public-key and key exchange methods (ECC, RSA and Discrete Logs). And so NIST has been working on defining a standard for the best method to replace these, and recently they made their announcement on the final of the PQC (Post Quantum Cryptography) standardization process. For Public-Key Encryption and KEMs (Key Encapsulation Mechanisms) 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 [1], 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 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).
• FALCON (Lattice).
• Rainbow (Oil and Vinegar).

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…