The most surprising thing about post-quantum cryptography (PQC) is that it doesn’t actually avoid quantum computers; it’s designed to resist them.
Imagine you’re sending a secret message. Traditionally, you use encryption algorithms like RSA or ECC. These rely on mathematical problems that are incredibly hard for classical computers to solve, like factoring large numbers or finding discrete logarithms. But a powerful enough quantum computer, using Shor’s algorithm, could crack these problems in a reasonable amount of time. PQC is about developing new encryption methods that are hard for both classical and quantum computers to break.
Let’s see PQC in action, not with code you’ll run today (it’s still evolving!), but by looking at the types of problems it uses. One leading candidate is based on lattices.
A lattice is essentially a grid of points in space. Think of a 2D grid of equally spaced dots. In PQC, the "hard problem" is often related to finding the shortest vector in a very high-dimensional lattice, or finding a combination of lattice points that sums to a specific target vector (the Shortest Vector Problem or Closest Vector Problem).
Here’s a simplified, conceptual example. Imagine a 2D lattice. You’re given a very large, "noisy" target vector. The secret key is a short, precise vector that, when added to a specific, publicly known lattice basis, results in that target vector. The public key is the noisy target vector and the lattice basis. A classical or quantum attacker would struggle to find that original short secret vector from the public information because the lattice is enormous and the "noise" (which is mathematically related to the difficulty) is significant.
Another promising approach uses hash functions. These are one-way functions that take any input and produce a fixed-size output (a hash). They’re already fundamental to many cryptographic systems. PQC explores using "hash-based signatures," which are built from the ground up using only secure hash functions.
Consider a simple hash-based signature scheme like Lamport signatures. To sign a message, you generate a secret key consisting of many random one-time private values. For each bit of the message’s hash, you reveal one of these private values. The public key is the hash of each of these secret values. To verify, the recipient hashes the revealed private values and checks if they match the public key components corresponding to the message’s hash. The "hard problem" here is that it’s computationally infeasible to forge a signature without knowing the secret keys, and even if you know one secret key, you can’t derive another to sign a different message. The limitation is that each private key can only be used once, making it a "one-time signature." More advanced schemes like Merkle trees build on this to create reusable signatures.
The core problem PQC solves is ensuring the confidentiality and integrity of data in an era where quantum computers could undermine today’s most trusted cryptographic foundations. It’s not about making encryption stronger in the absolute sense, but about making it resistant to a new class of computational attacks.
The exact levers you control in PQC are the choice of algorithm families (lattices, hashes, codes, etc.), the parameters within those algorithms (like lattice dimension or hash output size), and how they are integrated into existing protocols. For instance, a lattice-based encryption scheme might have parameters like CRYSTALS-KYBER which specifies a certain polynomial ring and module rank, directly influencing the security level and performance.
Many people think PQC is just about replacing RSA with a quantum-resistant equivalent, but it’s more nuanced. Different PQC algorithms have vastly different trade-offs. For example, lattice-based schemes often offer good performance but can have larger key sizes than classical algorithms. Hash-based signatures are very well understood and secure but are typically stateful or have large signature sizes. Code-based cryptography, using error-correcting codes, can have very large public keys. The choice depends on the specific application’s constraints.
The next concept you’ll run into is the standardization process and the challenges of migrating existing systems to these new algorithms.