Post-quantum cryptography (PQC) refers to a new set of cryptographic algorithms designed to protect data and systems against threats posed by quantum computers capable of running Shor’s algorithm, which could break classic public key cryptographic algorithms. While classical computers use bits as the basic unit of information, quantum computers use quantum bits (qubits). This allows quantum computers to perform complex mathematical calculations and solve problems exponentially faster than classical computers. On the other hand, the unparalleled processing power also allows them to potentially break today’s widely-used cryptographic algorithms, such RSA and ECDH and digital signature algorithms like RSA, ECDSA, and EdDSA. Post-quantum cryptography aims to develop new cryptographic algorithms that can withstand quantum computing attacks and ensure the authenticity, confidentiality, and integrity of digital communications.
Quantum computing is a double-edged sword. While the massive computational power of quantum computers promises ground-breaking advancements in various fields such as science, finance, pharmaceuticals, and energy, it also poses a serious threat to current public-key cryptography.
Quantum computers operate on the principles of quantum mechanics, such as superposition and entanglement, that help them perform complex mathematical calculations at speeds inconceivable by today’s classical computers. While this is great, it also implies that quantum computers have the power to break the cryptographic algorithms that underpin much of today’s digital security infrastructure.
Today, all digital transactions and communications are protected through public key cryptography algorithms such as RSA and ECDH and digital signature algorithms like RSA, ECDSA, and EdDSA. These encryption algorithms help protect data at rest and in transit, regardless of location and create a safe environment for Internet communications. Breaking these algorithms by solving the complex math problems behind them requires massive computational power that today’s classical computers do not have.
However, the arrival of large-scale quantum computers, such as a CRQC (cryptographically relevant quantum computer), could have dire implications. With their immense processing power, these machines could potentially break today’s encryption algorithms, particularly RSA, with alarming ease. This scenario would potentially leave much of today’s sensitive encrypted data vulnerable and at risk of exposure.
In 1994, Peter Shor developed an algorithm (now called Shor’s algorithm) that could factorize large integers exponentially faster than the best-known classical algorithms. This demonstrated the real-world possibility of quantum computing breaking the RSA algorithm.
With the promise of quantum computing growing stronger, threat actors are not waiting. They have already begun intercepting and storing encrypted data, even though they lack the means to decrypt it with current technology. This strategy, known as data harvesting, is to wait for the day when powerful quantum computers are readily available to decrypt this data.
The impact of quantum computing also goes beyond encryption. Grover’s algorithm, another quantum algorithm, can significantly speed up brute-force search processes, effectively halving the security strength of symmetric key algorithms such as AES. This means that keys previously considered secure would need to be doubled in size to maintain the same level of security against quantum attacks.
In light of the very real quantum threat, the adoption of post-quantum cryptography (PQC) is not just a suggestion, it’s a necessity. PQC is the key to building quantum resilience and safeguarding our digital infrastructures, all while harnessing the power of quantum computing.
Post-quantum cryptography algorithms are being developed as part of a global effort involving a diverse array of stakeholders, including scientists, academic researchers, cryptography experts, governmental bodies, and the private sector.
To make the most of this transformative technology, the White House published two presidential directives in 2022, the first defined policies and initiatives for investments in core QIS research programs, and the second laid out specific goals to effectively address the potential security risks of quantum computers.
Leading the charge for PQC is the National Institute of Standards and Technology (NIST) in the United States, which has organized an international competition to standardize post-quantum cryptographic algorithms. This competition has attracted submissions from cryptographic researchers and institutions worldwide, including prominent universities, research labs, and tech companies.
Big technology firms such as Google, IBM, and Intel are also actively researching and developing post-quantum cryptographic solutions, integrating these advancements into their products and services to future-proof their security infrastructures. Collaborations across these sectors are driving the development, analysis, and implementation of robust post-quantum cryptographic standards, ensuring they meet security, performance, and interoperability needs in a post-quantum world.
NIST is working on standardizing post-quantum cryptographic algorithms. The process includes multiple rounds of evaluation, considering security, performance, and implementation aspects. The aim is to provide a suite of cryptographic algorithms that can replace or augment current standards in the face of the threat posed by quantum computing.
In July 2022, NIST announced the first four PQC algorithms, powerful enough to withstand quantum-enabled attacks. These four recommended algorithms are expected to be finalized in July 2024.
The four algorithms are designed for two chief use cases where encryption is typically used: general encryption and digital signatures.
NIST recommends CRYSTALS-Dilithium as the primary algorithm. The FALCON algorithm will be used for applications that need smaller signatures than Dilithium can provide. The third algorithm, SPHINCS+, is said to be relatively larger and slower than the other two but has been selected as a backup since it is based on a different mathematical approach than the other three.
Once NIST announces the standard PQC algorithms, today’s cryptographic standards will eventually be deprecated and replaced with newer quantum-safe standards. Protecting digital assets and preventing cyberattacks will then come down to how quickly organizations can migrate their cryptographic systems to quantum-safe standards. The longer it takes to transition, the more the risk of exposure. Given the complexity, costs, and time involved in upgrading cryptographic systems, organizations need to plan and prepare their PKI proactively for PQC implementation.
While the discussion on quantum mechanics as a branch of physics goes back to the early 1900s, the idea of quantum computers emerged in the 1980s, largely due to the groundbreaking observations of physicists Richard Feynman and David Deutsch. Feynman’s insight that classical computers struggle to model quantum phenomena accurately due to their exponential complexity, and his suggestion of a computer built using quantum mechanical principles, laid the foundation for quantum algorithms and the broader field of quantum information science. Deutsch later formulated the idea of a universal quantum computer, capable of performing any computational task more efficiently than classical computers for specific problems. These seminal contributions set the stage for the future of quantum computing.
1994 was a pivotal year for quantum computing, as mathematician Peter Shor developed an algorithm that would change the game. Shor’s algorithm, capable of efficiently factoring large integers , demonstrated that a sufficiently powerful quantum computer could solve complex mathematical problems in a matter of seconds, a task that would take several years for the best-known classical algorithms to develop. This revelation not only highlighted the potential of quantum computing to break traditional encryption algorithms, but also sparked a wave of increased research and investment in the development of quantum computers and quantum-resistant encryption methods.
In 1996, computer scientist Lov Grover introduced an important quantum algorithm known as Grover’s algorithm. This algorithm allows quantum computers to search through an unsorted database at unprecedented speed when compared to classical computers. The practical implications of this are significant. For instance, quantum computers can perform brute-force searches—like trying out every possible key to break an encryption—much more quickly. If it would take a classical computer a million tries to find the right key, a quantum computer might only need a thousand. This breakthrough in cryptography catalyzed further research in the development of quantum-resistant algorithms, highlighting the real-world impact of quantum computing.
Over the subsequent decades, quantum research made significant progress, marked by experimental demonstrations of small-scale quantum processors, increased qubit coherence times, and advancements in error correction and quantum algorithms, bringing the theoretical promise of quantum computing closer to practical realization.
In 2019, Google announced the first-generation Sycamore processor, which marked a significant milestone in the quantum journey. Google claimed that the 53-qubit processor could perform a calculation in 200 seconds, which would have taken the world’s most powerful supercomputer 10,000 years.
In November 2022, IBM unveiled its most powerful quantum computing processor, with 433 qubits (quantum bits). Nicknamed the Osprey, the processor is nearly three times faster than the company’s 127-qubit Eagle processor, which it unveiled in 2021, and more than eight times faster than Google’s Sycamore processor.
At present, the field of quantum computing continues to advance at great velocity, with researchers and tech giants working on developing powerful and stable quantum processors. Additionally, new algorithms and error-correction techniques are being developed to enhance the practical usability of quantum computers and realize their transformative potential across various industries.
Quantum computers operate on the principles of quantum mechanics, utilizing qubits instead of classical bits to represent and process information. While classical bits can be either 0 or 1, qubits can be 0, 1, or both at the same time. Additionally, Qubits can become entangled, a phenomenon where the state of one qubit influences the state of another, regardless of the distance between them. These two properties—Superposition and entanglement—enable quantum computers to perform multiple calculations at once and process complex problems much faster than classical computers.
However, quantum computing also faces significant challenges. Maintaining qubit coherence has been a persistent challenge; quantum states are fragile and easily disrupted by external noise and environmental factors, requiring precise control and isolation techniques at extremely low temperatures. Another challenge is scaling quantum systems to larger numbers of qubits while maintaining coherence and reducing error rates, which currently limit the complexity and reliability of computations. Additionally, quantum error correction is crucial to mitigate errors that arise from imperfect operations and noise in quantum systems.
Post-quantum cryptography is an essential area of research and development in the field of cybersecurity. As quantum computing advances, current cryptographic systems face serious threats. Addressing these threats demands developing and adopting new cryptographic algorithms that are resilient against quantum attacks. Through standardization efforts and careful planning, organizations can confidently navigate towards the post-quantum era while maintaining the security and integrity of digital communications.