Chapter 46: The Post-Quantum Landscape and the Knapsack Problem

Chapter 46: The Post-Quantum Landscape and the Knapsack Problem#

46.1 Why Post-Quantum, Why Now#

You have already implemented Shor’s algorithm in Qiskit. The exact thing that makes it pedagogically delightful — that an integer can be factored in polynomial time on a quantum computer once we have one — is precisely what makes it strategically catastrophic. RSA, Diffie–Hellman, ECDH, ECDSA, EdDSA: every public-key primitive in widespread use today rests on the hardness of either integer factorisation or discrete logarithm in some abelian group. Shor’s algorithm dispatches the entire list in one stroke.

What “post-quantum” means

A post-quantum (or “quantum-resistant”, or “quantum-secure”) cryptosystem is a cryptosystem that runs on classical hardware (so we can deploy it today on commodity CPUs) but is believed to remain secure against an adversary who has a fault-tolerant quantum computer. The phrase is not synonymous with “quantum cryptography”, which refers to schemes like BB84 that use quantum hardware as part of the protocol.

The urgency is not “wait for the quantum computer to arrive”. The urgency is the harvest-now-decrypt-later threat: any encrypted traffic captured today and stored — by a state actor, a service provider, an opportunistic eavesdropper — can be decrypted in the future once a sufficiently large quantum computer exists. For data with a long confidentiality lifetime (medical records, diplomatic cables, intellectual property), the migration deadline is not the day the quantum computer boots; it is some number of years before that day, equal to the data’s required secrecy lifetime.

The US National Security Agency’s CNSA 2.0 guidance (2022, updated 2024) sets software/firmware signing to PQC by 2025, TLS/IPsec by 2030, and full transition by 2033. The EU agencies (BSI, ANSSI, ENISA) advocate hybrid deployments as a transitional defence-in-depth measure.

46.2 The Five Post-Quantum Families#

The candidate post-quantum cryptosystems group into a small number of families, each based on a different believed-hard problem. Section 10 of our course syllabus enumerates six; in practice the symmetric family is barely affected by quantum attack (Grover halves the effective key length, no more), so the focus falls on five public-key families:

Family

Hard problem

Standardised?

Lattice-based

LWE / Module-LWE / NTRU

ML-KEM (FIPS 203), ML-DSA (FIPS 204), Falcon/FN-DSA (draft FIPS 206)

Code-based

Decoding random linear codes (NP-hard)

Classic McEliece (4th-round), HQC (selected 2025)

Hash-based

Collision/preimage resistance of a hash function

SLH-DSA (FIPS 205), XMSS/LMS (RFC 8391/8554)

Multivariate

Solving systems of polynomial equations over a finite field (MQ)

None standardised; Rainbow broken in 2022

Isogeny-based

Walking the supersingular isogeny graph

None standardised; SIDH/SIKE broken in 2022

Two important properties cut across the table:

  • Diversity of assumption. ML-KEM and ML-DSA both rest on Module-LWE. If a surprise breakthrough were to break Module-LWE, the bulk of the deployed PQC ecosystem would fall in one stroke. NIST has therefore deliberately standardised at least one scheme from a different family in each role: HQC (code-based) as an alternative KEM to ML-KEM; SLH-DSA (hash-based) as an alternative signature to ML-DSA. Crypto-agility is the policy that preserves this diversity in deployment.

  • The “frontier” families are fragile. Both multivariate and isogeny-based cryptography saw their flagship schemes broken in 2022 (Rainbow by Ward Beullens; SIDH/SIKE by Castryck and Decru). The mathematics underlying these families is younger and the cryptanalytic community smaller; we cover them in Chapter 48 partly because they remain interesting research directions and partly because their breaks illustrate, vividly, what it looks like when a lattice-or-code candidate eventually does fall.

Table you should have memorised by W8

For each NIST standard: which family, which hard problem, what role (KEM vs signature), and one sentence on the size cost vs classical (X25519 or Ed25519). It will save you on the exam.

46.3 The NIST PQC Competition — A Brief History#

Year

Event

2016

NIST issues the call for PQC proposals.

2017

69 first-round submissions.

2019

26 second-round candidates.

2020

7 finalists + 8 alternates announced.

2022

First selections: CRYSTALS-Kyber (KEM), CRYSTALS-Dilithium (signature), Falcon (signature), SPHINCS+ (signature).

2024

Standards published as FIPS 203 (ML-KEM), FIPS 204 (ML-DSA), FIPS 205 (SLH-DSA).

2025 (March)

HQC selected as fifth standard (code-based KEM).

2025/2026

Falcon standardisation as FN-DSA / FIPS 206 still in progress.

Two of the original second-round candidates were broken during the competition, illustrating the value of public review:

  • Rainbow (multivariate signature) — broken by Beullens at CRYPTO 2022, reducing the published security level to “weekend on a laptop” for the proposed parameters.

  • SIKE (isogeny KEM, alternate candidate) — broken by Castryck and Decru in the summer of 2022, also reducing security to “minutes on a laptop” for SIKEp434.

These breaks did not invalidate the families they came from (other multivariate constructions and other isogeny constructions like CSIDH, SQIsign remain candidates for future research), but they did remove the standardisation candidates and cool enthusiasm for the families. We discuss both in Chapter 48.

46.4 The Subset-Sum / 0-1 Knapsack Problem#

To get a concrete feel for “NP-hard underpins a public-key cryptosystem”, we spend the rest of this chapter on the historically first attempt: the Merkle–Hellman knapsack cryptosystem (1978).

Definition — Subset-Sum / 0-1 Knapsack

Given a set of positive integers \(a_1, \ldots, a_n\) and a target sum \(S\), find \(\bx = (x_1, \ldots, x_n) \in \{0,1\}^n\) such that

\[ \sum_{i=1}^{n} x_i \, a_i = S. \]

The decision version of this problem is NP-complete (Karp 1972). At first glance, then, building public-key encryption out of it looks irresistible: pick a public sequence \(a_1, \ldots, a_n\), encode a plaintext bitstring \(\bx\) as the ciphertext \(S = \sum x_i a_i\), and the decryption problem inherits NP-hardness.

The catch — and Merkle and Hellman knew this — is that NP-hardness is a worst-case statement. We need every random instance of our scheme to be hard, not just some adversarial one. And as we shall see, a careful trapdoor that makes decryption easy for the legitimate recipient also makes the public sequence non-random in a way that cryptanalysts can exploit.

46.5 Superincreasing Knapsacks Are Easy#

Definition — Superincreasing Sequence

A sequence \(w_1, w_2, \ldots, w_n\) of positive integers is superincreasing if

\[ w_k > \sum_{i=1}^{k-1} w_i \quad \text{for every } k = 2, 3, \ldots, n. \]

For a superincreasing sequence the subset-sum problem is solved by a greedy algorithm in \(O(n)\) time: starting from the largest \(w_n\) and working down, include \(w_k\) in the subset whenever \(w_k \le S\) (and then subtract \(w_k\) from \(S\)). This works because everything below \(w_k\) together cannot reach \(w_k\).

This is the trapdoor. The legitimate recipient holds a superincreasing sequence \(w_1, \ldots, w_n\) as their secret key and decrypts in \(O(n)\). The public key is a disguised version of the sequence that no longer looks superincreasing.

import numpy as np

def is_superincreasing(w):
    w = list(w)
    s = 0
    for wi in w:
        if wi <= s:
            return False
        s += wi
    return True

def greedy_subset_sum(w, S):
    '''Solve subset-sum greedily for a superincreasing sequence.

    Returns the bit vector x in {0,1}^n with sum_i x_i*w[i] == S, or None.
    '''
    n = len(w)
    x = [0] * n
    remaining = S
    for k in range(n - 1, -1, -1):
        if w[k] <= remaining:
            x[k] = 1
            remaining -= w[k]
    return x if remaining == 0 else None


# Demonstration: a superincreasing sequence, encryption-by-summing,
# decryption-by-greedy.
rng = np.random.default_rng(20260503)
w = [2]
for _ in range(7):
    w.append(int(sum(w) + rng.integers(1, 5)))
print('Superincreasing sequence w =', w)
assert is_superincreasing(w)

x = [int(b) for b in '10110010']
S = sum(xi * wi for xi, wi in zip(x, w))
print('Plaintext bits  x =', x)
print('Ciphertext sum  S =', S)
x_recovered = greedy_subset_sum(w, S)
print('Recovered bits  x =', x_recovered)
assert x_recovered == x

Superincreasing sequence w = [2, 3, 8, 17, 31, 65, 130, 258]
Plaintext bits  x = [1, 0, 1, 1, 0, 0, 1, 0]
Ciphertext sum  S = 157
Recovered bits  x = [1, 0, 1, 1, 0, 0, 1, 0]

46.6 The Merkle–Hellman Trapdoor#

The Merkle–Hellman trick

Setup. Pick a superincreasing sequence \(w_1, \ldots, w_n\) (the secret key). Pick a modulus \(m > \sum w_i\) and a multiplier \(r\) coprime to \(m\).

Public key. Publish \(a_i = r \, w_i \bmod m\) for \(i = 1, \ldots, n\). The sequence \(a_1, \ldots, a_n\) no longer looks superincreasing — it looks random modulo \(m\).

Encryption. A sender encodes a plaintext bit-vector \(\bx \in \{0,1\}^n\) as \(S = \sum_i x_i a_i\) (an ordinary integer, not modular).

Decryption. The recipient computes \(S' = r^{-1} S \bmod m = \sum_i x_i w_i \bmod m\). Because \(\sum w_i < m\) and the actual \(\sum x_i w_i \le \sum w_i\) fits below the modulus, \(S'\) equals \(\sum x_i w_i\) as an integer. Now solve the easy superincreasing subset-sum to recover \(\bx\).

Notice how clean this is. The trapdoor — the multiplier-and-modulus disguise — is invertible if and only if you know \(r\). To everyone else, the public sequence \((a_i)\) looks like a hard knapsack instance; only the recipient can convert it back to the easy one.

def modinv(a, m):
    '''Compute the modular inverse of a mod m using extended Euclid.'''
    g, x, _ = extended_gcd(a, m)
    if g != 1:
        raise ValueError(f'{a} has no inverse mod {m}')
    return x % m

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = extended_gcd(b, a % b)
    return g, y1, x1 - (a // b) * y1


def merkle_hellman_keygen(n=8, seed=20260503):
    # `random.randrange` handles arbitrary-precision Python ints, so this
    # keygen works for any n (numpy's Generator caps at int64 ranges).
    import random as _r
    rnd = _r.Random(seed)
    # 1. Superincreasing secret sequence
    w = [rnd.randrange(2, 10)]
    for _ in range(n - 1):
        w.append(sum(w) + rnd.randrange(1, 10))
    # 2. Modulus m > sum(w_i), then a multiplier r coprime to m
    m = sum(w) + rnd.randrange(1, 100)
    while True:
        r = rnd.randrange(2, m)
        try:
            r_inv = modinv(r, m)
            break
        except ValueError:
            continue
    # 3. Public key a_i = r*w_i mod m
    a = [(r * wi) % m for wi in w]
    sk = {'w': w, 'm': m, 'r': r, 'r_inv': r_inv}
    pk = a
    return pk, sk

def merkle_hellman_encrypt(pk, x):
    return sum(xi * ai for xi, ai in zip(x, pk))

def merkle_hellman_decrypt(sk, S):
    Sp = (sk['r_inv'] * S) % sk['m']
    return greedy_subset_sum(sk['w'], Sp)


pk, sk = merkle_hellman_keygen(n=8)
print('Public  key a =', pk)
print('Secret  key w =', sk['w'])
print('  modulus  m =', sk['m'])
print('  multipl. r =', sk['r'])

plaintext = [int(b) for b in '11010011']
S = merkle_hellman_encrypt(pk, plaintext)
print('Ciphertext     S =', S)
recovered = merkle_hellman_decrypt(sk, S)
print('Recovered bits   =', recovered)
assert recovered == plaintext

Public  key a = [335, 402, 102, 338, 140, 347, 761, 753]
Secret  key w = [5, 6, 18, 38, 68, 137, 275, 555]
  modulus  m = 1104
  multipl. r = 67
Ciphertext     S = 2589
Recovered bits   = [1, 1, 0, 1, 0, 0, 1, 1]

46.6.1 Density and the W2 Lab Key#

The density of a knapsack instance \((a_1, \ldots, a_n)\) is

\[ d \;=\; \frac{n}{\log_2 \max_i a_i}. \]

The Lagarias–Odlyzko (1985) attack and its Coster–Joux–LaMacchia–Odlyzko–Schnorr– Stern (1992) refinement break low-density instances (\(d \lesssim 0.94\)) in polynomial time using lattice reduction. The cell below produces a low-density \(n=32\) Merkle–Hellman public key suitable for the W2 lab: in W2 we will read this key back, build the Lagarias–Odlyzko lattice (Ex 40.4 of the upstream cryptanalysis chapter), and run LLL to recover the plaintext bit-vector.

import math, json

def density(public_key):
    return len(public_key) / math.log2(max(public_key))

# Show how density falls as n grows under the default keygen.
for n in (8, 16, 32, 64):
    pk_n, _ = merkle_hellman_keygen(n=n, seed=20260503 + n)
    print(f'n = {n:3d}   max(a_i) ≈ 2^{math.log2(max(pk_n)):5.1f}   density = {density(pk_n):.3f}')

# Now build a deliberately low-density key for the W2 LLL lab: use a much larger
# multiplier modulus so the public a_i become wide integers.
def merkle_hellman_keygen_lowdensity(n=32, target_bits=128, seed=20260601):
    import random as _r
    rnd = _r.Random(seed)
    w = [rnd.randrange(2, 10)]
    for _ in range(n - 1):
        w.append(sum(w) + rnd.randrange(1, 10))
    m = (1 << target_bits) + rnd.randrange(1, 1 << 60)
    while True:
        r = rnd.randrange(2, m)
        try:
            r_inv = modinv(r, m); break
        except ValueError:
            continue
    a = [(r * wi) % m for wi in w]
    return a, {'w': w, 'm': m, 'r': r, 'r_inv': r_inv}

pk_w1, sk_w1 = merkle_hellman_keygen_lowdensity(n=32, target_bits=128)
print()
print(f'W2 lab key:  n = {len(pk_w1)},  ~{int(math.log2(max(pk_w1)))}-bit a_i, '
      f'density = {density(pk_w1):.3f}')

# Encrypt a plaintext to hand off.
plaintext_w1 = [int(b) for b in '11001010101100001100110010100111']
S_w1 = merkle_hellman_encrypt(pk_w1, plaintext_w1)

# Round-trip check before the lab handover.
assert merkle_hellman_decrypt(sk_w1, S_w1) == plaintext_w1, 'self-decrypt failed'

# Print a JSON blob ready to save as pk_w1.json (the W2 lab will read it).
handover = {
    'n': len(pk_w1),
    'public_key': pk_w1,
    'ciphertext': S_w1,
    'density': density(pk_w1),
}
print()
print('--- pk_w1.json (first 240 chars) ---')
print(json.dumps(handover)[:240], '...')

n =   8   max(a_i) ≈ 2^ 10.4   density = 0.767
n =  16   max(a_i) ≈ 2^ 18.4   density = 0.869
n =  32   max(a_i) ≈ 2^ 34.0   density = 0.942
n =  64   max(a_i) ≈ 2^ 65.9   density = 0.971

W2 lab key:  n = 32,  ~127-bit a_i, density = 0.250

--- pk_w1.json (first 240 chars) ---
{"n": 32, "public_key": [224387419562186596285440052009478462915, 288002407853184006134993028873468930260, 261862428319306777470369984933668012439, 138565005805237772219412842712369566393, 295867515989035635031290651886833907548, 2706524549 ...

46.7 Why Merkle–Hellman Broke#

The Merkle–Hellman cryptosystem was published in 1978 and broken by Adi Shamir in 1982 (published 1984). Shamir’s polynomial-time attack does not solve the general NP-hard subset-sum problem — that remains hard. It exploits the fact that the public sequence is a modular linear image of a superincreasing sequence, and that this leaves a recoverable pattern in the continued-fraction expansion of \(a_i / m\).

A second attack, due to Lagarias and Odlyzko (1985), realised that low-density subset-sum instances — those where the number of bits in each \(a_i\) is much larger than \(n\) — can be solved by lattice reduction. Each such instance is converted to a lattice in which a short vector encodes the plaintext bit-vector \(\bx\), and LLL recovers it in polynomial time.

Both attacks belong squarely in our W2 lecture: Shamir’s attack illustrates the danger of structured trapdoors, and the Lagarias–Odlyzko attack is the first crypto-relevant application of LLL we will see (full treatment in Chapter 40 of the upstream cryptanalysis book).

Lesson for this course

NP-hardness of a problem is necessary but not sufficient for a public-key cryptosystem. The cryptosystem must use random-looking instances of the problem, not engineered ones with a hidden structure. Every PQC family we will study has had to prove this — typically through a worst-case-to-average-case reduction (Ajtai for lattices, Brakerski–Vaikuntanathan for LWE) or through two decades of public cryptanalytic effort (McEliece, SPHINCS+).

46.8 Exercises#

Exercise 46.1 — Counting trapdoors.

For \(n = 8\), count how many distinct superincreasing sequences with \(w_1 \in [2,9]\) and \(w_{k+1} \in [\sum_{i \le k} w_i + 1, \sum_{i \le k} w_i + 10]\) exist. Estimate the entropy of the secret key for \(n = 256\) under the same per-step uniform choice. Is it sufficient to resist exhaustive search? Why is “exhaustive search of the secret key” not the right threat model for a knapsack cryptosystem?

Exercise 46.2 — Density of a knapsack.

The density of a knapsack instance \((a_1, \ldots, a_n)\) is \(d = n / \log_2 (\max_i a_i)\). Compute the density of the public key produced by merkle_hellman_keygen(n=8) and merkle_hellman_keygen(n=64). The Lagarias–Odlyzko (1985) attack succeeds for densities below \(\approx 0.6463\); the Coster–Joux–LaMacchia–Odlyzko–Schnorr–Stern (1992) refinement raised the threshold to \(\approx 0.9408\). Are the default parameters in the notebook below or above each threshold?

Exercise 46.3 — Implement Shamir’s continued-fraction attack (sketch).

Read Shamir 1984 §3. Implement, on a small instance (\(n = 5\)), the step that extracts a candidate multiplier \(r\) from the continued-fraction expansion of \(a_1 / a_2\). You do not need the full attack; the goal is to see why the trapdoor leaks.

Exercise 46.4 — Knapsack cryptosystem in modern wrapping.

Pretend the year is 2026 and you are pitching a “post-quantum” KEM based on subset-sum. Write a one-page memo (a) describing the parameters you would propose, (b) listing the two known attacks and their density requirements, and (c) estimating, by combining the attacks, what density would currently be considered safe. End with a recommendation: would you submit this to a NIST round 5 call?

Exercise 46.5 (lab handover to W2) — Build the artefact you will break.

Generate a Merkle–Hellman public key with \(n = 32\) and low density (modulus chosen so that each \(a_i\) has roughly \(4n = 128\) bits). Save the public key and a ciphertext to a JSON file pk_w1.json in your working directory.

In the W2 lab you will read this file back, build the lattice from Lagarias–Odlyzko (the construction in Ex 40.4 of the upstream Ch 40), run LLL on it, and recover the plaintext bit-vector.

Hint for picking the modulus

To produce roughly \(b\)-bit \(a_i\) values, pick the modulus \(m\) to be roughly \(2^b\). The density is then \(n/b\), so for \(n = 32\) and density \(\approx 0.25\) (safely in LLL-attackable territory) take \(m \approx 2^{128}\).

46.9 Summary#

  1. Quantum-resistant cryptography is needed now, not when a quantum computer appears, because of harvest-now-decrypt-later.

  2. Five public-key families are candidates: lattice, code, hash, multivariate, isogeny. Three have NIST standards (lattice + hash + code); two saw their flagship submissions broken in 2022.

  3. NP-hardness alone does not yield a public-key cryptosystem. Merkle–Hellman (1978) demonstrated this: subset-sum is NP-hard, but the trapdoor leaks structure that is exploitable in polynomial time (Shamir 1984; Lagarias–Odlyzko 1985 via LLL).

  4. The Lagarias–Odlyzko attack is the first crypto-relevant application of lattice reduction we meet — the formal LLL treatment is the W2 chapter (upstream Ch 40).

  5. Crypto-agility — the ability to swap algorithms cheaply — matters as much as any single algorithm choice.

46.10 References#

  1. Diffie, W. and Hellman, M. E. (1976). New Directions in Cryptography. IEEE Trans. Information Theory 22(6), 644–654.

  2. Merkle, R. C. and Hellman, M. E. (1978). Hiding Information and Signatures in Trapdoor Knapsacks. IEEE Trans. Information Theory 24(5), 525–530.

  3. Shamir, A. (1984). A Polynomial-Time Algorithm for Breaking the Basic Merkle–Hellman Cryptosystem. IEEE Trans. Information Theory 30(5), 699–704.

  4. Lagarias, J. C. and Odlyzko, A. M. (1985). Solving Low-Density Subset Sum Problems. J. ACM 32(1), 229–246.

  5. Coster, M. J., Joux, A., LaMacchia, B. A., Odlyzko, A. M., Schnorr, C.-P., Stern, J. (1992). Improved Low-Density Subset Sum Algorithms. Computational Complexity 2, 111–128.

  6. NIST (2024). FIPS 203 — Module-Lattice-Based Key-Encapsulation Mechanism Standard. https://csrc.nist.gov/pubs/fips/203/final

  7. NIST (2024). FIPS 204 — Module-Lattice-Based Digital Signature Standard.

  8. NIST (2024). FIPS 205 — Stateless Hash-Based Digital Signature Standard.

  9. NIST (2025-03-11). Public announcement: HQC selected as the fifth PQC standard. https://csrc.nist.gov/News.

  10. NSA (2024). Commercial National Security Algorithm Suite 2.0 (CNSA 2.0). https://media.defense.gov/2022/Sep/07/2003071834/-1/-1/0/CSA_CNSA_2.0_ALGORITHMS_.PDF

Contents