There’s little doubt that some of the most important pillars of modern cryptography will tumble spectacularly once quantum computing, now in its infancy, matures sufficiently. Some experts say that could be in the next couple decades. Others say it could take longer. No one knows.
The uncertainty leaves a giant vacuum that can be filled with alarmist pronouncements that the world is close to seeing the downfall of cryptography as we know it. The false pronouncements can take on a life of their own as they’re repeated by marketers looking to peddle post-quantum cryptography snake oil and journalists tricked into thinking the findings are real. And a new episode of exaggerated research has been playing out for the past few weeks.
All aboard the PQC hype train
The last time the PQC—short for post-quantum cryptography—hype train gained this much traction was in early 2023, when scientists presented findings that claimed, at long last, to put the quantum-enabled cracking of the widely used RSA encryption scheme within reach. The claims were repeated over and over, just as claims about research released in September have for the past three weeks.
Today, almost all data on the Internet, including bank transactions, medical records, and secure chats, is protected with an encryption scheme called RSA (named after its creators Rivest, Shamir, and Adleman). This scheme is based on a simple fact—it is virtually impossible to calculate the prime factors of a large number in a reasonable amount of time, even on the world’s most powerful supercomputer. Unfortunately, large quantum computers, if and when they are built, would find this task a breeze, thus undermining the security of the entire Internet.
Luckily, quantum computers are only better than classical ones at a select class of problems, and there are plenty of encryption schemes where quantum computers don’t offer any advantage. Today, the U.S. National Institute of Standards and Technology (NIST) announced the standardization of three post-quantum cryptography encryption schemes. With these standards in hand, NIST is encouraging computer system administrators to begin transitioning to post-quantum security as soon as possible.
“Now our task is to replace the protocol in every device, which is not an easy task.” —Lily Chen, NIST
These standards are likely to be a big element of the Internet’s future. NIST’s previous cryptography standards, developed in the 1970s, are used in almost all devices, including Internet routers, phones, and laptops, says Lily Chen, head of the cryptography group at NIST who lead the standardization process. But adoption will not happen overnight.
“Today, public key cryptography is used everywhere in every device,” Chen says. “Now our task is to replace the protocol in every device, which is not an easy task.”
Why we need post-quantum cryptography now
Most experts believe large-scale quantum computers won’t be built for at least another decade. So why is NIST worried about this now? There are two main reasons.
First, many devices that use RSA security, like cars and some IoT devices, are expected to remain in use for at least a decade. So they need to be equipped with quantum-safe cryptography before they are released into the field.
“For us, it’s not an option to just wait and see what happens. We want to be ready and implement solutions as soon as possible.” —Richard Marty, LGT Financial Services
Second, a nefarious individual could potentially download and store encrypted data today, and decrypt it once a large enough quantum computer comes online. This concept is called “harvest now, decrypt later“ and by its nature, it poses a threat to sensitive data now, even if that data can only be cracked in the future.
Security experts in various industries are starting to take the threat of quantum computersseriously, says Joost Renes, principal security architect and cryptographer at NXP Semiconductors. “Back in 2017, 2018, people would ask ‘What’s a quantum computer?’” Renes says. “Now, they’re asking ‘When will the PQC standards come out and which one should we implement?’”
Richard Marty, chief technology officer at LGT Financial Services, agrees. “For us, it’s not an option to just wait and see what happens. We want to be ready and implement solutions as soon as possible, to avoid harvest now and decrypt later.”
NIST’s competition for the best quantum-safe algorithm
NIST announced a public competition for the best PQC algorithm back in 2016. They received a whopping 82 submissions from teams in 25 different countries. Since then, NIST has gone through 4 elimination rounds, finally whittling the pool down to four algorithms in 2022.
This lengthy process was a community-wide effort, with NIST taking input from the cryptographic research community, industry, and government stakeholders. “Industry has provided very valuable feedback,” says NIST’s Chen.
These four winning algorithms had intense-sounding names: CRYSTALS-Kyber, CRYSTALS-Dilithium, Sphincs+, and FALCON. Sadly, the names did not survive standardization: The algorithms are now known as Federal Information Processing Standard (FIPS) 203 through 206. FIPS 203, 204, and 205 are the focus of today’s announcement from NIST. FIPS 206, the algorithm previously known as FALCON, is expected to be standardized in late 2024.
The algorithms fall into two categories: general encryption, used to protect information transferred via a public network, and digital signature, used to authenticate individuals. Digital signatures are essential for preventing malware attacks, says Chen.
Every cryptography protocol is based on a math problem that’s hard to solve but easy to check once you have the correct answer. For RSA, it’s factoring large numbers into two primes—it’s hard to figure out what those two primes are (for a classical computer), but once you have one it’s straightforward to divide and get the other.
“We have a few instances of [PQC], but for a full transition, I couldn’t give you a number, but there’s a lot to do.” —Richard Marty, LGT Financial Services
Two out of the three schemes already standardized by NIST, FIPS 203 and FIPS 204 (as well as the upcoming FIPS 206), are based on another hard problem, called lattice cryptography. Lattice cryptography rests on the tricky problem of finding the lowest common multiple among a set of numbers. Usually, this is implemented in many dimensions, or on a lattice, where the least common multiple is a vector.
The third standardized scheme, FIPS 205, is based on hash functions—in other words, converting a message to an encrypted string that’s difficult to reverse
The standards include the encryption algorithms’ computer code, instructions for how to implement it, and intended uses. There are three levels of security for each protocol, designed to future-proof the standards in case some weaknesses or vulnerabilities are found in the algorithms.
Lattice cryptography survives alarms over vulnerabilities
Earlier this year, a pre-print published to the arXiv alarmed the PQC community. The paper, authored by Yilei Chen of Tsinghua University in Beijing, claimed to show that lattice-based cryptography, the basis of two out of the three NIST protocols, was not, in fact, immune to quantum attacks. On further inspection, Yilei Chen’s argument turned out to have a flaw—and lattice cryptography is still believed to be secure against quantum attacks.
On the one hand, this incident highlights the central problem at the heart of all cryptography schemes: There is no proof that any of the math problems the schemes are based on are actually “hard.” The only proof, even for the standard RSA algorithms, is that people have been trying to break the encryption for a long time, and have all failed. Since post-quantum cryptography standards, including lattice cryptography, are newer, there is less certainty that no one will find a way to break them.
That said, the failure of this latest attempt only builds on the algorithm’s credibility. The flaw in the paper’s argument was discovered within a week, signaling that there is an active community of experts working on this problem. “The result of that paper is not valid, that means the pedigree of the lattice-based cryptography is still secure,” says NIST’s Lily Chen (no relation to Tsinghua University’s Yilei Chen). “People have tried hard to break this algorithm. A lot of people are trying, they try very hard, and this actually gives us confidence.”
NIST’s announcement is exciting, but the work of transitioning all devices to the new standards has only just begun. It is going to take time, and money, to fully protect the world from the threat of future quantum computers.
“We’ve spent 18 months on the transition and spent about half a million dollars on it,” says Marty of LGT Financial Services. “We have a few instances of [PQC], but for a full transition, I couldn’t give you a number, but there’s a lot to do.”
As a result, India, China, and a range of technology organizations in the European Union and United States are researching and developing QKD and weighing standards for the nascent cryptography alternative. And the biggest question of all is how or if QKD fits into a robust, reliable, and fully future-proof cryptography system that will ultimately become the global standard for secure digital communications into the 2030s. As in any emerging technology standard, different players are staking claims on different technologies and implementations of those technologies. And many of the big players are pursuing such divergent options because no technology is a clear winner at the moment.
According to Ciel Qi, a research analyst at the New York-based Rhodium Group, there’s one clear leader in QKD research and development—at least for now. “While China likely holds an advantage in QKD-based cryptography due to its early investment and development, others are catching up,” says Qi.
Two different kinds of “quantum secure” tech
At the center of these varied cryptography efforts is the distinction between QKD and post-quantum cryptography (PQC) systems. QKD is based on quantum physics, which holds that entangled qubits can store their shared information so securely that any effort to uncover it is unavoidably detectable. Sending pairs of entangled-photon qubits to both ends of a network provides the basis for physically secure cryptographic keys that can lock down data packets sent across that network.
Typically, quantum cryptography systems are built around photon sources that chirp out entangled photon pairs—where photon A heading down one length of fiber has a polarization that’s perpendicular to the polarization of photon B heading in the other direction. The recipients of these two photons perform separate measurements that enable both recipients to know that they and only they have the shared information transmitted by these photon pairs. (Otherwise, if a third party had intervened and measured one or both photons first, the delicate photon states would have been irreparably altered before reaching the recipients.)
“People can’t predict theoretically that these PQC algorithms won’t be broken one day.” —Doug Finke, Global Quantum Intelligence
This shared bit the two people on opposite ends of the line have in common then becomes a 0 or 1 in a budding secret key that the two recipients build up by sharing more and more entangled photons. Build up enough shared secret 0s and 1s between sender and receiver, and that secret key can be used for a type of strong cryptography, called a one-time pad, that guarantees a message’s safe transmission and faithful receipt by only the intended recipient.
By contrast, post-quantum cryptography (PQC) is based not around quantum physics but pure math, in which next-generation cryptographic algorithms are designed to run on conventional computers. And it’s the algorithms’ vast complexity that makes PQC security systems practically uncrackable, even by a quantum computer. So NIST—the U.S. National Institute of Standards and Technology—is developing gold-standard PQC systems that will undergird tomorrow’s post-quantum networks and communications.
The big problem with the latter approach, says Doug Finke, chief content officer of the New York-based Global Quantum Intelligence, is PQC is only believed (on very, very good but not infallible evidence) to be uncrackable by a fully-grown quantum computer. PQC, in other words, cannot necessarily offer the ironclad “quantum security” that’s promised.
“People can’t predict theoretically that these PQC algorithms won’t be broken one day,” Finke says. “On the other hand, QKD—there are theoretical arguments based on quantum physics that you can’t break a QKD network.”
That said, real-world QKD implementations might still be hackable via side-channel, device-based, and other clever attacks. Plus, QKD also requires direct access to a quantum-grade fiber optics network and sensitive quantum communications tech, neither of which is exactly commonplace today. “For day-to-day stuff, for me to send my credit card information to Amazon on my cellphone,” Finke says, “I’m not going to use QKD.”
China’s early QKD lead dwindling
According to Qi, China may have originally picked QKD as a focal point of their quantum technology development in part because the U.S. was not directing its efforts that way. “[The] strategic focus on QKD may be driven by China’s desire to secure a unique technological advantage, particularly as the U.S. leads in PQC efforts globally,” she says.
In particular, she points to ramped up efforts to use satellite uplinks and downlinks as the basis for free-space Chinese QKD systems. Citing as a source China’s “father of quantum,” Pan Jianwei, Qi says, “To achieve global quantum network coverage, China is currently developing a medium-high orbit quantum satellite, which is expected to be launched around 2026.”
That said, the limiting factor in all QKD systems to date is their ultimate reliance on a single photon to represent each qubit. Not even the most exquisitely-refined lasers and fiber optic lines can’t escape the vulnerability of individual photons.
QKD repeaters, which would blindly replicate a single photon’s quantum state but not leak any distinguishing information about the individual photons passing through—meaning the repeater would not be hackable by eavesdroppers—do not exist today. But, Finke says, such tech is achievable, though at least 5 to 10 years away. “It definitely is early days,” he says.
“While China likely holds an advantage in QKD-based cryptography due to its early investment and development, others are catching up.” —Ciel Qi, Rhodium Group
“In China they do have a 2,000-kilometer network,” Finke says. “But it uses this thing called trusted nodes. I think they have over 30 in the Beijing to Shanghai network. So maybe every 100 km, they have this unit which basically measures the signal... and then regenerates it. But the trusted node you have to locate on an army base or someplace like that. If someone breaks in there, they can hack into the communications.”
Meanwhile, India has been playing catch-up, according to Satyam Priyadarshy, a senior advisor to Global Quantum Intelligence. Priyadarshy says India’s National Quantum Mission includes plans for QKD communications research—aiming ultimately for QKD networks connecting cities over 2,000-km distances, as well as across similarly long-ranging satellite communications networks.
Priyadarshy points both to government QKD research efforts—including at the Indian Space Research Organization—and private enterprise-based R&D, including by the Bengaluru-based cybersecurity firm QuNu Labs. Priyadarshy says that QuNu, for example, has been working on a hub-and-spoke framework named ChaQra for QKD. (Spectrum also sent requests for comment to officials at India’s Department of Telecommunications, which were unanswered as of press time.)
“A hybrid of QKD and PQC is the most likely solution for a quantum safe network.” —Satyam Priyadarshy, Global Quantum Intelligence
Multiple sources contacted for this article envisioned a probable future in which PQC will likely be the default standard for most secure communications in a world of pervasive quantum computing. Yet, PQC also cannot avoid its potential Achilles’ heel against increasingly powerful quantum algorithms and machines either. This is where, the sources suggest, QKD could offer the prospect of hybrid secure communications that PQC alone could never provide.
“QKD provides [theoretical] information security, while PQC enables scalab[ility],” Priyadarshy says. “A hybrid of QKD and PQC is the most likely solution for a quantum safe network.” But he added that efforts at investigating hybrid QKD-PQC technologies and standards today are “very limited.”
Then, says Finke, QKD could still have the final say, even in a world where PQC remains preeminent. Developing QKD technology just happens, he points out, to also provide the basis for a future quantum Internet.
“It’s very important to understand that QKD is actually just one use case for a full quantum network,” Finke says.
“There’s a lot of applications, like distributed quantum computing and quantum data centers and quantum sensor networks,” Finke adds. “So even the research that people are doing now in QKD is still very, very helpful because a lot of that same technology can be leveraged for some of these other use cases.”
Login
