Maintaining secrecy is a universal challenge, intensifying with impending increased difficulty.Secrecy is constantly sought, while masses of private data traverse the digital landscape. Encryption safeguards this information, using mathematical methods to thwart prying eyes, even those aided by potent computers.
The foundation of encryption faces an unexpected challenger: quantum computers, once deemed hypothetical. In the 1990s, scientists recognized their potential to leverage the peculiar physics of the atomic and electron realms, surpassing conventional computing limits. As quantum machines advance, the ability to unravel mathematical locks on encrypted data emerges, potentially exposing global secrets.
Present-day quantum computers lack the potency to breach existing security measures. However, as IBM and Google unveil more robust quantum machines, a sense of urgency grips scientists and governments. The impending milestone, dubbed Y2Q, signifies the year when quantum computers could dismantle the encoding schemes safeguarding electronic communications. Mathematician Michele Mosca warns of a potential systemic catastrophe if encryption is compromised.
Y2Q is coming. What does it mean?
Encryption is omnipresent in the digital realm, shielding emails, financial records, medical data, and various online transactions. It extends to physical devices like cars, robot vacuums, and baby monitors. Even critical infrastructure like power grids relies on encryption. The looming Y2Q challenge jeopardizes these ubiquitous protective measures. Michele Mosca, CEO of cybersecurity firm evolutionQ, emphasizes the astronomical stakes involved in securing this pervasive technology.
Named in homage to the Y2K bug, Y2Q poses a systemic threat like its predecessor. However, the comparison is incomplete; Y2Q's resolution is far more intricate than adjusting date representation. Today, computers are even more deeply ingrained in society, amplifying the challenge. Unlike Y2K, the arrival of Y2Q remains uncertain, adding an extra layer of complexity to the impending issue.
The Y2Q challenge prompts a reevaluation of cryptography, the art of encoding information. Scientists and mathematicians are fervently collaborating to revamp encryption methods, ensuring resilience against quantum decoding. The U.S. National Institute of Standards and Technology (NIST) spearheads an initiative to establish updated standards for post-quantum cryptography algorithms, with an anticipated release next year. The urgency to prepare for an undefined date underscores the gravity of the situation.
Simultaneously, a forward-looking initiative embraces quantum technology to construct an impervious quantum internet. Globally, scientists are establishing networks to transmit quantum information across cities, envisioning communication resistant to hacking. This innovative approach aligns with the idea that leveraging quantum capabilities could offer a more secure foundation for the future of interconnected communication.
How public-key cryptography works
Sharing a secret message involves encrypting it, distorting the information for later decoding. A basic cipher, like replacing A with 1, B with 2, is a simple method. Those privy to the key can decode and read the message, be it the intended recipient or a curious classmate.
This scenario illustrates symmetric-key cryptography, where a single key encodes and decodes a message. In actual communication, the key would be highly intricate, making it virtually impossible to guess. Regardless, the same secret key is employed for both encoding and decoding processes.
Computer scientist Peter Schwabe notes the historical use of symmetric-key cryptography for centuries, often in military or clandestine romantic contexts. However, in today's globally interconnected world, a challenge emerges. Transmitting the secret key to someone on the opposite side of the planet, especially someone unknown, becomes problematic. The risk of interception by unauthorized entities complicates the application of symmetric-key cryptography in a globalized setting.
In the 1970s, cryptographers introduced a solution to the symmetric-key challenge: public-key cryptography. This method employs specialized mathematical techniques, utilizing two distinct yet related keys. A public key encrypts messages, while a corresponding private key decodes them. For instance, if Alice wishes to message Bob, she employs his public key to encrypt the communication, making it decipherable only with Bob's private key. Intercepted messages, devoid of the private key, remain unintelligible to any potential eavesdroppers.
How to swap secrets with strangers
Public-key cryptography allows people in far-flung places who have never met to share secret information. A publicly available key is used to encode the message being sent, and a different but mathematically related private key — known only to the intended recipient — is used to decode the message.
Public-key methods extend to generating digital signatures, ensuring online identities are authentic. This verification is crucial for confirming the legitimacy of downloads or interactions online. The private key owner exclusively signs the message, while anyone can use the corresponding public key to validate its authenticity.
However, the prevalent public-key cryptography on the internet faces direct vulnerability from large-scale quantum computers. Additionally, symmetric-key cryptography often depends on public-key cryptography for sharing the essential secret key. This dual reliance places a substantial portion of internet security at risk.
Why quantum computers will threaten public-key cryptography
If public-key encryption secures your data like a hidden treasure beneath the floorboards, accessing this information requires a special entry point – a secret door, as described by Mosca. This door, known as a trapdoor, relies on unique mathematical maneuvers, where certain operations are easy in one direction but challenging in the opposite. For instance, multiplying two large prime numbers is swift, but deducing the primes from their product is time-consuming and often impractical for standard computers with sizable numbers.
The difficulty of factoring large numbers forms the basis for RSA, a prevalent public-key encryption method today. The discrete logarithm problem presents a similar one-way challenge. These two mathematical problems underpin the majority of current public-key cryptography. However, the advent of a sufficiently powerful quantum computer would dismantle these trapdoors.
Angela Robinson of NIST emphasizes the vulnerability of existing public-key algorithms to quantum attacks, stating, "Our whole digital world is relying on quantum-vulnerable algorithms." The revelation dates back to 1994 when mathematician Peter Shor, now at MIT, devised an algorithm enabling quantum computers to solve both the factoring and discrete logarithm problems. Quantum bits, or qubits, with their unique ability to exist in a superposition of 0 and 1 simultaneously, as well as entanglement, open avenues for quantum tactics like Shor's.
Dustin Moody of NIST reflects on the evolution of quantum computing since the theoretical days when it seemed distant and impractical. A quantum computing boom has since unfolded, with machines employing qubits made from diverse materials. IBM's Osprey, a superconducting quantum computer, boasts 433 qubits, a significant leap from its 2016 counterpart with five qubits. IBM plans to launch a model exceeding a thousand qubits this year.
Despite these advancements, the Y2Q threshold remains distant. Breaking RSA encryption demands a quantum computer with 20 million qubits, a milestone yet to be achieved. Michele Mosca estimates a 50 percent chance of a quantum computer potent enough to breach standard public-key encryption within the next 15 years. This timeframe, although seemingly long, aligns with historical patterns of major cryptography overhauls, emphasizing the complexity of the task. The urgency stems from the potential vulnerability of today's encrypted data to future quantum computers. As Mosca warns, without proactive measures, hackers could collect encrypted information now, awaiting the day when a powerful quantum computer emerges to decode it. Getting ahead of this challenge is imperative.
New algorithms could safeguard our security
Moody, Robinson, and their counterparts at NIST aim to proactively address the quantum threat by selecting and standardizing post-quantum encryption and digital signatures. These techniques must thwart hackers using quantum machines while still safeguarding against classical hacks.
After NIST issued a call for post-quantum algorithms in 2016, the team evaluated numerous proposed schemes, considering factors like security level and computational requirements. In July 2022, NIST identified four top schemes, with final standards anticipated in 2024. Organizations can then transition to post-quantum encryption. NIST continues to explore additional candidates.
Concurrently, broader endorsements for the post-quantum initiative are emerging. A White House memo in May 2022 set 2035 as the goal for U.S. government agencies to adopt post-quantum measures. In November, Google revealed its use of post-quantum cryptography in internal communications.
Many of the selected algorithms by NIST share a common foundation—lattice-based cryptography. This technique involves a mathematical problem related to describing a lattice, or a grid of points, using a set of arrows or vectors.
In the context of Manhattan's grid, a lattice is described by vectors representing block lengths and directions. Even without seeing a map, one could reproduce the grid using two arrows—one for the length and direction of an avenue block, and another for a street block. More complex vector sets, starting from different points in the city, can also replicate the grid. This lattice-based approach forms the backbone of the selected post-quantum algorithms.
The shortest vector problem poses a challenging question: Given a set of long vectors generating a lattice, what is the shortest vector that, when part of a set, produces the grid? If the only information available about a city is the location of specific landmarks, deducing the shortest vector corresponding to the city's blocks becomes a formidable task.
Expanding this challenge to hundreds of dimensions, it becomes a problem deemed so intricate that no computer, whether quantum or classical, could solve it within a reasonable timeframe. This difficulty is fundamental to the robustness of various post-quantum cryptography algorithms. In lattice-based cryptography, the private key is derived from a short vector, while the long vectors contribute to generating the public key.
Help from the shortest vector problem
Certain post-quantum encryption methods leverage the shortest vector problem. Consider a set of two long vectors (depicted in green on the left). By aligning these vectors end-to-end, a grid of points can be outlined (shown in blue). The shortest vector problem involves determining the shortest of these vectors (illustrated by the horizontal arrow in the grid on the right) that can be used to trace the same grid. While this task is relatively straightforward in two dimensions, applying it to cryptography demands solving the problem in hundreds of dimensions—an exceedingly challenging undertaking.
NIST explored various post-quantum schemes based on distinct mathematical problems, with the primary criterion being the strength of each algorithm's security. However, none of these algorithms possesses definitive proof of security against quantum or classical computers. An algorithm initially considered by NIST, known as SIKE, faced a setback. Researchers reported its compromise, as it took only 10 minutes to crack on a standard computer, as published in Advances in Cryptology – EUROCRYPT 2023.
Despite appearing as a setback, the breakdown of SIKE can be viewed as a step forward. Confidence in the security of cryptographic algorithms is often strengthened through rigorous testing and attempts to break them. As Peter Schwabe notes, "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." In the realm of cryptographic progress, the demise of some algorithms serves as a testament to the rigorous evaluation and improvement of security measures.
A quantum internet could bolster security
Quantum physics, while posing threats, also offers a solution: quantum key distribution (QKD) promises communication with mathematically proven security. By transmitting photons and measuring their properties upon arrival, a shared private key can be generated, immune to both quantum and classical hacks.
QKD relies on the no-cloning theorem, a principle in quantum physics asserting the impossibility of copying quantum information without altering the original data. This unique feature allows two parties to share a secret key, detecting any eavesdropping attempts through discrepancies during comparisons. If interference is detected, the communicators discard the compromised key and start anew. In the absence of foul play, the shared secret key can be safely used to encrypt communication over the standard internet, ensuring its security.
Unlike traditional methods, QKD requires quantum networks, where photons are created, transmitted along optical fibers, and manipulated at the destination. Quantum networks already exist in various cities worldwide, such as in Chicago suburbs, China, South Korea, the U.K., Tokyo, and the Netherlands. These networks, utilizing the peculiarities of quantum physics, provide a secure solution for sharing secret keys over extended distances without the need for vulnerable mathematical trapdoors.
While many quantum networks serve as testbeds, some, like China's and South Korea's, have real-world applications. Banks and government agencies utilize these networks, and companies such as Switzerland's ID Quantique offer commercial quantum key distribution (QKD) devices.
Although QKD's security is mathematically proven, practical implementation on quantum networks faces challenges. The intricacies of creating, transmitting, detecting, and storing quantum particles introduce potential loopholes. Rigorous design and testing are crucial to thwart hackers and maintain the system's integrity.
A critical limitation hindering quantum networks is the absence of quantum memory. Quantum physicist Xiongfeng Ma notes its significance, especially for long-distance quantum communication where particles may be lost. Quantum repeaters, special stations in the network with quantum memory, could address this issue. By entangling particles over short distances and then using quantum repeaters to extend entanglement to farther particles, scientists envision creating a global quantum internet. However, the practical development of quantum repeaters is yet to be realized, as quantum particles are easily influenced by external factors.
The European initiative, Quantum Internet Alliance, ambitiously aims to establish a network with quantum repeaters by 2029, spanning over 500 kilometers with two metropolitan-scale networks. This moonshot mission, challenging yet visionary, holds the promise of not only enhancing QKD security and distance but also enabling more advanced applications, such as entangling distant quantum computers for collaborative tasks. Ultimately, scientists envision a global quantum internet accessible to the public, transforming the way people connect and share information.
What does the future of cryptography look like?
Quantum key distribution (QKD) and post-quantum cryptography serve as complementary measures to counter the threat of quantum computers. According to physicist Nicolas Gisin, co-founder of ID Quantique, both approaches are necessary for comprehensive security. While post-quantum cryptography may be more practical for everyday activities that don't require the highest security standards, situations demanding long-lasting security for decades necessitate the unique attributes of QKD.
Looking ahead, quantum techniques offer the potential for even more advanced forms of security, such as blind quantum computing, covert quantum communication, and device-independent QKD. These methods promise extreme secrecy, enabling users to compute remotely, communicate securely, and ensure security even with potentially flawed communication devices.
The debate over extreme secrecy revolves around perspectives, with government agencies like the FBI, CIA, and NSA arguing that encryption can hinder their efforts to combat crime and terrorism. These agencies have historically advocated for back doors in encrypted communications, raising concerns about privacy and surveillance.
Quantum techniques, if implemented correctly, have the potential to thwart eavesdropping attempts, even by powerful government agencies. This prospect prompts a broader question posed by physicist David Awschalom: "It’s interesting to think about a world where, in principle, one might imagine perfect security. Is that a good thing or is that a bad thing?" The answer to this question reflects differing viewpoints on the balance between security and privacy in the evolving landscape of quantum technologies.
