Cryptography After Quantum Computers

Every time you log in to online banking, pay through a mobile wallet or send a WhatsApp message, number theory quietly protects you. Much of that protection depends on problems, such as factoring large numbers, that are hard for ordinary computers but would be easy for a large quantum computer. This article explains why, and introduces the new mathematics, especially lattices, that cryptographers are deploying to stay safe in the quantum era.

Why Today's Public-Key Cryptography Is at Risk

Public-key systems rely on trapdoor problems: easy to compute in one direction, hard to reverse without secret information.

• RSA relies on the difficulty of factoring \( N = pq \), where \( p \) and \( q \) are large primes.
• Diffie–Hellman and elliptic-curve cryptography (ECC) rely on the discrete logarithm problem: given \( g \) and \( g^x \), find \( x \).

In 1994, Peter Shor showed that a sufficiently large, error-corrected quantum computer could solve both problems in polynomial time. The key idea is that factoring reduces to period finding, and quantum computers find periods efficiently using the quantum Fourier transform.

Worked Example 1: The Number Theory Inside Shor's Algorithm

Let us factor \( N = 15 \) using the same classical reduction that Shor's algorithm uses. The quantum computer's only job is Step 2, finding the period; here we do it by hand.

Step 1: Choose a base. Pick \( a = 7 \). Check \( \gcd(7, 15) = 1 \), so 7 does not already share a factor with 15.

Step 2: Find the order \( r \), the smallest positive integer with \( 7^r \equiv 1 \pmod{15} \).

• \( 7^1 = 7 \equiv 7 \)
• \( 7^2 = 49 \equiv 4 \) (since \( 49 - 45 = 4 \))
• \( 7^3 \equiv 4 \times 7 = 28 \equiv 13 \)
• \( 7^4 \equiv 13 \times 7 = 91 \equiv 1 \) (since \( 91 - 90 = 1 \))

So \( r = 4 \), which is even, as we need.

Step 3: Use the factorisation of a difference of squares. Because \( 7^4 - 1 \equiv 0 \pmod{15} \),

$$ (7^2 - 1)(7^2 + 1) = 48 \times 50 \equiv 0 \pmod{15}. $$

Step 4: Take greatest common divisors.

$$ \gcd(48, 15) = 3, \qquad \gcd(50, 15) = 5. $$

We have recovered \( 15 = 3 \times 5 \). For a 2048-bit RSA modulus, the period \( r \) is astronomically large and no classical method can find it in reasonable time, but a quantum computer with enough high-quality qubits could. That is the threat.

What About Symmetric Encryption?

Block ciphers such as AES are not broken by Shor's algorithm. The relevant quantum attack is Grover's search, which finds a key among \( 2^k \) possibilities in roughly \( 2^{k/2} \) steps. That effectively halves the security level in bits:

• AES-128 drops to about \( 2^{64} \) quantum operations, which is considered uncomfortably low in the long term.
• AES-256 drops to about \( 2^{128} \), which remains very strong.

The practical advice is simple: use longer symmetric keys and longer hash outputs. Public-key cryptography, however, needs entirely new mathematics.

"Harvest Now, Decrypt Later"

Large fault-tolerant quantum computers do not exist yet, so why worry now? Because an attacker can record encrypted traffic today and decrypt it years later. Medical records, state secrets and financial data often need to stay confidential for decades, so the migration must happen well before the quantum computer arrives.

The Post-Quantum Families

Post-quantum cryptography (PQC) means classical algorithms, running on ordinary computers, believed to resist quantum attacks. The main families are:

1. Lattice-based: security from problems such as Learning With Errors (LWE). Fast and versatile.
2. Hash-based signatures: security rests only on the properties of hash functions. Very conservative, but signatures are large.
3. Code-based: derived from error-correcting codes, for example McEliece (1978) and HQC.
4. Multivariate and isogeny-based: active research areas. A prominent isogeny scheme, SIKE, was broken in 2022 by a classical attack, a reminder that new assumptions need years of scrutiny.

In August 2024 the US National Institute of Standards and Technology (NIST) published its first PQC standards: ML-KEM (derived from CRYSTALS-Kyber) for key establishment, ML-DSA (from CRYSTALS-Dilithium) for signatures, and SLH-DSA (from SPHINCS+), a hash-based signature. A Falcon-based signature and the code-based HQC were selected for further standardisation.

Learning With Errors: The Heart of Lattice Cryptography

Solving a linear system \( A\mathbf{s} = \mathbf{b} \) is easy with Gaussian elimination. LWE adds a small random error:

$$ \mathbf{b} = A\mathbf{s} + \mathbf{e} \pmod{q}. $$

Given \( A \) and \( \mathbf{b} \), finding the secret \( \mathbf{s} \) becomes, for well-chosen dimensions, as hard as solving worst-case problems on lattices, such as finding very short vectors. Oded Regev proved this connection in 2005, and no efficient quantum algorithm for it is known.

Worked Example 2: A Toy LWE Encryption

Real schemes use dimensions in the hundreds and combine many samples; this toy version uses one sample in dimension 2 to show the mechanism. Take modulus \( q = 17 \), secret key \( \mathbf{s} = (3, 5) \), public vector \( \mathbf{a} = (2, 7) \) and small error \( e = 1 \).

Step 1: Compute the public value \( b \).

$$ b = \mathbf{a} \cdot \mathbf{s} + e = 2(3) + 7(5) + 1 = 6 + 35 + 1 = 42 \equiv 8 \pmod{17}. $$

Step 2: Encrypt a bit \( m \). The ciphertext is \( (\mathbf{a}, c) \) with \( c = b + m\lfloor q/2 \rfloor \) and \( \lfloor 17/2 \rfloor = 8 \).

• For \( m = 0 \): \( c = 8 \).
• For \( m = 1 \): \( c = 8 + 8 = 16 \).

Step 3: Decrypt using the secret. Compute \( \mathbf{a} \cdot \mathbf{s} = 41 \equiv 7 \pmod{17} \), then \( d = c - 7 \pmod{17} \).

• For \( m = 0 \): \( d = 8 - 7 = 1 \), which is close to 0, so we read 0.
• For \( m = 1 \): \( d = 16 - 7 = 9 \), which is close to 8, so we read 1.

Step 4: Sanity check. The error \( e = 1 \) shifted the result by only one unit, far less than the gap of about \( q/4 \approx 4 \) needed to cause a wrong decryption. Without \( \mathbf{s} \), an attacker sees \( b = 8 \) but cannot separate \( \mathbf{a} \cdot \mathbf{s} \) from the noise. In high dimensions, this noise makes the problem intractable.

Research Frontiers

• Cryptanalysis: estimating exactly how hard lattice problems are, using algorithms such as BKZ lattice reduction.
• Efficient implementation: fast polynomial multiplication with the number-theoretic transform, a modular cousin of the FFT.
• Side-channel resistance: making sure timing or power usage does not leak secrets.
• Crypto-agility and hybrids: combining classical and post-quantum algorithms during migration, as several major browsers and messaging apps have begun to do.
• Advanced tools: fully homomorphic encryption, which lets you compute on encrypted data, is also built on lattices.

Did You Know?

• Shor's algorithm has been demonstrated on tiny numbers like 15 and 21; breaking real RSA would require vastly more error-corrected qubits than any machine today.
• The McEliece code-based system from 1978 has survived over four decades of attacks, but its public keys are very large.
• Lattice problems are studied in pure mathematics too, going back to work on the geometry of numbers by Hermann Minkowski in the 1890s.

Key Takeaways

• Shor's algorithm breaks RSA and ECC by turning factoring and discrete logs into period finding.
• Grover's algorithm only halves symmetric key strength, so AES-256 remains safe.
• Learning With Errors hides a linear system under small noise and underpins ML-KEM and ML-DSA.
• "Harvest now, decrypt later" means migration to post-quantum cryptography must start before quantum computers mature.

Working on a cryptography assignment, number theory problem or thesis on post-quantum security? Amathify's experts and PhD scholars offer step-by-step solutions via WhatsApp or the Ask a Question form.