Post-Quantum and Lattice-Based Cryptography Questions

Direct answer

Recommend a LATTICE-based scheme (ML-DSA or, once standardized, Falcon/FN-DSA) as the default for on-chain transaction signing, with Falcon specifically favored where signature size and verification-gas cost dominate the decision, accepting its harder-to-implement constant-time signing in exchange. Reserve hash-based signatures (SLH-DSA/SPHINCS+) for a narrower role, infrequent, high-value, long-term-security operations (multisig root keys, upgrade-authorization keys) where large signature size is affordable and SLH-DSA's minimal, hash-only security assumption is worth the size cost. Multivariate is excluded outright (no NIST-standardized multivariate signature scheme survives after Rainbow's 2022 break); code-based is excluded for signatures specifically (McEliece-style constructions have no competitive signature variant, the assumption fits encryption, not signing).

Structured elaboration

Why verification cost and signature size dominate the on-chain decision, not key size. A blockchain's SIGNING happens once per transaction author, off-chain, largely unconstrained; VERIFICATION happens on EVERY full node, for EVERY transaction, every time the chain processes a block, so verification compute (gas cost) and signature size (propagated and stored on every node, forever, as part of the immutable ledger) are the recurring, multiplied-by-every-node-forever costs that should dominate the trade-off, not one-time key generation cost.

Falcon: smallest lattice signatures, hardest to implement safely. Falcon-512 (roughly NIST Category 1) signs with a 666-byte signature and a 897-byte public key; Falcon-1024 (roughly Category 5) with a 1,280-byte signature and 1,793-byte public key, the smallest signatures of any lattice-based NIST finalist, a direct, real advantage for propagation bandwidth and on-chain storage. The cost: Falcon's signing algorithm requires floating-point (or carefully emulated fixed-point) Gaussian sampling over an NTRU lattice, a genuinely harder target for constant-time, side-channel-resistant implementation than ML-DSA/ML-KEM's simpler integer NTT-based operations; verification, by contrast, uses only integer arithmetic and is comparatively simple and fast, which matters specifically because verification is the operation repeated on every node.

ML-DSA: a more implementation-forgiving middle ground. ML-DSA's signatures are larger than Falcon's (several kilobytes, using integer-only lattice operations throughout, avoiding Falcon's floating-point signing complexity entirely), a reasonable default when implementation-safety margin is weighted above squeezing signature size to the theoretical lattice-based minimum, which is a defensible choice for a base-layer protocol that many independent teams will need to implement correctly and interoperably.

SLH-DSA/SPHINCS+: minimal assumption, large signatures, no statefulness risk. At the 128-bit level, SLH-DSA's SMALL ("s") variant signs at 7,856 bytes with a 32-byte public key; its FAST ("f") variant signs at 17,088 bytes for faster signing at the cost of larger signatures. Both are far larger than any lattice-based option, an unattractive cost for routine transaction signing at scale, but SLH-DSA's security rests on hash-function properties alone (collision and preimage resistance, with no algebraic or number-theoretic assumption at all), the most conservative, least-structurally-exposed assumption among all PQC signature families, and it is STATELESS (unlike XMSS, no leaf-index management or reuse risk to coordinate across signing devices). This combination, maximally conservative assumption, no statefulness risk, at the cost of size, is precisely the profile that fits an infrequently-used, high-value ROOT key (a multisig governance key, an upgrade-authorization key) far better than it fits routine per-transaction signing.

Worked example

Concrete size comparison across the recommended options, all figures live-verified this session against their respective specifications, not recalled from memory alone:

Falcon's signature is roughly 12x smaller than SLH-DSA's SMALL variant and roughly 26x smaller than its FAST variant, a genuinely material difference at blockchain scale where every byte is replicated and stored permanently across every full node; SLH-DSA's 32-byte public key, by contrast, is the smallest PUBLIC key of the group by a wide margin, a relevant advantage specifically for a root/governance key that many other keys or contracts might need to reference or embed on-chain repeatedly, even though its signature itself is the largest.

Trade-offs and pitfalls

• Common mistake: optimizing purely for signature size without weighing implementation-safety risk. Falcon's smaller signature is a real advantage, but shipping a signing implementation with a subtly non-constant-time Gaussian sampler is a WORSE outcome than a slightly larger ML-DSA signature signed correctly; for a base-layer protocol where implementation bugs are catastrophic and hard to patch retroactively (immutable history, hard-fork required to fix), the implementation-safety margin deserves real weight against the pure size optimization.
• Multisig use-cases add a genuine multiplicative cost that plain single-signer comparisons hide. An $m$-of-$n$ multisig scheme using $n$ SIGNATURES concatenated (the naive approach) multiplies whichever per-signature size was chosen by $n$; lattice-based options' smaller per-signature size compounds favorably here, while SLH-DSA's already-large signatures become proportionally more expensive still, reinforcing why SLH-DSA is better reserved for a SINGLE root key rather than routine multisig participants.
• Light-client verification cost is a separate axis from full-node verification cost, and both matter. A light client verifying a proof of chain state (rather than every full transaction) may be far more sensitive to per-signature verification cost than a full node is, since light clients often run on constrained hardware (mobile, embedded); Falcon's integer-only, comparatively fast verification is again the favorable choice on this axis specifically.
• Upgradeability: committing to ONE family exclusively creates exactly the concentration risk that undermined confidence in NIST's own round-3 finalist slate (three of four finalists, Kyber, Dilithium, and Falcon, shared the same lattice hard-problem family, precisely the structural-diversity gap NIST's own March 2025 HQC decision was meant to close). A protocol design that hard-codes a single signature scheme with no upgrade path, should that scheme's specific hard-problem family suffer an unexpected future break, repeats the same structural risk NIST's own post-hoc HQC diversification move was meant to address; a genuinely robust on-chain design should include an explicit, governance-controlled signature-scheme migration path from day one, not assume the initially chosen family will remain secure indefinitely.

Direct answer

NIST's PQC standardization process (2016 to present) succeeded at its primary goal, three FIPS standards published in August 2024 (FIPS 203 ML-KEM from CRYSTALS-Kyber, FIPS 204 ML-DSA from CRYSTALS-Dilithium, FIPS 205 SLH-DSA from SPHINCS+) plus FN-DSA (Falcon) expected to follow, but the process's own outcomes reveal a real critique: of the four initial finalists, three (Kyber, Dilithium, Falcon) were lattice-based, concentrating cryptographic diversity risk on a single mathematical assumption family, a gap NIST itself later moved to address by announcing, in March 2025, standardization of the code-based HQC algorithm specifically as a structurally different backup KEM. Implementation security (side-channels) and deployment readiness were treated as evaluation criteria throughout, but concrete testing OBLIGATIONS for submitters were comparatively light relative to the mathematical-security evaluation, a second real gap.

Structured elaboration

Selection criteria, as NIST stated them. Security (against both classical and quantum attackers, and including resistance to side-channel and implementation-level attacks as a stated, though not uniformly weighted, factor), cost and performance (across a range of platforms, including constrained embedded devices), and algorithm and implementation characteristics (simplicity, flexibility, ease of secure implementation) were the three official evaluation axes across all rounds.

Algorithmic diversity: the real, corpus-confirmed gap. Round 3's four finalists were Kyber, Dilithium, Falcon (all lattice-based) and SPHINCS+ (hash-based), meaning three of four rested on essentially the same mathematical assumption family (structured lattice problems). This was a live concern during the process itself (part of why Classic McEliece, BIKE, HQC remained as round-4 alternates rather than being eliminated outright), and NIST's own subsequent action, announcing in March 2025 that it would standardize HQC specifically as a second, structurally DIFFERENT KEM (code-based, not lattice-based) alongside ML-KEM, is itself the strongest evidence that the diversity gap was real: NIST would not have deliberately added a second, less-efficient KEM to the standard portfolio if the existing lattice-heavy slate were considered to already provide adequate structural diversity.

Implementation security emphasis: present but secondary to mathematical security in practice. Side-channel resistance was a named evaluation criterion, but the bulk of round-by-round public evaluation and academic cryptanalysis focused overwhelmingly on breaking or bounding the MATHEMATICAL hardness assumptions (exactly the kind of work that broke Rainbow and SIKE), while side-channel robustness was comparatively lightly tested at the submission stage and has instead been an ONGOING post-selection concern (constant-time reference implementations, masking countermeasures for NTT-based and Gaussian-sampling operations, published well after finalist selection rather than as a submission-time gate).

Readiness for deployment. The process explicitly favored candidates with clear implementation paths and reasonable performance across platforms, which is part of why lattice schemes (fast, moderate key/ciphertext sizes) fared well relative to Classic McEliece (excellent mathematical track record, but huge public keys) in the KEM category specifically; this is a defensible trade-off, not obviously a flaw, but it does mean "deployment readiness" as evaluated skewed toward performance-friendly candidates in ways that a security-purist selection process might have weighted differently.

Worked example

The lattice-concentration critique is not a matter of opinion, it follows directly from counting the finalists by underlying hard-problem family:

Three of four finalists (75%) share a lattice-based hard-problem family; the sole non-lattice finalist is a signature scheme, meaning the KEM category specifically had ZERO non-lattice representation among the round-3 finalists. NIST's March 2025 decision to move HQC (code-based) toward standardization as an additional KEM directly closes exactly this gap, not a coincidental additional feature: it gives the KEM category the same non-lattice fallback the signature category already had via SPHINCS+/SLH-DSA.

Trade-offs and pitfalls

• Concentration risk is not hypothetical: it already partially materialized within the process itself. No lattice finalist was broken, but Rainbow (multivariate, round-3 finalist in the SIGNATURE category) and SIKE (isogeny-based, a round-4 KEM alternate) were both catastrophically broken in 2022, after years of prior scrutiny; this is direct, in-process evidence that "survived cryptanalysis so far" is not the same as "structurally safe," which is exactly the argument for deliberately maintaining structural diversity even among candidates that currently look secure.
• Common mistake: treating the eventual HQC addition as proof the original process was flawed, rather than as the process correctly self-correcting. A standardization process that identifies a gap in its OWN portfolio and deliberately fills it (rather than declaring victory at four finalists) is arguably evidence the process worked as intended over a long enough horizon, not evidence it failed; the critique is better aimed at the TIMELINE (diversity as an afterthought years later, rather than a harder requirement from round 3 onward) than at the fact of the gap's existence.
• Concrete improvements worth proposing for future rounds: (1) a MANDATORY constant-time reference implementation and a standardized side-channel test suite (dudect-style statistical timing tests, fault-injection test vectors) as a submission-stage GATE, not a post-selection nice-to-have; (2) an explicit, stated minimum-diversity requirement across hard-problem families among finalists in each category, rather than diversity as an emergent property of whichever candidates happen to survive cryptanalysis; (3) a published, structured scoring rubric (weighted criteria, explicit tie-breaking rules) rather than narrative-only selection reports, to make the trade-offs between security margin, performance, and implementation simplicity auditable after the fact.
• Deployment-readiness criteria can create a subtle selection bias toward "easy to implement fast," which is not the same axis as "hardest to get wrong." Falcon's need for careful floating-point (or fixed-point-emulated) Gaussian sampling during signing is widely acknowledged as a genuinely harder implementation target for constant-time correctness than ML-KEM/ML-DSA's simpler integer NTT-based operations, a real implementation-risk cost that a pure performance-and-size comparison does not fully capture.

Direct answer

Adding hybrid post-quantum key exchange to TLS 1.3 means carrying both a classical ECDHE share and a PQC KEM's public value/ciphertext through the existing key_share extension mechanism, combining the two resulting secrets (concatenation, fed into the existing key schedule) so an attacker must break both primitives to recover the session keys, and relying on TLS 1.3's existing transcript-authentication machinery for downgrade protection rather than inventing a new mechanism. The main deployment costs are larger handshake messages (kilobyte-scale KEM keys/ciphertexts versus tens of bytes for classical ECDHE) and the generally small additional CPU cost of the KEM operations, not any change to certificate-based authentication, which for now stays classical.

Structured elaboration

Handshake message flow changes. TLS 1.3's ClientHello already carries a key_share extension listing (NamedGroup, key_exchange) pairs; a hybrid deployment defines a new named-group identifier representing the combination (an "X25519 + ML-KEM-768" group), so the client sends one combined key share containing the X25519 public value concatenated with the ML-KEM encapsulation key. The server's ServerHello responds with its own X25519 public value concatenated with the KEM ciphertext. No new message TYPES are introduced, only a larger payload inside the existing extension.

sequenceDiagram
    participant C as Client
    participant S as Server
    C->>S: ClientHello + key_share(X25519_pub || MLKEM_ek)
    S->>S: sample ephemeral X25519 keypair
    S->>S: encapsulate against MLKEM_ek -> ct, ss_pq
    S->>C: ServerHello + key_share(X25519_pub_S || MLKEM_ct)
    Note over C,S: both sides compute ss_classical via X25519 DH
    Note over C,S: client decapsulates MLKEM_ct -> ss_pq
    Note over C,S: HKDF-Extract(ss_classical || ss_pq) feeds existing key schedule
    C->>S: Finished, MAC over full transcript
    S->>C: Finished, MAC over full transcript

How secrets are combined into keying material. Both sides independently compute a classical shared secret (X25519 Diffie-Hellman) and a post-quantum shared secret (KEM decapsulation), CONCATENATE the two byte strings, and feed the result into TLS 1.3's existing HKDF-Extract step exactly where a plain ECDHE secret would normally go, no other part of the key schedule changes. This concatenation combiner is a standard, analyzed way to combine two KEM secrets: it is secure as long as at least one of the two component secrets is secure, so neither a classical break of X25519 alone nor a future break of the PQC KEM alone compromises the session.

Negotiation and downgrade protection. Because the hybrid combination is negotiated as a single, atomic named group inside the extension mechanism TLS 1.3 already authenticates, no new downgrade-protection mechanism is required: the entire handshake transcript, including which group was negotiated, is bound into the derived keys and verified by the Finished message's MAC. An active attacker who strips the hybrid group to force a classical-only fallback changes the transcript both sides hash, so the resulting Finished MACs no longer match and the handshake aborts, TLS 1.3's existing transcript-binding design is what protects against this without any hybrid-specific addition.

Certificate/signature format adjustments. Current mainstream hybrid deployments scope the PQC change to KEY EXCHANGE only; the certificate chain authenticating the handshake remains classical (RSA or ECDSA) for now. Migrating authentication to post-quantum signatures (ML-DSA/Dilithium certificates) is a largely separate migration with its own cost profile (larger certificate chains on every handshake, not just when a fresh key exchange happens), which is why hybrid key exchange is commonly deployed well ahead of PQC certificate authentication.

Performance and latency impacts. The dominant added cost is bytes, not CPU: a Level-3-category ML-KEM public key/ciphertext pair adds roughly a kilobyte to ClientHello and a similar amount to ServerHello, which can matter for handshakes constrained by the TCP initial congestion window more than for raw computation, lattice KEM operations are fast on modern hardware, generally negligible next to RSA/ECDSA signature verification in the same handshake (worked example below).

Worked example

ML-KEM-768's published sizes (1,184-byte public key, 1,088-byte ciphertext) give a directly computable handshake-growth number, worth deriving explicitly rather than eyeballed:

x25519_share = 32           # bytes, each direction
mlkem768_pk  = 1184          # bytes, published ML-KEM-768 public key size
mlkem768_ct  = 1088          # bytes, published ML-KEM-768 ciphertext size

client_hello_added = (x25519_share + mlkem768_pk) - x25519_share   # swap classical-only for hybrid
server_hello_added = (x25519_share + mlkem768_ct) - x25519_share
print("ClientHello key_share growth (classical-only -> hybrid):", client_hello_added, "bytes")
print("ServerHello key_share growth (classical-only -> hybrid):", server_hello_added, "bytes")
print("total added across the handshake:", client_hello_added + server_hello_added, "bytes")

Output:

ClientHello key_share growth (classical-only -> hybrid): 1184 bytes
ServerHello key_share growth (classical-only -> hybrid): 1088 bytes
total added across the handshake: 2272 bytes

Roughly 2.3 KB of extra handshake bytes split across both directions, against a typical TCP initial congestion window on the order of ten packets (about 14.6 KB at a 1,460-byte MSS): the added bytes are a meaningful fraction of that budget without necessarily forcing an extra round trip on their own, but combined with a certificate chain in the same flight it can tip a handshake over the initial window on constrained paths, which is the concrete mechanism behind the "hybrid TLS costs a round trip on some networks" caution.

Trade-offs and pitfalls

• Downgrade protection is "free" here specifically because of how the group is negotiated as a single atomic option. If a hybrid implementation instead negotiated the classical and PQC components as two separate, independently-droppable extensions, an attacker could strip just the PQC one without necessarily breaking the transcript hash in a way the peer notices, exactly why the single-combined-group approach, not two separate shares, is the deployed pattern.
• Concatenation combiner security depends on the specific analyzed construction, not just "mixing the secrets somehow." Ad hoc combiners (XOR instead of concatenation, or hashing the two secrets separately before combining) can lose the "secure if either component is secure" property.
• Treating this as solving the whole PQC-migration problem is a common overreach. Hybrid key exchange protects confidentiality of new sessions against a future quantum adversary (directly addressing harvest-now-decrypt-later); it does nothing for authentication, a quantum adversary with Shor's algorithm still forges RSA/ECDSA signatures on certificates until those are separately migrated.

Direct answer

Shor's algorithm is a quantum algorithm that solves integer factorization and the discrete logarithm problem (including the elliptic-curve variant) in time polynomial in the bit-length of the input, placing both problems in the complexity class BQP (bounded-error quantum polynomial time). RSA's security rests on factoring being hard and ECC's rests on the discrete logarithm problem (DLP) being hard for the chosen group; because Shor's algorithm solves both efficiently on a sufficiently large, fault-tolerant quantum computer, an attacker who can build and run one recovers RSA and ECC private keys directly from public keys, breaking confidentiality, authenticity, and non-repudiation for anything protected by these schemes.

Structured elaboration

What Shor's algorithm actually computes. At its core, Shor's algorithm is a period-finding algorithm: given a periodic function $f(x) = a^x \bmod N$, it finds the period $r$ (the order of $a$ modulo $N$) using quantum phase estimation and the quantum Fourier transform (QFT) to extract $r$ from a superposition over all $x$ in one coherent measurement, something no known classical algorithm can do efficiently for a generic $N$. Once $r$ is known, everything else is classical post-processing.

Complexity class. Shor's algorithm runs in time polynomial in $\log N$ (the number of bits of the modulus), dominated by modular exponentiation and the QFT, both of which cost polynomially many quantum gates. This places integer factorization and the discrete logarithm problem in BQP. Classically, the best known algorithm for factoring (the general number field sieve) is sub-exponential but still super-polynomial; the best known algorithm for the discrete logarithm problem over a well-chosen elliptic curve group (Pollard's rho) is fully exponential in the group's bit-length. Shor's algorithm collapses both to polynomial time.

Which problems it solves, and the mapping to RSA/ECC.

• Factoring, breaks RSA. RSA's modulus is $N = pq$ for two large secret primes. Shor's algorithm factors $N$ directly: pick a random $a$ coprime to $N$, find its order $r$ via period-finding, and if $r$ is even and $a^{r/2} \not\equiv -1 \pmod{N}$, then $\gcd(a^{r/2}-1, N)$ and $\gcd(a^{r/2}+1, N)$ are non-trivial factors of $N$ (worked example below). Recovering $p, q$ lets an attacker directly compute the RSA private exponent.
• Discrete logarithm, breaks ECC. ECC public keys have the form $Q = dG$ for a base point $G$ and secret scalar $d$. Shor's algorithm generalizes to abelian groups: it finds $d$ via the same period-finding machinery applied to the group operation (point addition) instead of modular multiplication, again in polynomial time in the bit-length of the group order, directly recovering the ECDH/ECDSA private key.

Which security properties are lost. Once an attacker can run Shor's algorithm against a target key:

• Confidentiality is lost for anything encrypted, or whose symmetric session key was established, via RSA encryption or elliptic-curve Diffie-Hellman: the attacker recovers the private key and decrypts.
• Authenticity and non-repudiation are lost for RSA and ECDSA/EdDSA signatures: an attacker who recovers the signing key can forge signatures indistinguishable from genuine ones, so a signature can no longer be trusted as proof the claimed signer produced it.
• Any protocol layering additional guarantees on top (mutual TLS, certificate chains rooted in an RSA/ECDSA CA key) inherits the same collapse, since the whole chain of trust reduces back to these two hard problems.

Worked example

The classical bookkeeping of Shor's algorithm, given the period $r$, is easy to verify by hand for a toy modulus. Take $N = 15$, witness $a = 7$ (the standard textbook example; the quantum period-finding subroutine that returns $r$ is treated as a black box here):

import math
N, a = 15, 7
r, v = 1, a % N
while v != 1:
    v = (v * a) % N
    r += 1
print("order r:", r)                     # 4
half = pow(a, r // 2, N)
print("a^(r/2) mod N =", half)            # 4
f1 = math.gcd(half - 1, N)
f2 = math.gcd(half + 1, N)
print("factors:", f1, f2)                 # 3 5
assert f1 * f2 == N

Output:

order r: 4
a^(r/2) mod N = 4
factors: 3 5

$r = 4$ is even and $a^{r/2} = 4 \not\equiv -1 \equiv 14 \pmod{15}$, so the algorithm succeeds: $\gcd(3,15)=3$, $\gcd(5,15)=5$, and $3 \times 5 = 15$. In a real attack $N$ would be a 2048+ bit RSA modulus and $r$ would come from the quantum subroutine rather than classical trial multiplication, but the classical factor-recovery step shown here is exactly what runs afterward.

Trade-offs and pitfalls

• Confusing Shor's algorithm with Grover's algorithm. Grover's algorithm gives only a quadratic speedup on unstructured search (relevant to symmetric-key primitives and hash functions), roughly halving effective key length; it does not break AES or SHA outright, it motivates doubling key sizes. Shor's algorithm exploits algebraic structure (periodicity) to go from exponential to polynomial time, which is why symmetric crypto survives with larger keys but RSA/ECC do not survive at any classical key size.
• "Just use a bigger key" does not save RSA/ECC. Because Shor's algorithm is already polynomial in $\log N$, increasing the key size only slows the attack polynomially, not exponentially; there is no key-size regime where classical public-key schemes become quantum-safe again.
• "No quantum computer exists yet" is not the same as "no risk yet." Harvest-now-decrypt-later: an adversary can record encrypted traffic today and decrypt it once a sufficiently large fault-tolerant quantum computer exists, which is why migration urgency is driven by data lifetime, not by when a cryptographically relevant quantum computer actually arrives.
• Overstating today's quantum hardware. Current noisy intermediate-scale quantum (NISQ) devices have far too few logical qubits and too much noise to run Shor's algorithm against cryptographically relevant moduli; conflating today's prototypes with the future fault-tolerant threat leads to both complacency and alarmism, neither well-calibrated.

Direct answer

The current families of post-quantum key-establishment candidates are lattice-based (LWE/RLWE/NTRU, e.g. Kyber/ML-KEM), code-based (e.g. Classic McEliece), multivariate (mostly a signature-oriented family in practice), and isogeny-based (e.g. SIKE, now broken). Of these, lattice-based and code-based are the two most directly comparable for KEY ESTABLISHMENT specifically, sitting at nearly opposite ends of the performance-versus-size-versus-confidence trade-off space.

Structured elaboration

Lattice-based (e.g. Kyber/ML-KEM). Performance: very fast, NTT-accelerated polynomial arithmetic on both sides. Key/ciphertext size: small, kilobyte-scale (a public key and ciphertext each roughly one to one-and-a-half kilobytes at typical security levels). Confidence in assumptions: strong worst-case-to-average-case reductions (LWE and RLWE both reduce from worst-case lattice problems such as GapSVP/SIVP, with the RLWE reduction specifically requiring a quantum step) and a large, very active cryptanalytic community, but the assumption itself is comparatively young, mid-2000s for LWE, 2010 for RLWE, relative to number-theoretic assumptions.

Code-based (e.g. Classic McEliece). Performance: extremely fast encryption and decryption, essentially matrix-vector operations plus one efficient algebraic decoder. Key/ciphertext size: the largest public keys of any mainstream PQC KEM family, hundreds of kilobytes to roughly a megabyte depending on the security level, because the public key is a dense, essentially incompressible matrix with no compact algebraic shortcut. Confidence in assumptions: the oldest surviving post-quantum-relevant assumption by a wide margin (McEliece's core construction dates to 1978), with an extraordinarily long unbroken track record against its core structural hardness, exactly why NIST selected Classic McEliece as a standard despite the size cost.

Multivariate (listed for completeness, not deep-dived here). In practice used almost exclusively for SIGNATURES rather than key establishment (Rainbow was the most prominent multivariate NIST candidate); it is worth naming explicitly that multivariate is not really a live option for key exchange the way lattice and code-based schemes are, and Rainbow itself was practically broken in 2022 (Beullens), an important cautionary data point about how quickly a structural weakness can collapse a scheme family's confidence.

Isogeny-based (listed for completeness, not deep-dived here). SIKE (Supersingular Isogeny Key Encapsulation) was a NIST Round 4 alternate candidate valued specifically for having the smallest key sizes of any PQC KEM family, and was completely broken in 2022 (Castryck and Decru's attack, exploiting extra structure available via an auxiliary torsion-point construction) using only a single classical, laptop-scale computation, no quantum computer involved. This is arguably the single most important recent cautionary tale in PQC: a scheme with a plausible-looking hardness argument, small keys, and years of prior cryptanalysis, collapsed almost overnight once the right structural insight was found, directly illustrating why confidence in assumptions is a first-class selection criterion, not an afterthought behind performance and size.

Worked example

The size gap between the two deep-dived families is not folklore, it follows directly from how each public key is built. A lattice public key at dimension $n$ over modulus $q$ needs about $n\lceil\log_2 q\rceil$ bits (one small ring element, see the companion LWE-vs-RLWE worked example); a code-based public key built as an $(n-k)\times k$ parity-check matrix in systematic form needs about $(n-k)\cdot k$ bits, no compact algebraic shortcut available. Using the already-verified Kyber-scale lattice numbers ($n=256$, $q=3329$) against illustrative (not a specific real standardized parameter set) code-based dimensions $n=4000$, $k=3000$, chosen only to show where code-based parameters typically have to live to reach a comparable security margin:

import math
n_lat, q_lat = 256, 3329
lat_bits = n_lat * math.ceil(math.log2(q_lat))
n_code, k_code = 4000, 3000   # illustrative, not a specific real standardized parameter set
code_bits = (n_code - k_code) * k_code
print("lattice pk:", lat_bits, "bits =", round(lat_bits/8/1024, 3), "KiB")
print("code-based pk:", code_bits, "bits =", round(code_bits/8/1024, 1), "KiB")
print("ratio:", round(code_bits/lat_bits, 1))

Output:

lattice pk: 3072 bits = 0.375 KiB
code-based pk: 3000000 bits = 366.2 KiB
ratio: 976.6

Roughly a three-orders-of-magnitude gap, driven entirely by the $(n-k)\cdot k$ (quadratic-in-the-code-parameters) shape of an unstructured parity-check matrix versus the $n\log q$ (linear) shape a ring element gets from its algebraic structure, exactly the mechanism behind the "hundreds of kilobytes to roughly a megabyte" figure named above, not a number to take on faith.

Trade-offs and pitfalls

• Size and performance numbers alone hide the confidence axis. A naive "smallest keys wins" reading of the trade-off table would have favored isogeny-based schemes right up until they were broken; the SIKE collapse is the concrete argument for why any competent scheme-selection exercise weights assumption maturity and cryptanalytic diversity explicitly, not just size and speed.
• "Multivariate" and "code-based" are sometimes conflated as interchangeable "alternative, non-lattice" options. They have essentially nothing in common structurally or in track record, multivariate has had multiple prominent breaks, code-based McEliece has an outstanding record, lumping them together as similar-confidence alternatives is a real, common mistake.
• Public-key size is not the only bandwidth number that matters for key establishment specifically. McEliece's huge public key is a one-time (or infrequent) cost if reused across many sessions, while its ciphertext is comparatively small; a size comparison that only quotes one of the two numbers can misrepresent the real per-handshake bandwidth cost depending on how the KEM is actually used in a protocol.