What is Post-Quantum Cryptography?How Does It Work?

If you’ve been following our learning articles at SSLTrust, then you should know how SSL/TLS work and why the encryption they provide forms the backbone of modern web security, protecting sensitive data from being intercepted by malicious actors.

However, as with all cybersecurity technology, the encryption offered by the current generation of SSL certificates is always at risk of becoming outdated as the technology available to attackers evolves.

One of these emerging threats is the rise of quantum computing.

In this article, we’ll explore the strength of current encryption offered by SSL certificates, why quantum computing poses a threat, and how the development of post-quantum cryptography seeks to combat this threat and maintain the integrity of SSL/TLS protection.

The strength of public-key cryptography (and the reason we trust it to secure websites) is based on the fact that the mathematical complexity of public-key encryption makes decryption infeasible for anyone using a traditional computer.

For example, as explored in our article on 256-bit encryption, it would take current computing hardware millions of years to go through every possible key combination to break the encryption.

So, it’s not that the encryption can’t be broken with current hardware; it’s just that brute-forcing would take so long that it wouldn’t be worth attempting.

Basically, quantum computing uses a completely different approach to processing information than traditional computers. Current computer hardware handles data as binary bits (1s and 0s), while quantum computers use quantum bits (more commonly known as qubits).

The underlying mathematics are complex, but put simply, a classical binary bit can only exist as a 1 or 0. In contrast, a qubit can be both a 1 and 0 at the same time, allowing a quantum computer to process multiple calculations simultaneously.

For this reason, quantum computers provide many exciting opportunities for advancement in multiple fields, such as science, medicine, and artificial intelligence.

However, as with any new technology, there is always a dark side. With a sufficiently powerful quantum computer, it’s speculated that an attacker could break 256-bit encryption in a matter of hours (rather than millions of years).

Luckily, cybersecurity researchers are already developing safeguards against the threat posed by quantum computing. Chief among these is post-quantum cryptography.

Post-quantum cryptography (PQC) refers to a new set of encryption algorithms that are designed to withstand brute-force attacks from quantum computers.

However, it’s important to understand the distinction between quantum cryptography and post-quantum cryptography, as many people confuse the two.

Quantum cryptography uses quantum mechanics to create secure channels such as Quantum Key Distribution (QKD). This means that the security is being provided by leveraging the laws of physics. So, you are literally transmitting quantum particles like photons to generate the encryption keys, which are physically impossible to copy or duplicate.

While this method of encryption is incredibly strong, it also requires quantum hardware to implement. This is not practical for everyday website encryption, as it would be too costly to provide this technology to secure the millions of websites that rely on SSL/TLS security today.

This is where post-quantum cryptography steps in.

Post-quantum cryptography uses classical computing techniques that are specifically designed to resist quantum computing attacks. Since it does not rely on leveraging quantum mechanics, PQC is far more accessible and can be incorporated into SSL/TLS certificates without upgrading to quantum technology.

In our guide to TLS, we explained how modern SSL/TLS certificates use a combination of symmetric and asymmetric encryption to establish a secured connection. One of the encryption algorithms we mentioned was Rivest-Shamir-Adleman (RSA). Other key algorithms include Elliptic Curve Cryptography (ECC) and Diffie-Hellman Key Exchange (DHKE).

As mentioned, these algorithms are based on complex mathematical problems that would take a classical computer millions of years to decrypt, which is why we rely on them in SSL/TLS certificates.

Quantum computers threaten these algorithms due to Shor’s Algorithm. Developed by mathematician Peter Shor in 1994, this algorithm (when combined with the computational power of quantum computers) can efficiently factor large numbers and resolve the complex algebraic problems (such as discrete logarithms) that RSA, ECC and DHKE rely on.

So, post-quantum cryptography is all about developing new mathematical problems or other solutions that are difficult for both classical and quantum computers to solve.

Some of the most promising new methods include:

Lattice-based cryptography is based on the difficulty of lattice problems. A lattice is a grid-like mathematical structure that has points arranged in different dimensions.

Lattice-based encryptions work by:

Why is it difficult for quantum computers to break?

Lattice-based cryptography is difficult for quantum computers to break due to two things: the Shortest Vector Problem (SVP) and Learning With Errors (LWE).

Shortest Vector Problem (SVP): You can think of SVP as trying to find the quickest path through a complex maze where there are millions of possible routes. The lattice structure forms this type of maze. Even with a quantum computer, it would take an incredibly large amount of calculations to find the shortest route through the maze, making brute-force attacks pointless.

Learning With Errors (LWE): LWE relies on adding random errors (noise) to encoded messages.

For example, solving an algebraic problem like X + Y = 10 is easy.

With LWE, this equation might look like X + Y ≈ 10.0047.

Without knowing how the error was introduced (the secret key), it would be incredibly hard to find the exact values of X and Y.

Even a quantum computer would have trouble removing this noise efficiently. This, again, would make brute-force attacks impractical.

Lattice-based cryptography is already a frontrunner in post-quantum cryptography and has been used to develop the CRYSTALS-Kyber and CRYSTALS-Dilithium algorithms. These new algorithms have officially become standardised by the National Institute of Standards and Technology (NIST) in the US for post-quantum cryptography.

Hash-based cryptography secures information with cryptographic hash functions instead of complex mathematical problems.

The hash function converts information into a unique, fixed-length string of characters. This string of characters is deterministic and irreversible. No matter how many times you hash the same information, the output will be the same, and it’s impossible to reverse this process to uncover the information.

The process is simple:

Because the hash is deterministic, even a tiny change in the original information would produce a different hash, making any tampering immediately detectable. This is why hash-based cryptography is already used for code-signing certificates and email-signing (S/MIME) certificates, as well as in digital signatures used to verify the Certificate Authority (CA) in SSL certificates.

While hash-based cryptography is already widely used to verify digital signatures, it isn’t used as the primary method of encryption (which still relies on RSA, ECC, etc.) Post-quantum cryptography is now exploring the use of hash functions as the primary encryption method because they still remain difficult for quantum computers to break.

Why?

Because hash functions do not rely on difficult math problems like RSA and ECC, the extra computational power of quantum computers does not pose the same threat. A hash function is a one-way transformation of information, so a quantum computer can’t efficiently reverse them no matter how powerful it is.

SPHINCS+ (Stateless Practical Hash-based INdirected Signature Scheme) is an example of a post-quantum cryptography solution leveraging hash-based cryptography.

Multivariate polynomial cryptography (MPKC) relies on the complexity of attempting to solve many nonlinear equations at once.

For example, a standard algebraic equation might look like:

A polynomial equation might look like:

The x² term makes this a nonlinear equation because the variable is squared.

Now, imagine a huge set of equations that looked like this:

Looks a lot more complex to solve, right? In this equation, solving X and Y is much more complicated because of the nonlinear ways the variables interact, making it harder to isolate them.

Multivariate polynomial cryptography uses a system of equations like this to encrypt and decrypt messages:

Just like with the other post-quantum cryptographic algorithms we have covered, decoding the message all depends on having the private key. Without it, it would be infeasible even for a quantum computer to brute-force its way through these exponentially more difficult equations.

The most well-known example of a post-quantum solution leveraging multivariate polynomial cryptography was Rainbow. Rainbow was lauded for being very fast and resource-efficient compared to other post-quantum solutions.

Unfortunately, in 2022, Rainbow was broken by a white-hat attack that revealed hidden weaknesses in the mathematical key structure. Despite this, researchers are still exploring multivariate polynomial cryptography as a viable post-quantum solution.

At this stage, there’s no denying that quantum computers will eventually make existing encryption standards ineffective. With tech companies and governments (including Australia) investing heavily in quantum computing, it’s estimated that the quantum threat could materialise in the next 10 to 20 years or even sooner.

While the quantum technology required to break current encryption is not yet available to attackers, that does not mean they are sitting idle. Many attackers are actively collecting encrypted data based on the idea of “Harvest Now, Decrypt Later”, which involves collecting as much data as possible in preparation for when decrypting it with quantum computers becomes feasible.

So, the cybersecurity world is racing against time to deploy practical post-quantum solutions. A leader in this space is the aforementioned NIST, which is actively engaged in standardising post-quantum cryptography solutions through rigorous testing and evaluation.

Quantum computing presents some amazing opportunities but is also a serious threat to online security. It’s no longer a question of if SSL/TLS encryption will be broken by quantum computing but a question of when.

Thankfully, forward-thinkers have already made significant progress in developing practical post-quantum cryptographic solutions. We will have to wait and see if these solutions can be deployed in time to ensure the continued security and integrity of digital communication.