SABER: Learning with Rounding … For Post-Quantum Crypto, It’s All About Lattice

NIST is now finalising the post-quantum cryptography competition. Overall the methods we can use to replace our existing public key methods are:

• Hash-based/symmetric-based. This includes Merkle signatures, SPHINCS and Picnic, and are used to create digital signatures. They cannot be used for public-key encryption and involve creating a range of private/public key pairs, and which are only used once. We must keep a track of the key pairs that we have used, in order to not use the again.
• Code-based. This includes McEliece and Niederreiter, and have been studied for decades.
• Multivariate. This involves multivariate quadratic methods. An example of this is the oil-and-vinegar method [here].
• Lattice-based. This includes NTRU (Nth degree TRUncated polynomial ring), learning with errors (LWE), Ring LWE, and Learning with Rounding. These have some of the best attributes for creating digital signatures, key exchange and encryption, and with reasonably small encryption keys and ciphertext sizes.
• Isogenies. This includes Supersinglar elliptic curve isogenies. These are interesting but are rather slow at the current time.

For Public-Key Encryption and KEMs (Key Exchange), NIST has the following as finalists:

• 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…