What is Post-Quantum Cryptography (PQC)?

What is PQC?

Post-quantum cryptography (PQC) refers to a set of classical cryptographic algorithms that are believed to be “quantum-safe,” meaning that they are expected to remain safe even in the presence of quantum computers.

Recap: Why do we need quantum-safe cryptography?

Many of the applications running on the Internet today are protected by a set of protocols collectively known as “public key cryptography.” Examples of such protocols include RSA, RSA-EC, DSA, DH, and DHEC.

The security of these protocols relies on the assumption that it would take even the most powerful classical computers thousands of years to solve certain mathematical problems (e.g. factoring large numbers or computing a discrete logarithm).

However, we now know that quantum computers could break most of the encryption protocols used today, leaving internet data unprotected.

How does PQC work?

The idea behind post-quantum cryptography (PQC) is to change the underlying mathematical problems. We know that factorization and discrete logarithms will be easy for future quantum computers to solve because of Shor's algorithm, which renders existing algorithms such as RSA, DSA, DH, and ECDH unsafe. So, PQC uses different mathematical problems that are believed (but not proven) to be difficult for both classical and quantum computers alike.

PQC itself is a purely classical technology: there are not quantum networks or quantum states involved in the implementation of PQC. The term post-quantum in PQC refers to the goal of offering a security mechanism that cannot be broken by quantum computers.

Status of PQC development: NIST standards

The USA National Institute of Standards and Technology (NIST) is leading the charge in developing standards around PQC algorithms. NIST began this process in 2016 and in 2020, announced a list of 7 finalists as well as 8 alternatives. The process takes time, as these new candidates must be evaluated both in terms of theoretical security and in terms of performance in real-world conditions. NIST plans to announce a final list of protocols in 2022-2024.

Conclusion: Where does PQC fit?

The biggest advantages of PQC are that it is a relatively incremental evolution of existing security protocols and that it can run over the existing Internet infrastructure: it does not require any quantum network to be deployed. Other advantages include simplicity and the fact that it does both encryption and authentication.

The biggest disadvantage of PQC is that, while the new mathematical algorithms have been scrutinized and are widely believed to be safe from attack by quantum computers, this has not been mathematically proven. As a reminder: the science community was shocked that factorization turned out to be easy for quantum computers to solve due to Shor's algorithm. Thus, PQC critics like to point out that PQC is only a temporary solution.

For many applications, PQC is likely to replace today’s cryptographic protocols. For applications with long-term security requirements or those with especially sensitive data, researchers have turned to other methods, such as quantum key distribution (QKD), which does not rely on mathematical assumptions.

To keep up with the latest in the development of PQC and other quantum-safe security solutions, subscribe to the Quantum Connect newsletter in the footer of this page.