Peter Shor published one of the earliest algorithms for quantum computers in 1994. Running Shor’s algorithm on a hypothetical quantum computer, one could rapidly factor enormous numbers—a seemingly innocuous superpower. But because the security of digital information relies on such math, the implications of Shor’s algorithm were ground-shaking.
It’s long been prophesied that modern cryptography, employed universally across the devices we use every day, will die at the hands of the first practical quantum computer.
Naturally, researchers have been searching for secure alternatives.
In 2016, the US National Institute of Standards and Technology (NIST) announced a competition to create the first post-quantum cryptographic algorithms. These programs would run on today’s computers but defeat attacks by future quantum computers.
Beginning with a pool of 82 submissions from around the world, NIST narrowed the list to four in 2022. The finalists went by the names CRYSTALS-Kyber, CRYSTALS-Dilithium, Sphincs+, and FALCON. This week, NIST announced three of these have become the first standardized post-quantum algorithms. They’ll release a standard draft of the last, FALCON, by the end of the year.
The algorithms, according to NIST, represent the best of the best. Kyber, Dilithium, and FALCON employ an approach called lattice-based cryptography, while Sphincs+ uses an alternative hash-based method. They’ve survived several years of stress testing by security experts and are ready for immediate use.
The release includes code for the algorithms alongside instructions on how to implement them and their intended uses. Like earlier encryption standards developed by the agency in the 1970s, it’s hoped wide adoption will ensure interoperability between digital products and consistency, lowering the risk of error. The first of the group, renamed ML-KEM, is for general encryption, while the latter three (now ML-DSA, SLH-DSA, and FN-DSA) are for digital signatures—that is, proving that sources are who they say they are.
Arriving at standards was a big effort, but broad adoption will be bigger.
While the idea that future quantum computers could defeat standard encryption is fairly uncontroversial, when it will happen is murkier. Today’s machines, still small and finicky, are nowhere near up to the task. The first machines able to complete useful tasks faster than classical computers aren’t expected until later this decade at the very earliest. But it’s not clear how powerful these computers will have to be to break encryption.
Still, there are solid reasons to get started now, according to proponents. For one, it’ll take as long as 10 to 15 years to roll out post-quantum cryptography. So, the earlier we kick things off the better. Also, hackers may steal and store encrypted data today with the expectation it can be cracked later—a strategy known as “harvest now, decrypt later.”
“Today, public key cryptography is used everywhere in every device,” Lily Chen, head of cryptography at NIST, told IEEE Spectrum. “Now our task is to replace the protocol in every device, which is not an easy task.”
There are already some early movers, however. The Signal Protocol underpinning Signal, WhatsApp, and Google Messages—products used by more than a billion people—implemented post-quantum cryptography based on NIST’s Kyber algorithm alongside more traditional encryption in late 2023. Apple did the same for iMessages earlier this year.
It’s notable both opted to run the two in parallel, as opposed to going all-in on post-quantum security. NIST’s algorithms have been scrutinized, but they haven’t been out in the wild for nearly as long as traditional approaches. There’s no guarantee they won’t be defeated in the future.
An algorithm in the running two years ago, SIKE, met a quick and shocking end when researchers took it down with some clever math and a desktop computer. And this April, Tsinghua University’s, Yilei Chen, published a pre-print on the arXiv in which he claimed to show lattice-based cryptography actually was vulnerable to quantum computers—though his work was later shown to be flawed and lattice cryptography still secure.
To be safe, NIST is developing backup algorithms. The agency is currently vetting two groups representing alternative approaches for general encryption and digital signatures. In parallel, scientists are working on other forms of secure communication using quantum systems themselves, though these are likely years from completion and may complement rather than replace post-cryptographic algorithms like those NIST is standardizing.
“There is no need to wait for future standards,” said Dustin Moody, a NIST mathematician heading the project, in a release. “Go ahead and start using these three. We need to be prepared in case of an attack that defeats the algorithms in these three standards, and we will continue working on backup plans to keep our data safe. But for most applications, these new standards are the main event.”
Image Credit: IBM
