Post-Quantum Cryptography
What is Post-Quantum Cryptography
After it was theorized that quantum computers could provide computational speed advantages over classical computers, researchers began discovering quantum algorithms that could be used to demonstrate such advantages. One of the earliest such algorithms, and the one that instantly drew attention to the nascent field, is called Shor’s Algorithm. Named after mathematician Peter Shor, this algorithm can efficiently factorize integers. Factorization can be thought of as reverse multiplication, starting with the product and then determining the integers that were multiplied together to get it. There are other use cases for quantum computing besides factorization, as noted in “Understanding the Potential of Commercial Quantum Computers,” but factorization could arguably be the most potentially disruptive.
While integer factorization may not initially seem like a big deal, it turns out to be very hard to do with classical computers. As the numbers get larger and larger, in fact, it becomes essentially impossible to do. And because there is no known way to efficiently factorize large numbers with classical computers, some of the most heavily-used encryption schemes that protect our data and communications are dependent upon this principle. The discovery of Shor’s Algorithm, therefore, exposed a vulnerability in these cryptosystems that wasn’t previously thought to exist. If Shor’s Algorithm could be run today, all of that presumably-secure data and communications could potentially be decrypted and exposed.
At the time of this discovery, the world had zero quantum computers. Even today, the quantum computers in existence are too small and too error-prone to run Shor’s Algorithm. But at some point, someone asked what the world would do after a large enough fault-tolerant quantum computer could be built – a milestone known as either Y2Q or Q-Day – to finally run the algorithm. Because the concern is for after such quantum computers exist, one potential solution to this problem became known as post-quantum cryptography, or PQC, even though the term might sound strange being implemented today. The post quantum cryptography purpose, however, is to protect data and communication from the future quantum threat.
It's important to note that not all cryptographic schemes are vulnerable to Shor’s Algorithm. Some cryptosystems are vulnerable to Grover’s Algorithm, but there’s a relatively-easy defense for that one: increasing the size of the keys. Other cryptosystems are thought to be quantum-safe already. Unfortunately, some of the most critical protocols are the vulnerable ones.
For more information, TechTarget’s definition of “post-quantum cryptography” is a fairly in-depth article considering it’s classified as a glossary term. Educative’s article “What is post-quantum cryptography?,” on the other hand, has a simple definition, and it also provides definitions for the four types of post quantum cryptography algorithms.
What is Post-Quantum Cryptography
Post Quantum Cryptography is also referred to as “quantum-proof,” “quantum-safe,” and “quantum-resistant” cryptography. PQC refers to classical algorithms, often public-key algorithms, that are resistant to decryption by Shor’s Algorithm.
PQC is not the only potential solution to this threat, though. Quantum Key Distribution (QKD) can be thought of as a type of quantum cryptography, a post quantum encryption scheme that leverages quantum mechanics to defend against quantum computers.
Both PQC and QKD are in development around the world, and even in various stages of deployment.
How Does Post-Quantum Cryptography Work
Asking how does post-quantum cryptography work can lead to very technical answers. However, a high-level summary can be limited to:
- There are two main types of encryption, the process that secures data by making it unreadable: symmetric and asymmetric (“public key”).
- Some protocols rely on mathematical problems, such as integer factorization or discrete logarithms, that are hard for classical computers to solve.
- Quantum computers running Shor’s Algorithm can potentially solve these problems, which would reveal the private keys needed to decrypt encrypted messages.
- PQC considers lattice-based, code-based, multivariate polynomial, hash-based, isogeny-based, supersingular isogeny key exchange, and other cryptographic approaches that are secure against both quantum and classical attacks.
The United States National Institute of Standards and Technology (NIST) is leading an initiative to standardize PQC algorithms. The vetting process includes ample opportunity for proposed algorithms to be broken, which is important to know before any of these protocols are officially adopted and put into widespread deployment.
Key Features of Post-Quantum Cryptography
Some of the approaches that are being considered for PQC, in no particular order, include:
- Lattice-Based Cryptography, which uses lattice-related mathematical problems
- Hash-Based Cryptography, which scrambles variable-length data as fixed-length values
- Code-Based Cryptography, which uses random linear codes
- Multivariate Polynomial Cryptography, which uses multivariate polynomials
- Isogeny-Based Cryptography, which uses mappings between elliptic curves
The objective is to provide security against both quantum and classical attacks. One approach is to layer multiple features, instead of just relying on one approach to be doubly secure. A second layer can be thought of as a fail-safe in the event one algorithm becomes compromised.
The Necessity of Post-Quantum Cryptography
In a digital age characterized by the constant transmission of sensitive information, protecting this information is absolutely vital. With quantum computers poised to compromise some of the world’s major cryptosystems, PQC offers hope of protecting today’s information against future quantum attack, a scenario referred to as “harvest now, decrypt later.”
- Recent advancements in logical qubits and fault-tolerant quantum computing (FTQC) have brought Y2Q closer than may have been thought just a year ago.
- A large enough quantum computer could decrypt RSA and other cryptosystems in as little as a few hours
- Technological and algorithmic advancements can happen at any time, making Y2Q closer than current projections
One advantage that PQC has over QKD is that PQC can be implemented now. This doesn’t guarantee that the chosen algorithms won’t be broken, but QKD isn’t in widespread deployment. And while Shor’s-capable quantum computers don’t yet exist, the “harvest now, decrypt later” problem is real. Data that can’t be protected with QKD now can be stored by malicious parties until such time as it can be decrypted with powerful enough quantum computers in the future. Data protected with PQC, however, can also be stored by malicious parties, but will hopefully be of no value to these malicious parties no matter how powerful quantum computers get.