Will These Algorithms Save You From Quantum Threats?

Advertisement

In 1994, a Bell Labs mathematician named Peter Shor cooked up an algorithm with frightening potential. By vastly reducing the computing resources required to factor large numbers—to break them down into their multiples, like reducing 15 to 5 and 3—Shor’s algorithm threatened to upend many of our most popular methods of encryption.

Fortunately for the thousands of email providers, websites, and other secure services using factor-based encryption methods such as RSA or elliptic curve cryptography, the computer needed to run Shor’s algorithm didn’t exist yet. 

Shor wrote it to run on quantum computers which, back in the mid-1990s, were largely theoretical devices that scientists hoped might one day outperform classical computers on a subset of complex problems.

Advertisement

In the decades since, huge strides have been made toward building practical quantum computers, and government and private researchers have been racing to develop new quantum-proof algorithms that will be resistant to the power of these new machines. For the last six years, the National Institute of Standards and Technology (NIST)—a division of the US Department of Commerce—has been running a competition to find the algorithms that it hopes will secure our data against quantum computers. This week, it published the results.

NIST has whittled hundreds of entries from all over the world to an initial list of just four: CRYSTALS-Kyber for general encryption, and CRYSTALS-Dilithium, FALCON, and SPHINCS+ for use in digital signatures during identity verification or when signing digital documents. “People have to understand the threat that quantum computers can pose to cryptography,” says Dustin Moody, who leads the post-quantum cryptography project at NIST. “We need to have new algorithms to replace the ones that are vulnerable, and the first step is to standardize them.”

Advertisement

Just as RSA encryption relies on the difficulty of factoring extremely large numbers, three of the four algorithms unveiled this week use a complicated mathematical problem that’s expected to be difficult for even quantum computers to wrestle with. Structured lattices are abstract multi-dimensional grids that are extremely challenging to navigate unless you know the shortcuts. In structured lattice cryptography, as with RSA, the sender of a message will encrypt the contents using the recipient’s public key, but only the receiver will have the keys to decrypt it. With RSA the keys are factors—two large prime numbers that are easy to multiply together but difficult to ascertain if you have to work backwards. In these post-quantum cryptography algorithms the keys are vectors, directions through the maze of a structured lattice.

Although it will be a few years before these standards are published in their final form, it’s a pretty big moment. “For the first time, we have something to use against a quantum threat,” says Ali El Kaafarani, the CEO of PQShield, which worked on the FALCON algorithm.

Advertisement