Where is post-quantum cryptography used?

Post quantum cryptography (PQC) standardization is a program being run by the National Institute of Standards and Technology (NIST). It began in 2016, and by the end of 2017, NIST had received 82 submissions, of which 69 were accepted for further consideration. Through successive rounds of elimination, the number of proposals dropped from 69 to 26 to 7. Today, there are four remaining, and they are being readied for deployment.

The impetus for the PQC program is the existential threat that quantum computers will pose to existing security schemes like RSA (Rivest–Shamir–Adleman) public-key encryption and Elliptic Curve Cryptography (ECC) that are currently secure. According to a NIST analysis, developing and deploying new encryption standards takes about 20 years, and the PQC standardization program hopes to be completed before the deployment of commercial-scale quantum computing, as illustrated in Figure 1.

Figure 1. It can take 20 years to transition to new encryption standards. (Image: NIST)

Four remaining PQC algorithms

NIST has released draft standards for three of the four PQC algorithms selected in the most recent culling. A draft standard for the fourth, FALCON, is scheduled for release in 2024. The four PQC standards include:

CRYSTALS-Kyber is designed for general encryption purposes, such as creating secure websites, and is covered in Federal Information Processing Standard 203 (FIPS 203). It’s a quantum-safe algorithm (QSA) and is a member of the CRYSTALS (Cryptographic Suite for Algebraic Lattices) suite of algorithms. It’s an IND-CCA2-secure key encapsulation mechanism (KEM), whose security is based on the hardness of solving the learning-with-errors (LWE) problem over module lattices.
CRYSTALS-Dilithium is designed to protect digital signatures and is covered in FIPS 204. It’s strongly secure under chosen message attacks based on the hardness of lattice problems over module lattices. The security structure means that an adversary having access to a signing oracle cannot produce a signature of a message whose signature he hasn’t yet seen nor produce a different signature of a message that he already saw signed.
SPHINCS+ is also designed for digital signatures, is a stateless hash-based signature scheme, and is covered in FIPS 205. It offers three PQC security levels of 64, 96, and 128 bits. The parameters for each of the security levels provide 128 bits of security, 192 bits of security, and 256 bits of security, respectively. A separate algorithm identifier has been assigned for SPHINCS+ at each of these security levels.
FALCON also focuses on digital signatures and is scheduled to receive its own draft FIPS in 2024. FALCON uses multiple tools to ensure compactness and efficiency. To achieve this goal, the use of a NTRU lattice allows the size of the signatures and public keys to be relatively small, while Fast Fourier sampling permits efficient signature computations. Unlike RSA and ECC, NTRU is not known to be vulnerable to attacks from quantum computers.

Figure 2. The draft PQAC standards are moving toward expected finalization in 2024. (Image: Voice & Data)

More PQC Algorithms

The four algorithms outlined above are the first group of PQC standards NIST expects to create, but they will not be the last. NIST has also selected several ‘alternate’ PQC algorithms. The need for alternates to serve as backups was made evident in the previous round of assessment for seven algorithms when SIKE was cracked with a classical digital computer. According to NIST, that development proved the validity and thoroughness of the evaluation process.

Summary

The NIST PQC program is well down the track and has selected the first four finalist algorithms. Alternative algorithms have also been identified as a hedge should one of the four be cracked during the standard development process. While standardization is underway, it’s not the final step in the process. There’s more work to be done.