What is post-quantum cryptography and should we care?

Post-quantum cryptography has been a buzzword for a while now. What is it and how will it affect encryption security?

Since the 1980s, scientists have speculated that by using quantum mechanics, it might be possible to build quantum computers that could more quickly perform certain calculations that would take enormous amounts of time on an ordinary computer. In 1994, mathematician Peter Shor discovered that if you had such a quantum computer, you could use it to factor large numbers and break the security of RSA, the algorithm that forms the basis of the most widely used public key encryption system.

It quickly became clear that quantum computers, if they existed, would not only break RSA, but they would also break every other public key encryption, signature and key exchange algorithm in systems like the Transport Layer Security protocol, SSH or Pretty Good Privacy.

Today, cryptographers are looking for new algorithms, and these are called post-quantum cryptography.

While cryptographers think there are algorithms that are safe from quantum computer attacks, they aren't always simple replacements for existing algorithms. Some of these algorithms are very slow, while others require very large keys or signature sizes. Some of these schemes are based on very new ideas, so cryptographers don't recommend using them until a lot more analysis has been done about their security.

The NIST is currently running a project to "solicit, evaluate, and standardize one or more quantum-resistant public-key cryptographic algorithms," which will become a part of future post-quantum cryptography standards, but those are not coming any time soon. According to NIST's plans, draft standards are expected to be available between 2022 and 2024.

Nobody knows when or even if practical quantum computers will ever be built. Experts' estimates range from five to 10 years, to "not in the foreseeable future." For security engineers, this uncertainty is a challenge because if quantum computers ever are practical, they will also threaten today's encrypted communication. A patient attacker -- such as government monitoring adversaries or an advanced persistent threat monitoring potential targets -- could store encrypted data today to decrypt later.

This is why some companies are already experimenting with promising post-quantum algorithms. Google launched experiments where they couple an existing elliptic curve algorithm with a future post-quantum algorithm. The idea is that even if the post-quantum algorithm turns out to be insecure, users will still have the security of the elliptic curve algorithm. That is not quantum safe, but it provides good protection against attacks without a quantum computer.