What Is Post-Quantum Cryptography (PQC)?

Post-quantum cryptography: Algorithms and foundations

PQC involves developing new algorithms based on different mathematical foundations that are believed to be hard for both classical and quantum computers to solve.

The U.S. National Institute of Standards and Technology (NIST) is a main driving force behind the adoption of PQC algorithms, and has focused on standardizing algorithms from several mathematical families. After a multi-year process and a number of rounds of elimination (that included the breaking of the isogeny-based SIKE algorithm), NIST is currently pushing for the adoption of the following types of algorithms:

• Lattice-based cryptography. This approach derives its security from the presumed difficulty of certain complex tasks within high-dimensional geometric structures called lattices.
• Hash-based cryptography. These methods rely on the one-way nature of hash functions. They are considered quantum-resistant because reversing a hash operation is computationally difficult.
• Code-based cryptography. This type of cryptography relies on error-correcting codes. The Classic McEliece encryption algorithm is a well-known example.

Why quantum computers are a threat to current encryption methods

Quantum computers pose a significant threat to current data encryption methods due to their ability to perform calculations far exceeding classical capabilities. This threat is primarily realized through specific quantum algorithms designed to break the mathematical problems that underpin modern cryptography. Both symmetric and asymmetric cryptography are at risk to varying degrees.

Breaking asymmetric cryptography with Shor's Algorithm

Many widely used asymmetric cryptographic algorithms, such as RSA and Elliptic Curve Cryptography (ECC), rely on the computational difficulty of problems like integer factorization or the discrete logarithm problem. For classical computers, solving these problems within a reasonable timeframe is considered too difficult, forming the foundation of digital security.

Shor's Algorithm, developed by mathematician Peter Shor in 1994, fundamentally changes this landscape. It allows a sufficiently powerful quantum computer to efficiently solve these specific mathematical problems, effectively breaking the security of RSA, ECC, and Diffie-Hellman in a post-quantum world. This means that data encrypted with these methods could become vulnerable to decryption.

For example, a conventional computer might take billions of years to factor large numbers, but a capable quantum computer could solve the same puzzle in days or hours.

Weakening symmetric cryptography with Grover's Algorithm

Symmetric algorithms, such as the Advanced Encryption Standard (AES), are also at risk, primarily from Grover's Algorithm.

While Shor's Algorithm targets specific mathematical problems, Grover's Algorithm is a generic quantum search algorithm. It offers a significant quadratic speedup in searching through unsorted lists, like possible encryption keys. For a key with “n” bits, Grover's Algorithm can reduce the search effort to approximately 2^(n/2) quantum operations, effectively halving the strength of the symmetric key.

For instance, AES-128 security would be reduced to 64-bit strength, making it ineffective against quantum adversaries in the long term. Doubling the key size, such as moving from 128-bit to 256-bit keys, can mitigate this risk for symmetric algorithms. This is the current recommended approach to offer initial resistance to quantum threats.

The threat of "Q-Day" and "harvest now, decrypt later" attacks

The term "Q-Day" refers to the future point in time when a quantum computer could break today's standard encryption. While the exact timing is unknown and could be a few years or a decade away, the risk to sensitive data is present now.

Adversaries are already engaging in "harvest now, decrypt later" (HNDL) attacks. This involves collecting currently encrypted sensitive data—such as customer personally identifiable information (PII), financial records, or intellectual property—to decrypt it once sufficiently powerful quantum computers emerge. According to a recent study, 65% of organizations surveyed on the risks of quantum computing are concerned about HNDL attacks.

This strategy is particularly concerning for information that retains its value for decades, such as national security secrets, permanent personal identifiers, or foundational intellectual property.

The development of cryptographically relevant quantum computers

The threats become concrete with the development of a "cryptographically relevant quantum computer" (CRQC), which would possess the processing power necessary to break current encryption. Although such hardware does not currently exist, quantum developers are actively working towards it, treating its arrival as an inevitability.

Such computers would employ many thousands of qubits, the basic unit of quantum computing, analogous to bits in classical computing. Qubits are currently fragile and subject to errors, but the potential for future breaches of currently secure data makes the urgent move to PQC a necessity.

How to transition to post-quantum cryptography

Organizations should start with a hybrid approach, using stronger encryption as soon as possible to protect against the threat of  "harvest now, decrypt later" attacks. They should transition to a fully agile solution over time to minimize disruption, manage risk, and test new algorithms. Trellix Data Encryption professional services experts can help customers identify critical data, assess dependencies, and integrate PQC solutions, offering crypto-agile solutions and guidance.

Trellix aims to phase out quantum-vulnerable legacy asymmetric cryptography in its solutions as PQC standards mature and are tested. Symmetric encryption (e.g., AES-256) will remain fundamental.

Our goal is for our company—and our customers—to achieve a fully quantum-resistant security posture.