Skip to main content
Be Bitwise

Quantum Computing & Security

Quantum Computing Fundamentals · Frontiers track

6 min read

In this module

The Quantum Threat to Cryptography

The cryptography modules, from Symmetric Encryption to Cryptographic Protocols, walked through how modern cryptography underpins nearly every corner of digital security: HTTPS, digital signatures, secure messaging, cryptocurrency, the lot. Most of that security leans on mathematical problems that classical computers can't solve in any reasonable time. Quantum computing threatens to kick that foundation out.

The only open question is timing. Governments and organisations worldwide are already moving on it, and the cryptographic community has spent over a decade quietly building quantum-resistant alternatives.

What Quantum Computers Can Break

RSA and Integer Factoring

RSA encryption hinges on the difficulty of factoring large semiprimes (products of two large primes). As we saw last lesson, Shor's algorithm factors integers in polynomial time. Give it a powerful enough quantum computer and RSA falls at any key length.

Current estimates put breaking a 2048-bit RSA key at roughly 4,000 logical qubits with full error correction, which works out to millions of physical qubits at today's error rates. Nobody's there yet, but the trajectory is steady and unmistakable.

Elliptic Curve Cryptography (ECC)

ECC leans on the elliptic curve discrete logarithm problem. A variant of Shor's algorithm cracks that one efficiently too. Counterintuitively, ECC is actually more exposed than RSA in the quantum era — because ECC keys are shorter, the quantum computer needs fewer qubits to break them.

Diffie-Hellman Key Exchange

The Diffie-Hellman protocol lets two parties agree on a shared secret over an insecure channel by leaning on the discrete logarithm problem. Shor's algorithm breaks that too.

Harvest Now, Decrypt Later

Even though large-scale quantum computers do not exist yet, adversaries can record encrypted communications today and decrypt them later when quantum computers become available. This "harvest now, decrypt later" strategy means that information with long-term sensitivity - diplomatic communications, trade secrets, medical records - is at risk right now. This is why the transition to post-quantum cryptography is urgent, even though the quantum threat is not yet realised.

What Quantum Computers Cannot Break

Not all cryptography is vulnerable to quantum attacks:

Symmetric Encryption (AES)

Grover's algorithm gives a quadratic speedup on searching, which in cryptographic terms effectively halves the security of a symmetric key. AES-128 drops to 64-bit security against a quantum attacker, which isn't enough. AES-256 holds at 128-bit security, which is comfortably safe. The remedy is mercifully simple: double the key length.

Hash Functions

Quantum computers do speed up hash collision finding — O(2^(N/2)) drops to O(2^(N/3)) via the BHT algorithm — but the gain is modest. SHA-256 and SHA-3 hold up against quantum attacks at their current output sizes.

Algorithm TypeClassical SecurityQuantum SecurityFix
RSA-2048~112 bitsBroken (Shor's)Replace with PQC
ECC P-256~128 bitsBroken (Shor's)Replace with PQC
AES-128128 bits64 bits (Grover's)Use AES-256
AES-256256 bits128 bits (Grover's)Already sufficient
SHA-256128 bits (collision)~85 bitsAlready sufficient

Post-Quantum Cryptography

Post-quantum cryptography (PQC) is the umbrella term for cryptographic algorithms believed to be secure against both classical and quantum attacks. They run on classical computers; no quantum hardware required. The goal is to retire vulnerable algorithms (RSA, ECC, Diffie-Hellman) and swap in quantum-resistant alternatives before large-scale quantum computers actually turn up.

NIST Standardisation

The U.S. National Institute of Standards and Technology (NIST) began a standardisation process in 2016 to select post-quantum cryptographic algorithms. After multiple rounds of evaluation, NIST announced its first selections in 2022:

For Key Encapsulation (replacing RSA/Diffie-Hellman for key exchange):

  • ML-KEM (CRYSTALS-Kyber) - based on the Module Learning with Errors (MLWE) problem. Selected as the primary standard due to its relatively small key sizes and fast operations.

For Digital Signatures (replacing RSA/ECDSA for signing):

  • ML-DSA (CRYSTALS-Dilithium) - also lattice-based, selected as the primary signature standard.
  • SLH-DSA (SPHINCS+) - hash-based signatures, selected as a backup in case lattice-based schemes are broken.

Types of Post-Quantum Cryptography

Several mathematical foundations underpin PQC, each with their own quirks:

Lattice-based cryptography — leans on the hardness of problems in high-dimensional lattices, such as finding the shortest vector or solving the Learning with Errors (LWE) problem. The most versatile approach in the family, and the basis for NIST's primary selections. Lattice problems have been studied for decades and look hard for both classical and quantum computers.

Hash-based signatures — build digital signatures purely out of hash functions, whose security properties are well-understood. The Merkle signature scheme goes all the way back to 1979. Conservative, exhaustively analysed, but burdened with larger signatures, and they're stateful (each key can sign only a fixed number of messages) unless you use stateless variants like SPHINCS+.

Code-based cryptography — built on the difficulty of decoding random linear codes. The McEliece cryptosystem (1978) has shrugged off decades of cryptanalysis. The catch is enormous key sizes.

Multivariate polynomial cryptography — built on the difficulty of solving systems of multivariate polynomial equations. Efficient for signatures, though several proposed schemes have been broken outright.

Isogeny-based cryptography — built on finding paths between elliptic curves. SIKE looked promising and was then promptly demolished by a classical attack in 2022, a sharp reminder that PQC is still very much a live research area.

Defence in Depth

The breaking of SIKE illustrates why the cryptographic community advocates for algorithm agility - the ability to swap out cryptographic algorithms without redesigning entire systems. No one can guarantee that today's PQC algorithms will remain secure forever. Building systems that can quickly adopt new algorithms is as important as choosing the right algorithm today.

Quantum Key Distribution (QKD)

A wildly different angle on quantum-safe communication is Quantum Key Distribution (QKD). Rather than leaning on mathematical hardness assumptions, QKD pins its security on the laws of physics themselves.

The best-known QKD protocol is BB84 (Bennett and Brassard, 1984):

  1. Alice sends qubits to Bob, randomly encoding each in one of two bases (rectilinear or diagonal)
  2. Bob measures each qubit in a randomly chosen basis
  3. They publicly compare which bases they used (but not the results)
  4. They keep only the results where they happened to use the same basis
  5. They check a subset of their shared bits for errors - any eavesdropping would introduce detectable errors due to the no-cloning theorem

QKD's security comes courtesy of quantum mechanics itself: any attempt to measure a qubit disturbs it in a detectable way. The practical baggage is real, though. You need dedicated quantum communication channels (usually fibre), range tops out at a few hundred kilometres without quantum repeaters, and the deployment costs are eye-watering.

The Transition Timeline

Migrating to post-quantum cryptography is a generational undertaking. Every protocol, library, and device that touches RSA, ECC, or Diffie-Hellman has to be updated. The rough shape of the timeline:

  • Now through 2030 — hybrid approaches: using both classical and post-quantum algorithms in parallel, so security holds up even if one of them gets broken.
  • 2030s — widespread adoption of PQC standards, with quantum-vulnerable algorithms deprecated and removed.
  • 2030s-2040s — the era when large-scale quantum computers may finally be capable of breaking today's classical cryptography.

Anyone handling data with long-term sensitivity should already be migrating. The security modules (14-20) in this course cover the classical cryptographic foundations; getting those down is what makes both the risk and the post-quantum alternatives actually make sense.