As billions of dollars are being invested in making quantum computing a reality, many technical and ethical questions about technology need to be addressed. Of all the concerns, one of the greatest is what the future of security and encryption will look like and how we can make quantum-resistant encryption algorithms.
An example depiction of quantum cryptography. Image [modified] used courtesy of Quantum Xchange
To help answer this question, NIST announced a contest in 2016 for groups to develop and propose encryption algorithms that could solve the quantum challenge. This week, after six years, NIST has finally selected its first round of winners of the context, with NXP being one of them.
In this article, we’ll discuss the threat that quantum computing poses to conventional encryption and look closely at some of the contest winners.
Why Quantum Threatens Security
At its most basic, encryption is a series of mathematical functions performed to a binary sequence to alter an original message. The fundamental concept behind encryption is that it should be extremely easy to decrypt the message with access to the secret key. However, without that key, it should be virtually impossible to break.
Disregarding side-channels and other attack vectors, the most straightforward way to break encryption is brute force, which aims to manually guess the secret key one by one.
Today, key lengths can reach up to 128 bits or more, meaning there can be as many as 2128 possible key values. With this many permutations, even the world’s fastest supercomputers, which have reached up to 1.1 exaFLOPS, would take trillions of years to break by brute force.
Quantum computers are believed to be able to easily break conventional encryption algorithms. Image used courtesy of Active Cyber, IQC, Security Innovation, and NTRU
With that information in mind is where quantum computing comes in. In theory, quantum computers can perform calculations millions of times faster than even the faster supercomputer existing today. With this kind of computational power, it is believed that quantum computers will be able to break most existing encryption algorithms with relative ease.
For this reason, cryptographers, mathematicians, and computer scientists have been scrambling to devise new quantum-resistant algorithms that can withstand quantum computers’ brute force capabilities.
Winner for General Encryption
Out of the group of winners of NIST’s contest, NIST chose only one for general encryption. The winner is dubbed CRYSTALS-Kyber and is a quantum-resistant encryption algorithm for general encryption purposes that a group of engineers co-authored at NXP.
According to the algorithm’s creators, Kyber is an IND-CCA2-KEM (indistinguishability under chosen-ciphertext attack secure key encapsulation mechanism) algorithm and has its roots in learning-with errors (LWE) algorithms. Compared to previous LWE encryption schemes, the researchers claim that Kyber has improved by using a square matrix and the same noise distribution for developing the secret key.
On a quantum level, Kyber-512 aims to deliver security roughly equivalent to AES-128, Kyber-768 for AES-192, and Kyber-1024 for AES-256.
According to NIST, some of the key advantages of CRYSTALS-Kyber include its comparatively small encryption key sizes, the ease with which two parties can exchange the key, and the speed of operation.
Winner for Digital Signatures
Aside from general encryption, NIST also announced three winners in the field of quantum-resistant digital signatures.
Namely, the three algorithms selected are called:
Several academics from many international universities authored each of these algorithms, including researchers at other locations such as IBM Europe.
According to the NIST researchers, CRYSTALS-Dilithium and Falcon were praised for their high efficiency. Of the two, NIST recommended CRYSTALS-Dilithium as the primary algorithm used, while FALCON is said to be better suited for smaller-signature applications.
SPHINCS+, on the other hand, is said to be a more memory and time-intensive algorithm than the other two but is unique in its mathematical foundation.
An example of a small SPHINCS structure. Screenshot used courtesy of Bernstein et al
Specifically, it is based on a different mathematical approach than CRYSTALS-Dilithium, FALCON, and CRYSTALS-Kyber, which are all based on structured lattices, while SPHINCS+ is based on hash functions. For this reason, NIST considers SPHINCS+ a good “backup” for being unique and therefore uniquely hard to break.
Featured image used courtesy of N. Hanacek/NIST
Interested in other cryptography and security news? Read on in the articles down below.