Post-Quantum Cryptography

Introduction: What is Post-Quantum Cryptography?

Current widely used asymmetric cryptography relies on the assumption that one-way functions exist—problems that are easy to compute in one direction but infeasible to reverse. Examples include integer factorization and the discrete logarithm. On classical computers, both problems can only be solved in exponential time, making them practically infeasible for sufficiently large inputs. The fastest known algorithm for factoring large integers is the General Number Field Sieve (GNFS) with runtime $\mathcal{O}\!\left(e^{\log(N)^{\frac{1}{3}}\cdot\log(\log(N))^{\frac{2}{3}}}\right)$.

In 1997, Peter Shor introduced an algorithm that can solve the factorization problem in polynomial time, provided a sufficiently powerful quantum computer is available. The number of required qubits depends on computation time and error rates. Estimates suggest that breaking RSA-2048 would require around $10^{7}$ qubits in 100 days or $10^{9}$ qubits in one hour. Although IBM has demonstrated a quantum computer with 6100 qubits, current systems are still far from the scale needed to break modern cryptographic schemes.

Quantum computers operate fundamentally differently from classical machines, enabling new types of algorithms. If large-scale quantum computers become practical, they could efficiently solve factorization and discrete logarithms, rendering current asymmetric cryptographic systems insecure.

Another important quantum algorithm, developed by Lov Grover, provides a quadratic speedup for searching unsorted data (O(√N) instead of O(N)). This affects symmetric cryptography by effectively reducing its security strength, meaning that key sizes must be doubled to maintain the same level of security against quantum attacks.

Why Post-Quantum Security Matters — Now

Physicists and quantum computing researchers broadly agree: within the next 10 to 15 years, a quantum computer with enough qubits will exist to break widely deployed schemes such as RSA and ECDSA. That timeline makes the threat concrete and near-term, not theoretical.

This gives rise to the "Harvest now – decrypt later" attack strategy. Adversaries are already capturing encrypted data in transit today, storing it cheaply, and waiting until quantum hardware is powerful enough to decrypt it retrospectively. For financial data—invoices, audit trails, tax records subject to retention periods of 10 years or more—the risk is immediate: data you encrypt today must still be confidential a decade from now.

Quantum Computing

Classical computers store and process information using bits — the fundamental unit of classical information. A bit is always in exactly one of two states: 0 or 1. Every calculation, from adding numbers to rendering graphics, reduces to sequences of such binary operations.

A quantum computer replaces bits with qubits (quantum bits). Unlike a classical bit, a qubit can exist in a superposition of both 0 and 1 simultaneously — not as an unknown value, but as a genuine combination of both at once, characterised by complex-valued amplitudes. Only when a qubit is measured does it collapse to a definite 0 or 1, with probabilities determined by the amplitudes.

This property of superposition — together with entanglement (correlations between qubits that have no classical counterpart) and interference (the ability to amplify correct computation paths and cancel wrong ones) — is what gives quantum computers their potential to solve certain problems exponentially faster than any classical machine.

Computing with Single Qubits

In quantum computing, states are typically written in the form |x⟩, known as Dirac notation or ket notation, named after the British physicist and Nobel laureate Paul Dirac.

When the superposition of a qubit is destroyed by measurement, it collapses to either |0⟩ or |1⟩. Which value it takes is governed by the amplitudes: with probability |α|² the qubit adopts state |0⟩, and with probability |β|² it adopts state |1⟩.

Unlike a coin toss—which is theoretically predictable given all parameters—there is no known way to predict the outcome of measuring a qubit. There are, however, deterministic special cases: the state 0⋅|0⟩ + 1⋅|1⟩ behaves like a classical bit set to 1, and 1⋅|0⟩ + 0⋅|1⟩ behaves like a classical bit set to 0.

To exploit superposition for computation, a state vector is transformed by multiplying it with a computation matrix—without performing a measurement, so superposition is preserved.

A fundamental example is the Hadamard gate H, named after the French mathematician Jacques Hadamard. It implements a 1-qubit random number generator:

$$H = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$$

Applied to |1⟩:

$$\begin{pmatrix} \alpha' \\ \beta' \end{pmatrix} = H \cdot \begin{pmatrix} 0 \\ 1 \end{pmatrix} = \begin{pmatrix} \tfrac{1}{\sqrt{2}} \\ -\tfrac{1}{\sqrt{2}} \end{pmatrix}$$

Applied to |0⟩:

$$\begin{pmatrix} \alpha' \\ \beta' \end{pmatrix} = H \cdot \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} \tfrac{1}{\sqrt{2}} \\ \tfrac{1}{\sqrt{2}} \end{pmatrix}$$

In both cases the output probabilities are equal:

$$|\alpha'|^2 = |\beta'|^2 = \tfrac{1}{2}$$

After measurement the qubit therefore takes each of |0⟩ and |1⟩ with probability ½.

---

Quantum Registers

A single qubit provides very limited computational power. Just as classical computers group bits into registers, we can combine multiple qubits into a quantum register.

In vector form, the state vector of an n-qubit register has 2ⁿ components, and computational steps are represented by unitary 2ⁿ×2ⁿ matrices. This exponential growth is what gives quantum computers their potential advantage over classical machines for certain problem classes.

Prime Factorisation and RSA

In 1977, Ron Rivest, Adi Shamir, and Len Adleman invented the RSA asymmetric encryption scheme while attempting to disprove a theoretical framework on public-key cryptography proposed by Whitfield Diffie and Martin Hellman. Key generation works as follows:

1. Choose two random primes p and q and compute $$n = p \cdot q \quad \text{and} \quad \phi = (p-1)\cdot(q-1)$$
2. Choose $$e \in \mathbb{N} \text{ with } \gcd(e,\phi)=1$$
3. Find $$d \in \mathbb{N} \text{ with } e \cdot d \equiv 1 \pmod{\phi}$$

The private key is (d, n) and the public key is (e, n). Efficient algorithms exist for every step above. To encrypt a message x, compute

$$c \equiv x^e \pmod{n}$$

To decrypt c:

$$x \equiv c^d \pmod{n}$$

It is widely believed—though not proven—that recovering the private key (d, n) from the public key (e, n) is exactly as hard as factoring n into p and q on a classical computer (unless d is already known).

---

The Period-Finding Problem

From this theorem, an algorithm for finding a non-trivial factor of n can be derived:

1. Choose a uniformly at random from {2, …, n−1}.
2. Compute z = gcd(a, n). If z > 1, output z and stop.
3. Find the period p of $f(x) = a^x \bmod n$.
4. If p is odd, return to step i).
5. Compute gcd(a^p/2−1, n) and gcd(a^p/2+1, n). If no proper factor is found, return to step i); otherwise output the factor.

No efficient algorithm exists for step iii) on classical computers—but one does on quantum computers.

---

Shor's Algorithm: Quantum Period Finding

Shor's algorithm, named after its inventor Peter Shor, is a quantum algorithm that determines the period in polynomial time. It works as follows, where f(x) = a^x mod N and N = 2ⁿ:

1. Initialise two registers R₁ and R₂: $$R = R_1, R_2 \leftarrow |0\cdots 0\rangle\,|0\cdots 0\rangle$$
2. Apply the Hadamard transform to R₁, placing it in superposition over all possible x-values: $$R \leftarrow \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} |x\rangle\,|0\cdots 0\rangle$$
3. Apply the oracle U𝑓 to compute the period function and write the result into R₂: $$R \leftarrow \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} |x\rangle\,|f(x)\rangle$$
4. Measure y = R₂.
5. Apply the Quantum Fourier Transform QFTₙ to R₁: $$R_1 \leftarrow \mathrm{QFT}_N\,|x\rangle$$
6. Measure z = R₁ and output the result.

If p ∣ N, the measured value z is a multiple $z = j \cdot \frac{N}{p}$. When gcd(j, p) = 1, the period can be recovered:

$$p = \frac{N}{\gcd(z, N)}$$

If gcd(j, p) ≠ 1, the measurement yielded a wrong multiple and the circuit must be run again. Since the period can now be computed efficiently, and efficient classical algorithms exist for all other steps, RSA can be broken by a sufficiently powerful quantum computer.

The Solution: Lattice-Based Cryptography

To counter the quantum threat, the industry is transitioning to algorithms built on fundamentally different mathematical foundations. The leading candidate family is Lattice-Based Cryptography, whose hardness assumptions are believed to resist both classical and quantum attacks. The NIST Post-Quantum Cryptography standardisation project selected two lattice-based algorithms as primary standards in 2024: ML-KEM (CRYSTALS-Kyber) for key encapsulation and ML-DSA (CRYSTALS-Dilithium) for digital signatures.

---

What Is a Lattice?

A lattice ℒ is a regular, discrete grid of points in n-dimensional space, generated by taking all integer linear combinations of a set of basis vectors. Given a basis matrix B = [b₁ | … | bₙ] the lattice is:

$$\mathcal{L}(B) = \left\{ B\mathbf{x} \;\middle|\; \mathbf{x} \in \mathbb{Z}^n \right\}$$

---

The Learning With Errors (LWE) Problem

Most modern lattice schemes are based on the Learning With Errors (LWE) problem, introduced by Oded Regev in 2005. The central idea: given a system of linear equations modulo a prime q, with a small amount of random noise added to each equation, recover the secret vector s.

Formally, an adversary is given many samples (aᵢ, bᵢ) where aᵢ ∈ ℤᵧ is chosen uniformly at random and:

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

Here s ∈ ℤᵧⁿ is the fixed secret, and e is a small noise vector drawn from a narrow Gaussian distribution χ. Without the noise the system would be trivially solvable by Gaussian elimination. With noise, recovering s is as hard as solving worst-case lattice problems (via Regev's reduction).

---

ML-KEM (CRYSTALS-Kyber): Key Encapsulation

ML-KEM is based on the Module-LWE variant, which works over modules of polynomial rings ℤ_q[X]/(Xⁿ+1) for improved efficiency. The scheme has three phases:

---

ML-DSA (CRYSTALS-Dilithium): Digital Signatures

ML-DSA provides digital signatures using a "Fiat-Shamir with aborts" construction over Module-LWE. The key insight is that signing uses rejection sampling to hide the secret, giving signatures that reveal no information about s.

We implement both ML-KEM-768 (NIST security level 3, ~AES-192 equivalent) and ML-DSA-65 in our encryption pipeline to protect financial document data at rest and in transit against both classical and quantum adversaries.

The Practical Use Case: Protecting Financial Data

Financial records, invoices, and audit trails often have strict retention requirements—sometimes up to 10 or 15 years.

Data encrypted today must withstand the cryptographic attacks of the 2030s and 2040s. By applying post-quantum encryption schemas now, pdftables.io ensures that your sensitive financial data remains mathematically protected against future quantum decryption.