Keeping secrets is hard. Kids know it. Celebrities know it. National security experts know it, too.
And it’s about to get even harder.
There’s always someone who wants to get at the juicy details we’d rather keep hidden. Yet at every moment, untold volumes of private information are zipping along internet cables and optical fibers. That information’s privacy relies on encryption, a way to mathematically scramble data to prevent any snoops from deciphering it — even with the help of powerful computers.
But the mathematical basis of these techniques is under threat from a foe that has, until recently, seemed hypothetical: quantum computers.
In the 1990s, scientists realized that these computers could exploit the weird physics of the minuscule realm of atoms and electrons to perform certain types of calculations out of reach for standard computers. That means that once the quantum machines are powerful enough, they could crack the mathematical padlocks on encrypted data, laying bare the world’s secrets.
Today’s quantum computers are far too puny to defeat current security measures. But with more powerful quantum machines being regularly rolled out by the likes of IBM and Google, scientists, governments and others are beginning to take action. Experts are spreading the word that it’s time to prepare for a milestone some are calling Y2Q. That’s the year that quantum computers will gain the ability to crack the encoding schemes that keep electronic communications secure.
“If that encryption is ever broken,” says mathematician Michele Mosca, “it would be a systemic catastrophe.”
Y2Q is coming. What does it mean?
Encryption pervades digital life — safeguarding emails, financial and medical data, online shopping transactions and more. Encryption is also woven into a plethora of physical devices that transmit information, from cars to robot vacuums to baby monitors. Encryption even secures infrastructure such as power grids. The tools Y2Q threatens are everywhere. “The stakes are just astronomically high,” says Mosca, of the University of Waterloo in Canada, who is also CEO of the cybersecurity company evolutionQ.
The name Y2Q alludes to the infamous Y2K bug, which threatened to create computer havoc in the year 2000 because software typically used only two digits to mark the year (SN: 1/2/99, p. 4). Y2Q is a similarly systemic issue, but in many ways, it’s not a fair comparison. The fix for Y2Q is much more complex than changing how dates are represented, and computers are now even more inextricably entwined into society than two decades ago. Plus, no one knows when Y2Q will arrive.
Confronted with the Y2Q threat, cryptography — the study and the practice of techniques used to encode information — is facing an overhaul. Scientists and mathematicians are now working urgently to prepare for that unknown date by devising new ways of encrypting data that won’t be susceptible to quantum decoding. An effort headed by the U.S. National Institute of Standards and Technology, or NIST, aims to release new standards for such post-quantum cryptography algorithms next year.
Meanwhile, a longer-term effort takes a can’t-beat-’em-join-’em approach: using quantum technology to build a more secure, quantum internet. Scientists around the world are building networks that shuttle quantum information back and forth between cities, chasing the dream of communication that theoretically could be immune to hacking.
How public-key cryptography works
If you want to share a secret message with someone, you can encrypt it, garbling the information in such a way that it’s possible to decode it later.
Schoolkids might do this with a simple cipher: For example, replace the letter A with the number 1, B with 2 and so on. Anyone who knows this secret key used to encrypt the message can later decode the message and read it — whether it’s the intended recipient or another sneaky classmate.
It’s a simplified example of what’s called symmetric-key cryptography: The same key is used to encode and decode a message. In a more serious communication, the key would be much more complex — essentially impossible for anyone to guess. But in both cases, the same secret key is used to encode and decode.
This strategy was used in cryptography for millennia, says computer scientist Peter Schwabe of the Max Planck Institute for Security and Privacy in Bochum, Germany. “It was either used in a military context or it was used between lovers that were not supposed to love each other.”
But in the globally connected modern world, symmetric-key cryptography has a problem. How do you get the secret key to someone on the other side of the planet, someone you’ve never met, without anyone else getting their hands on it?
To solve this quandary, in the 1970s cryptographers devised public-key cryptography, which uses special mathematical tricks to solve the symmetric-key conundrum. It uses two different, mathematically related keys. A public key is used to encrypt messages, and a mathematically related private key decodes them. Say Alice wants to send a message to Bob. She looks up his public key and uses it to scramble her communication. Only Bob, with his private key, can decode it. To any snoops that intercept the message, it’s meaningless.
Public-key techniques are also used to create digital signatures. These signatures verify that someone online really is who they say they are, so you know you’re really downloading that new app from Apple, not some nefarious impersonator. Only the owner of a private key can sign the message, but anyone can use the public key to verify its authenticity.
The public-key cryptography that permeates the internet is directly vulnerable to full-scale quantum computers. What’s more, symmetric-key cryptography often relies on public-key cryptography to share the secret key needed to communicate. That puts the majority of internet security under threat.
Why quantum computers will threaten public-key cryptography
If public-key encryption keeps your data hidden away under the floorboards, then to read that information, you need to build a way in. You have to be able to access the data with your private key. “There’s got to be a secret door somewhere in there, where if I knock the right way, it opens up,” Mosca says.
Constructing such a trapdoor demands special mathematical tactics, based on operations that are easy to perform in one direction but hard in the opposite direction. Multiplying two prime numbers together is quick work for a computer, even if the numbers are very large. But it’s much more time-consuming for a computer to calculate the primes from their product. For large enough numbers, it’s impossible to do in a practical amount of time with a standard computer.
The challenge of finding the prime factors of a large number is behind one of the main types of public-key encryption used today, known as RSA. A hacker using a classical computer wouldn’t be able to deduce the private key from the public key. Another math problem, known as the discrete logarithm problem, is a similar one-way street.
These two mathematical problems underlie nearly all of the public-key cryptography in use today. But a sufficiently powerful quantum computer would blow their trapdoors wide open. “All of those public-key algorithms are vulnerable to an attack that can only be carried out by a quantum computer,” says mathematician Angela Robinson of NIST, in Gaithersburg, Md. “Our whole digital world is relying on quantum-vulnerable algorithms.”
This vulnerability came to light in 1994, when mathematician Peter Shor, now at MIT, came up with an algorithm that would allow quantum computers to solve both of these math problems. In quantum machines, the bits, called qubits, can take on values of 0 and 1 simultaneously, a state known as a superposition. And qubits can be linked with one another through the quantum connection called entanglement, enabling new tactics like Shor’s (SN: 7/8/17 & 7/22/17, p. 34).
“Back then, that was an interesting theoretical paper. Quantum computers were a distant dream,” says mathematician Dustin Moody of NIST, “but it wasn’t a practical threat.” Since then, there’s been a quantum computing boom (SN: 7/8/17 & 7/22/17, p. 28).
The machines are being built using qubits made from various materials — from individual atoms to flecks of silicon to superconductors (which conduct electricity without resistance) — but all calculate according to quantum rules. IBM’s superconducting quantum computer Osprey, for example, has 433 qubits. That’s up from the five qubits of the computer IBM unveiled in 2016. The company plans to roll out one with more than a thousand qubits this year.
That’s still far from the Y2Q threshold: To break RSA encryption, a quantum computer would need 20 million qubits, researchers reported in 2021 in Quantum.
Mosca estimates that in the next 15 years, there’s about a 50 percent chance of a quantum computer powerful enough to break standard public-key encryption. That may seem like a long time, but experts estimate that previous major cryptography overhauls have taken around 15 years. “This is not a Tuesday patch,” Mosca says.
The threat is even more pressing because the data we send today could be vulnerable to quantum computers that don’t exist yet. Hackers could harvest encrypted information now, and later decode it once a powerful quantum computer becomes available, Mosca says. “It’s just bad news if we don’t get ahead of this.”
New algorithms could safeguard our security
Getting ahead of the problem is the aim of Moody, Robinson and others who are part of NIST’s effort to select and standardize post-quantum encryption and digital signatures. Such techniques would have to thwart hackers using quantum machines, while still protecting from classical hacks.
After NIST put out a call for post-quantum algorithms in 2016, the team received dozens of proposed schemes. The researchers sorted through the candidates, weighing considerations including the level of security provided and the computational resources needed for each. Finally, in July 2022, NIST announced four schemes that had risen to the top. Once the final standards for those algorithms are ready in 2024, organizations can begin making the post-quantum leap. Meanwhile, NIST continues to consider additional candidates.
In parallel with NIST’s efforts, others are endorsing the post-quantum endeavor. In May 2022, the White House put out a memo setting 2035 as the goal for U.S. government agencies to go post-quantum. In November, Google announced it is already using post-quantum cryptography in internal communications.
Several of the algorithms selected by NIST share a mathematical basis — a technique called lattice-based cryptography. It relies on a problem involving describing a lattice, or a grid of points, using a set of arrows, or vectors.
In math, a lattice is described by a set of vectors used to produce it. Consider Manhattan. Even if you’d never seen a map of the city, you could roughly reproduce its grid using two arrows, one the length and direction of an avenue block and the other matching a street block. Discounting the city’s quirks, such as variations in block lengths, you’d just place arrows end-to-end until you’ve mapped out the whole grid.
But there are more complicated sets of vectors that can reproduce the city’s grid. Picture two arrows starting, for example, at Washington Square Park in lower Manhattan, with one pointing to Times Square in Midtown and the other to a neighboring landmark, the Empire State Building. Properly chosen, two such vectors could also be used — with more difficulty — to map out the city’s grid.
A math problem called the shortest vector problem asks: Given a set of long vectors that generate a lattice, what is the shortest vector that can be used as part of a set to produce the grid? If all you knew about the city was the location of those three landmarks, it’d be quite a task to back out the shortest vector corresponding to the city’s blocks.
Now, picture doing that not for a 2-D map, but in hundreds of dimensions. That’s a problem thought to be so difficult that no computer, quantum or classical, could do it in a reasonable amount of time.
The difficulty of that problem is what underlies the strength of several post-quantum cryptography algorithms. In lattice-based cryptography, a short vector is used to create the private key, and the long vectors produce the public key.
Other post-quantum schemes NIST considered are based on different math problems. To choose among the options, NIST mathematicians’ chief consideration was the strength of each algorithm’s security. But none of these algorithms are definitively proved to be secure against quantum computers, or even classical ones. One algorithm originally considered by NIST, called SIKE, was later broken. It took just 10 minutes to crack on a standard computer, researchers reported in April in Advances in Cryptology – EUROCRYPT 2023.
Although it might seem like a failure, the SIKE breakdown can be considered progress. The faith in the security of cryptographic algorithms comes from a trial by fire. “The more [that] smart people try to break something and fail, the more confidence we can get that it’s actually hard to break it,” Schwabe says. Some algorithms must perish in the process.
A quantum internet could bolster security
Quantum physics taketh away, but also, it gives. A different quantum technique can allow communication with mathematically proved security. That means a future quantum internet could, theoretically at least, be fully safe from both quantum and classical hacks.
By transmitting photons — particles of light — and measuring their properties upon arrival, it’s possible to generate a shared private key that is verifiably safe from eavesdroppers.
This quantum key distribution, or QKD, relies on a principle of quantum physics called the no-cloning theorem. Essentially, it’s impossible to copy quantum information. Any attempt to do so will alter the original information, revealing that someone was snooping. “Someone who was trying to learn that information would basically leave a fingerprint behind,” says quantum engineer Nolan Bitner of Argonne National Laboratory in Lemont, Ill.
This quirk of quantum physics allows two people to share a secret key and, by comparing notes, determine whether the key has been intercepted along the way. If those comparisons don’t match as expected, someone was eavesdropping. The communicators discard their key and start over. If there is no sign of foul play, they can safely use their shared secret key to encrypt their communication and send it over the standard internet, certain of its security. It’s a quantum solution to the quandary of how two parties can share secret keys without ever meeting. There’s no need for a mathematical trapdoor that might be vulnerable to an undiscovered tactic.
But QKD can’t be done over normal channels. It requires quantum networks, in which photons are created, sent zipping along optical fibers and are manipulated at the other end.
Such networks already snake through select cities in the world. One threads through Chicago suburbs from the University of Chicago to Argonne lab and Fermilab in Batavia, for a total of 200 kilometers. In China, an extensive network connects cities along a more than 2,000-kilometer backbone that wends from Beijing to Shanghai, along with two quantum satellites that beam photons through the air. A quantum network crisscrosses South Korea, and another links several U.K. cities. There are networks in Tokyo and the Netherlands — the list goes on, with more to come.
Many of these networks are test-beds used by researchers to study the technology outside of a lab. But some are getting real-world use. Banks use China’s network, and South Korea’s links government agencies. Companies such as ID Quantique, based in Switzerland, offer commercial QKD devices.
QKD’s security is mathematically proven, but quantum networks can fall short of that guarantee in practice. The difficulty of creating, transmitting, detecting and storing quantum particles can open loopholes. Devices and networks must be painstakingly designed and tested to ensure a hacker can’t game the system.
And one missing component in particular is holding quantum networks back. “The number one device is quantum memory,” says quantum physicist Xiongfeng Ma of Tsinghua University in Beijing. When sending quantum information over long distances through fibers, particles can easily get lost along the way. For distances greater than about 100 kilometers, that makes quantum communication impractical without the use of way stations that amplify the signal. Such way stations temporarily convert data into classical, rather than quantum, information. That classical step means hackers could target these “trusted nodes” undetected, marring QKD’s pristine security. And it limits what quantum maneuvers the networks can do.
It’s not possible to create pairs of particles that are entangled over long distances in a network like this. But special stations sprinkled throughout the network, called quantum repeaters, could solve the problem by storing information in a quantum memory. To create far-flung entangled particles, scientists could first entangle sets of particles over short distances, storing them in quantum memories at each quantum repeater. Performing certain operations on the entangled particles could leapfrog that entanglement to other particles farther apart. By repeating this process, particles could be entangled across extended distances.
But, thanks in part to quantum particles’ tendency to be easily perturbed by outside influences, scientists have yet to develop a practical quantum repeater. “When that does appear, it’s likely to catalyze global quantum networks,” says David Awschalom, a physicist at the University of Chicago. Not only will such technologies allow longer distances and better security for QKD, but they will also enable more complicated tasks, like entangling distant quantum computers to allow them to work together.
A European effort called the Quantum Internet Alliance aims to build a network with quantum repeaters by the end of 2029, creating a backbone stretching over 500 kilometers, in addition to two metropolitan-scale networks. The effort is “super challenging,” says physicist and computer scientist Stephanie Wehner of Delft University of Technology in the Netherlands. “We are on a moon shot mission.” Eventually, scientists envision a global quantum internet.
Awschalom imagines the networks becoming accessible to all. “Wouldn’t it be great to be able to go to a public library and be able to get onto a quantum network?”
What does the future of cryptography look like?
QKD and post-quantum cryptography are complementary. “In order to overcome the threat of the quantum computers we need both,” says physicist Nicolas Gisin of the University of Geneva and cofounder of ID Quantique. When people are exchanging information that doesn’t require the utmost security — say, using a mobile phone to post cat memes on Reddit — post-quantum cryptography will be more practical, as it doesn’t demand a to-and-fro of individual quantum particles. But “there are really situations where we want to make sure that the security is going to last … for several decades, and post-quantum cryptography cannot guarantee that,” Gisin says.
Eventually, quantum techniques could allow for even more advanced types of security, such as blind quantum computing. In that scheme, a user could compute something on a remote quantum computer without anyone being able to determine what they’re computing. A technique called covert quantum communication would allow users to communicate securely while hiding that they were exchanging messages at all. And device-independent QKD would ensure security even if the devices used to communicate are potentially flawed (SN: 8/27/22, p. 10).
The appeal of such extreme secrecy, of course, depends upon whether you’re the secret-keeper or the snoop. In the United States, government agencies like the FBI, CIA and the National Security Agency have argued that encryption makes it difficult to eavesdrop on criminals or terrorists. The agencies have a history of advocating for back doors that would let them in on encrypted communications — or building in secret back doors.
But quantum techniques, done properly, can prevent anyone from intercepting secrets, even powerful government agencies.
“It’s interesting to think about a world where, in principle, one might imagine perfect security,” Awschalom says. “Is that a good thing or is that a bad thing?”
Source: Physics - www.sciencenews.org
