You might be familiar with the concept of classical cryptography, which is the type of encryption we use every day. You may even have heard of quantum cryptography which makes use of quantum computers and quantum mechanical effects. While both of these are important technologies in their own right, classical cryptography underpins almost the entirety of modern communications technology, post-quantum cryptography is a really critical step that isn’t that widely known. Post-quantum cryptography isn’t supposed to be the next biggest thing after quantum encryption. Instead, it’s the class of cryptography that is still relevant in a world where powerful quantum computers exist.
The quantum speedup
Classical cryptography is basically all based on a small number of different math problems. These problems have been carefully chosen because they are extremely difficult unless you know specific information. Even with computers, these math problems are provably difficult. In 2019 a study spent 900 CPU core years to break a 795-bit RSA key. A 1024-bit RSA key would take more than 500 times more processing power to break. Additionally, 1024-bit RSA keys have been deprecated in favour of 2048-bit RSA which would be practically impossible to break.
The problem is that quantum computers work in a completely different way compared to normal computers. This means that certain things that are difficult for normal computers to do are much easier for quantum computers to do. Unfortunately, many of the math problems used in cryptography are perfect examples of this. All asymmetric encryption in modern use is vulnerable to this quantum speed-up, assuming access to a sufficiently powerful quantum computer.
Traditionally, if you want to increase the security of encryption, you just need longer keys. This does assume that there are no more fundamental issues with the algorithm and that it can be scaled up to use longer keys, but the principle holds. For each extra bit of security, the difficulty doubles, this means going from 1024-bit to 2048-bit encryption is a huge difficulty spike. This exponential difficulty growth, however, doesn’t apply to these problems when run on quantum computers where the difficulty increases logarithmically not exponentially. This means you can’t simply double the key length and be fine for the next decade of computing power increase. The whole game is up and a new system is needed.
A ray of hope
Interestingly, all modern symmetric encryption algorithms are also affected but to a much lesser degree. The effective security of an asymmetric cipher like RSA is decreased by the square root. A 2048-bit RSA key offers the equivalent of 45 or so bits of security against a quantum computer. For symmetric algorithms like AES, the effective security is “only” halved. 128-bit AES is considered secure against a normal computer, but the effective security against a quantum computer is just 64 bits. This is weak enough to be considered insecure. The problem can be solved, however, by doubling the key size to 256 bits. A 256-bit AES key offers 128-bits of protection even against a sufficiently powerful quantum computer. That is enough to be considered secure. Even better, 256-bit AES is already publicly available and in use.
Tip: The bits of security offered by symmetric and asymmetric encryption algorithms are not directly comparable.
The whole “sufficiently powerful quantum computer” thing is a bit hard to define precisely. It means that a quantum computer needs to be able to store enough qubits to be able to track all the states needed to break the encryption key. The key fact is that no one has the technology to do this yet. The problem is we don’t know when someone will develop that technology. It could be five years, ten years, or more.
Given that there’s at least one type of math problem suitable for cryptography that isn’t particularly vulnerable to quantum computers, it’s safe to assume that there are others. There are actually many proposed encryption schemes that are safe to use even in the face of quantum computers. The challenge is to standardise these post-quantum encryption schemes and prove their security.
Conclusion
Post-quantum cryptography refers to cryptography that remains strong even in the face of powerful quantum computers. Quantum computers are able to thoroughly break some types of encryption. They can do so far faster than normal computers can, thanks to Shor’s algorithm. The speed-up is so great that there is no way to practically counter it. As such, an effort is underway to identify potential cryptographic schemes that aren’t vulnerable to this exponential speed-up and so can stand up to quantum computers.
If someone with a future quantum computer has a lot of old historical data that they can easily crack, they can still do great damage. With the high cost and technical skills needed to build, maintain, and use a quantum computer there’s little chance of them being used by criminals. Governments, and ethically ambiguous mega-corporations, however, have the resources and may not use them for the greater good. Even though these powerful quantum computers may not exist yet, it’s important to transfer over to post-quantum cryptography as soon as it is shown to be secure to do so to prevent widespread historical decryption.
Many post-quantum cryptography candidates are essentially ready to go. The problem is that proving that they are secure was already hellishly difficult when you didn’t have to allow for mind-bendingly complicated quantum computers. A lot of research is ongoing to identify the best options for widespread use. A key thing to understand is that post-quantum cryptography runs on a normal computer. This differentiates it from quantum cryptography which needs to run on a quantum computer.
