Introduction

The NIST (National Institute of Standards and Technology) recently revealed its post-quantum computation standards for cryptography on July 5th, 2022. The four finalists of the standardization process include one public key cryptography algorithm named CRYSTALS-Kyber and three signature algorithms: CRYSTALS-Dilithium, FALCON, and SPHINCS. What does this mean for the average consumer?

In short, nothing yet.

Although quantum computers have made quite a splash in the world, especially after Google declared quantum supremacy, there is still a lot to be done. These machines are still incredibly error-prone and hardly accessible to the public. The sole exception is that of the IBM Quantum Experience center where you can use IBM’s quantum computers to run your code.

Basic rundowns of the algorithms follow:

All four finalist algorithms utilize the SHAKE algorithm to generate keys.

Public Key Cryptography Algorithm: Kyber

The only public key cryptography algorithm selected by the NIST for post-quantum cryptography was CRYSTALS-Kyber. Kyber, in its current stage, is about comparable to AES-128 with a 512-bit key length, with the 768-bit key length being comparable to AES-192. For those unfamiliar, AES (Advanced Encryption Standard) is the current standard for cryptography and is quantum-resistant, at least somewhat. This result gets more significant when Kyber combines with another algorithm such as the quantum-resistant Elliptic-Curve-Cryptography algorithm. Kyber primarily relies on the use of lattice problems to create the ciphertext and its corresponding key. Lattice problems were originally a candidate in general for PQC by utilizing Learning With Errors problems. Quote Applebaum et al.

“The LWE assumption states that it is hard to distinguish from uniform the distribution (A,As+e), where A is a uniformly-random matrix in Zm×nq,s is a uniformly-random vector in Znq, and e is a vector with random “small” coefficients chosen from some distribution.” 

As Kyber (alongside all of the other algorithms here) is still experimental, it will definitely face more roadblocks, however, this is a promising first result. 

Signature Algorithms:

CRYSTALS-Dilithium

The creators of Kyber also landed a finalist position on the signature side with Dilithium. Dilithium utilizes a very similar mathematical algorithm to Kyber to generate its keys and as such, both algorithms utilize LWE to generate their respective outputs. 

FALCON

Similar to Dilithium and Kyber, FALCON utilizes lattice problems to create signatures for files. However, FALCON differs in its basic cryptographic structure it was originally meant to work with NTRU, an eliminated competitor for PQC in public key cryptography. While Dilithium is relatively inefficient, FALCON has a rated keygen speed of 8.64ms for a 512-bit signature and 27.45ms for 1024-bit when ran on a Coffee Lake laptop CPU with very little impact on performance and RAM consumption. For mobile applications, FALCON may be a viable option.

SPHINCS

SPHINCS was revealed in 2015 and currently has 3 possible options for signatures, SHAKE-256, SHA-256, and Haraka. Haraka, the outlier, is an algorithm that relies on AES to quickly implement a solution to post-quantum hashing and as such promises easy integration and efficiency.

Other algorithms such as SIKE or SABER failed for varying reasons. For example, SIKE has a security flaw allowing malicious actors to recover the key and break the encryption within minutes on a single-core processor.

More information is available on the NIST page or at the algorithm’s respective sites. 

If you’re interested in reading more news such as this, visit the main news site here!