Post-Quantum and Lattice-Based Cryptography Questions

Direct answer

$N=701, q=8192$ with Hamming weight $d \approx 72$ matches NTRU-HRSS-701, a real NIST round-3 NTRU submission parameter set. Two structurally different attack vectors are relevant, and the honest security estimate is that this parameter set was designed to keep BOTH above the target margin simultaneously: a lattice-reduction (BKZ) attack on the $2N=1402$-dimensional NTRU lattice, and a combinatorial meet-in-the-middle (MITM) search exploiting the private key's SPARSITY (only $d \approx 72$ of $N=701$ coefficients nonzero) directly, independent of the lattice structure. HRSS's defining design feature, relevant to the decryption-failure question, is that it is constructed to have ZERO decryption failures by design (not merely a small failure probability), a deliberate improvement over earlier NTRU parameter sets.

Structured elaboration

Lattice-reduction attack. The public key $h$ defines a rank-$2N$ lattice (the standard NTRU lattice construction: rows built from $h$'s convolution structure alongside a $qI$ block, exactly the same q-ary lattice CONSTRUCTION FAMILY used to mount primal lattice attacks against plain LWE/RLWE samples, just built from a single polynomial's convolution rather than an explicit LWE sample matrix) containing the short vector $(f, g)$ (the two small private polynomials). BKZ-based reduction searches for this unusually short vector the same way the primal RLWE attack does; the relevant dimension here is $2N=1402$, and the standard core-SVP cost model, which converts a required BKZ blocksize into a bit-security estimate via an exponential cost-in-blocksize relationship, applies directly once a required blocksize is established.

Combinatorial (meet-in-the-middle) attack. Because the private polynomial has only $d$ nonzero coefficients out of $N$, an attacker can attempt to guess it directly rather than attacking the lattice at all. The raw search space (choosing which $d$ of $N$ positions are nonzero) is $\binom{N}{d}$; Odlyzko's meet-in-the-middle technique splits the guess into two halves and matches partial sums, achieving roughly a SQUARE-ROOT speedup over naive search (halving the exponent), a real time-memory trade-off requiring correspondingly large memory to realize, structurally the same flavor of speedup BHT's quantum collision-finding gives over classical birthday search, but achieved here CLASSICALLY via a combinatorial matching technique, not a quantum algorithm.

Which vector is "most relevant" depends on which is cheaper, and real analysis runs both. Neither attack dominates the other in general; a parameter set's real security level is set by the CHEAPER of the two (and by "hybrid" attacks combining both, Howgrave-Graham's approach of lattice-reducing a SUBSET of coordinates and combinatorially searching the rest, which can beat either pure attack alone). NTRU-HRSS-701's designers selected $N,q,d$ specifically to push both the pure-lattice and pure-combinatorial costs, and known hybrids of the two, above the target margin together, not to defeat just one attack family.

Decryption failure and the effect of changing $q$ or $d$. Standard (non-HRSS) NTRU parameter sets have a small but nonzero probability that honest decryption fails, because the polynomial arithmetic can occasionally produce a result outside the range the decoder correctly recovers; HRSS's specific construction (a deliberately chosen parameter relationship rather than a happenstance one) is designed to make this failure probability EXACTLY zero for every valid ciphertext, not merely negligibly small, a meaningfully stronger and simpler-to-reason-about guarantee. Changing $q$ or $d$ independently risks breaking this zero-failure property if the new values fall outside the specific relationship HRSS's analysis relies on, in addition to the more obvious security effects: increasing $d$ (denser secret) increases both the lattice-attack security margin (shorter target vector relative to the lattice, in the appropriate normalized sense) and the combinatorial search space $\binom{N}{d}$, but also increases decryption-failure risk and computational cost per operation; increasing $q$ independent of $N$ weakens the lattice-side security margin (worse $N/\log_2 q$ ratio, the same qualitative relationship described above for the lattice-reduction attack) while giving more numerical headroom against decryption failure.

Worked example

import math

def log2_comb(n, k):
    return (math.lgamma(n + 1) - math.lgamma(k + 1) - math.lgamma(n - k + 1)) / math.log(2)

def log2_multinomial(n, k1, k2):
    n2 = n - k1 - k2
    return (math.lgamma(n + 1) - math.lgamma(k1 + 1) - math.lgamma(k2 + 1) - math.lgamma(n2 + 1)) / math.log(2)

N, d = 701, 72
raw_unsigned = log2_comb(N, d)
raw_signed = log2_multinomial(N, d // 2, d // 2)  # ternary secret, evenly split +1/-1

print(f"N={N}, d={d}, NTRU lattice dimension 2N={2*N}")
print(f"log2 C(N,d) [positions only] = {raw_unsigned:.1f}")
print(f"log2 multinomial(N; d/2, d/2) [positions + signs, balanced ternary] = {raw_signed:.1f}")
print(f"Odlyzko MITM estimate (exponent halved): {raw_signed/2:.1f}")

Output:

N=701, d=72, NTRU lattice dimension 2N=1402
log2 C(N,d) [positions only] = 330.4
log2 multinomial(N; d/2, d/2) [positions + signs, balanced ternary] = 399.0
Odlyzko MITM estimate (exponent halved): 199.5

The raw combinatorial search space (positions and signs) is $2^{399.0}$; Odlyzko's meet-in-the-middle roughly square-roots this to $2^{199.5}$, which sits comfortably above a 128-bit target, indicating the COMBINATORIAL attack vector alone is not the binding constraint for this parameter set (this MITM figure is a standard textbook approximation of the technique's asymptotic behavior, not the fully refined state-of-the-art combinatorial/hybrid attack cost, which is beyond what this simplified calculation captures). Whether the LATTICE-reduction attack (dimension 1402) is more or less binding requires the same core-SVP blocksize-vs-cost analysis described above, which this answer does not re-derive numerically for the NTRU case specifically, consistent with omitting a precise figure this session cannot rigorously pin without the full lattice-estimator tool.

Trade-offs and pitfalls

• Common mistake: analyzing only the lattice attack and ignoring the combinatorial vector, or vice versa. NTRU's sparse-secret structure makes the combinatorial attack a genuinely competitive alternative to the lattice attack, unlike a dense-secret LWE/RLWE instance where the combinatorial vector is not competitive; a security estimate that considers only one vector for an NTRU-style scheme is incomplete by construction.
• Hybrid attacks (lattice-reduce a subset of coordinates, combinatorially search the rest) can beat BOTH pure attacks, which is why real NTRU security estimation (as done by the NTRU submission team and independent analysts) explicitly models the hybrid attack surface, not just the two pure endpoints shown here.
• The zero-decryption-failure property is a SPECIFIC, parameter-relationship-dependent guarantee, not a generic property of "NTRU with small enough $d$." Treating it as automatically preserved under an arbitrary change to $q$ or $d$ is a common and dangerous mistake; HRSS's zero-failure proof is tied to the SPECIFIC values chosen, and any parameter change needs its own decryption-correctness re-analysis, not an assumption that the guarantee "probably still holds."
• The MITM combinatorial estimate shown here is illustrative, not the authoritative state-of-the-art figure. Real combinatorial/hybrid NTRU cryptanalysis (as used in the actual NTRU-HRSS submission's own security analysis) applies further refinements this simplified square-root approximation does not capture; presenting $2^{199.5}$ as "the" combinatorial security level of this scheme would overstate this calculation's precision.

Direct answer

The McEliece cryptosystem builds public-key encryption directly from the hardness of decoding a general linear error-correcting code: the public key is derived from a highly efficiently-decodable, secretly-structured code, classically a binary Goppa code, disguised to look like a generic, structureless linear code. Encryption adds a random error pattern the public description cannot correct; decryption uses secret knowledge of the code's true structure to correct that error and recover the message, a capability no one without the secret can replicate efficiently, since decoding a GENERIC linear code with no known structure is believed hard even for a quantum computer.

Structured elaboration

The error-correcting code. McEliece's security is anchored in a code chosen so decoding it given only the PUBLIC description is computationally hard, while decoding it efficiently is possible given a secret structural description. Classically, this is a binary Goppa code: a code whose parameters, length $n$, dimension $k$, error-correcting capability $t$, are chosen so it can correct up to $t$ errors using an efficient algebraic decoding algorithm (Patterson's algorithm) when its Goppa-polynomial structure is known.

Public and private keys. In the Niederreiter-style formulation Classic McEliece actually standardizes, the private key is the Goppa code's secret structural description (defining polynomial and support set) together with the scrambling transformation used to disguise it; the public key is a scrambled PARITY-CHECK matrix $H$, in systematic form, describing the same code but revealing none of its efficiently-decodable structure. Computationally, $H$ is designed to be indistinguishable from the parity-check matrix of a generic linear code, a SEPARATE hardness assumption (Goppa-code distinguishing) from the decoding hardness assumption below.

How encryption and decryption operate via syndrome generation and decoding. The plaintext is encoded as a length-$n$ error vector $e$ of weight exactly $t$; encryption computes the SYNDROME

using the public parity-check matrix, trivial to compute but, given only $H$ and $c$, extremely hard to invert back to the original weight-$t$ $e$ without the secret structure, exactly the syndrome-decoding problem, addressed cryptanalytically by information-set-decoding (ISD) attacks: Prange's baseline algorithm and its refinements (Stern, MMT, BJMM), all of which guess an error-free information set and solve the resulting linear system, repeated until a guess succeeds. Decryption uses the recipient's secret knowledge of the underlying Goppa code's efficient decoding algorithm to find the unique weight-$t$ error vector $e$ matching the received syndrome $c$, recovering the plaintext directly from $e$'s support (the positions of its nonzero entries).

Strengths. Extremely fast encryption and decryption (matrix-vector multiplication plus one efficient algebraic decoding pass, no expensive number-theoretic operations); an unusually long, essentially unbroken track record on the core structural assumption, going back to 1978, arguably the most conservative and battle-tested assumption in the entire PQC portfolio; resistant to all currently known quantum attacks beyond the generic Grover-style quadratic speedup on information-set decoding.

Weaknesses. The public key is enormous, hundreds of kilobytes to roughly a megabyte depending on the target security level, because the disguised matrix has no compact algebraic shortcut the way a lattice scheme's structured ring element does, by a wide margin the largest public key of any mainstream NIST PQC KEM. Key generation is comparatively expensive, and there is no analogous compact SIGNATURE scheme built on the same core assumption with competitive size, the McEliece assumption has historically been much more naturally suited to encryption/KEM constructions than to signatures.

Worked example

The structured-vs-unstructured decoding gap is concrete on a tiny real error-correcting code. Implementing a full binary Goppa decoder is out of scope for a compact demo, so this uses the $[7,4]$ Hamming code instead, a small, genuine error-correcting code with its own efficient syndrome decoder, standing in for the same mechanism McEliece relies on:

H = [
    [1,0,1,0,1,0,1],
    [0,1,1,0,0,1,1],
    [0,0,0,1,1,1,1],
]
n = 7

def syndrome(H, e):
    return tuple(sum(row[i]*e[i] for i in range(n)) % 2 for row in H)

e_true = [0,0,0,0,1,0,0]           # secret error, weight 1 (this code corrects up to 1 error)
s = syndrome(H, e_true)
print("syndrome:", s)

# STRUCTURED decoder: knowing this H's column layout, syndrome bits ARE the error position
# in binary (a classic Hamming-code property) -> O(1) lookup, the analogue of McEliece's
# secret Goppa-code decoder.
columns = [tuple(H[r][c] for r in range(3)) for c in range(n)]
pos_from_syndrome = {col: i for i, col in enumerate(columns)}
structured = [0]*n
structured[pos_from_syndrome[s]] = 1
print("structured decoder:", structured, "correct:", structured == e_true)

# UNSTRUCTURED decoder: given ONLY H and the syndrome, search candidate error vectors --
# the generic approach an attacker without the secret structure is reduced to (information-
# set decoding's regime at real McEliece sizes; trivial here at n=7).
for pos in range(n):
    cand = [0]*n
    cand[pos] = 1
    if syndrome(H, cand) == s:
        print("brute-force decoder:", cand, "found after", pos+1, "candidates")
        break

Output:

syndrome: (1, 0, 1)
structured decoder: [0, 0, 0, 0, 1, 0, 0] correct: True
brute-force decoder: [0, 0, 0, 0, 1, 0, 0] found after 5 candidates

Both decoders agree, but they get there completely differently: the structured decoder uses a direct lookup exploiting the code's known internal structure (position-in-binary), while the brute-force decoder searches candidate error patterns with no shortcut, trivial to enumerate at $n=7$, but the same search at real Classic McEliece parameters (thousands of positions, dozens of errors) is exactly the information-set-decoding problem the scheme's security rests on: identical syndrome-decoding TASK, only the availability of the secret structure separates an instant decode from an infeasible search.

Trade-offs and pitfalls

• Two separate hardness assumptions are doing work here, not one. McEliece's security needs BOTH the Goppa-code-distinguishing assumption (the public matrix is computationally indistinguishable from a generic random-linear-code matrix) AND the syndrome-decoding hardness assumption; conflating them into "McEliece is hard because decoding is hard" skips a genuinely separate assumption that also has to hold.
• Structured variants that shrink the key have repeatedly run into trouble. Several proposals over the years have tried to add extra algebraic structure, quasi-cyclic or similarly patterned matrices, specifically to shrink McEliece's large public key, and multiple such structured variants have been broken by attacks exploiting exactly the added structure; this is precisely why Classic McEliece deliberately keeps an unstructured, random-looking Goppa code despite the size cost, a considered trade-off, not an oversight.
• The scrambled public matrix "looking random" is the entire point, not a coincidence to be suspicious of. Candidates sometimes intuitively distrust a public key that "looks like nothing," expecting visible structure the way an RSA modulus or an elliptic-curve point has recognizable form; McEliece's public key deliberately has NO visible structure, that is what indistinguishability from a random code means, and it is the correct, intended state.

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

A security reduction is a proof technique showing that if an adversary can break a cryptographic scheme, that adversary can be used, as a subroutine inside another algorithm, to solve a problem believed to be hard, such as LWE or SIS. Reductions matter for post-quantum schemes specifically because the field is comparatively young: security is asserted relative to hardness assumptions rather than proven from first principles, and a reduction is what ties a scheme's concrete security back to those assumptions in a checkable way. The reduction's tightness, whether it preserves the adversary's advantage closely or loses a large factor, determines how literally a "128-bit secure" label should be trusted.

Structured elaboration

Tight vs. non-tight. A reduction $B$ that uses adversary $A$ (breaking the scheme with advantage $\epsilon_A$) to solve the hard problem gives a bound of the form

for some loss factor $L$. A tight reduction has $L=O(1)$, independent of the security parameter or query budget, so a break of the scheme translates almost directly into a break of the assumption. A non-tight (loose) reduction has $L$ growing with, for example, the number of oracle queries $Q$ an adversary is allowed (common in signature reductions using the forking lemma, where $L$ can scale like $Q$ or $Q^2$), meaning the scheme's proven security is meaningfully weaker than the assumed problem's security once the loss is accounted for.

Practical implications for parameter selection. If a reduction loses a factor $L$ and the design target is $\lambda$ bits of scheme security, the underlying hard-problem instance must actually be set to roughly $\lambda + \log_2 L$ bits to compensate (worked example below). Parameter selection that only looks up "LWE is $\lambda$-bit secure at these parameters" without checking the reduction's loss factor silently under-provisions security whenever the reduction is loose.

Practical implications for confidence in a scheme. A tight reduction to a well-studied problem is close to the strongest assurance a scheme can offer short of a first-principles proof: an attacker who breaks the scheme has, almost for free, also broken the assumption. A loose reduction still provides genuine assurance, but practical confidence then rests partly on cryptanalytic experience against the scheme's specific construction, not purely on the assumption's hardness. Several NIST PQC lattice signature schemes have reductions that are heuristic or non-tight in the deployed parameter regime, which is why their published parameter sets carry a deliberate margin beyond the bare reduction's requirement.

Random-oracle model (ROM) vs. standard model. Many efficient reductions, particularly Fiat-Shamir-style constructions common in lattice signatures, only go through if a hash function is modeled as a truly random oracle. This is a heuristic: no real hash function is a random oracle, and there exist contrived schemes provably secure in the ROM that are provably insecure for every real instantiation of the hash function (Canetti, Goldreich, and Halevi's 1998 uncomputability separation). Standard-model reductions avoid this idealization at the cost of being harder to construct and often less efficient, which is why high-assurance contexts (long-lived root keys, formally verified systems) sometimes explicitly favor standard-model constructions despite the efficiency cost, while most deployed PQC signatures accept the ROM heuristic given decades without it failing for well-designed schemes.

Worked example

The loss-factor arithmetic is simple exponent bookkeeping, worth doing explicitly rather than eyeballed. Suppose a reduction loses $L=2^{40}$ (from a forking-lemma bound on $Q=2^{40}$ hash queries), targeting $\lambda=128$ bits of scheme security:

target_adv_exp, loss_exp = 128, 40
print(target_adv_exp + loss_exp)   # 168

The underlying hard-problem instance needs roughly 168-bit hardness, not 128-bit, to deliver a genuinely 128-bit-secure scheme once this reduction's loss is accounted for. A "128-bit security" claim resting on this reduction without inflating parameters overstates its assurance by exactly the loss factor.

Trade-offs and pitfalls

• "A reduction exists" is not a binary pass/fail check. The most common mistake is treating "the scheme has a proof" as sufficient without checking tightness and against what problem; a reduction with an exponential loss factor provides far less than a tight reduction to a well-studied worst-case-hard problem.
• Asymptotic vs. concrete security. Reductions are usually stated asymptotically; real parameter selection needs the concrete loss factor as an explicit number, exactly the distinction the worked example makes.
• Heuristic security is common and should be labeled as such. Several practical lattice signature schemes rely on reductions that are non-tight or partly heuristic at deployed parameters; NIST's selected schemes compensate with conservative margins validated by extensive cryptanalysis rather than resting purely on the formal bound.

Direct answer

Recommend a binary Goppa code with $n = 3488$, $t = 64$, giving a code dimension $k = n - mt = 3488 - 12 \times 64 = 2720$ (using field-extension degree $m = \lceil \log_2 n \rceil = 12$, the smallest $m$ with $2^m \ge n$), matching Classic McEliece's actual NIST-submitted mceliece348864 parameter set exactly. Justification: this follows the same derive-and-cross-check methodology throughout, computing Prange's classical information-set-decoding (ISD) work factor directly from $(n,k,t)$ and confirming it clears the 128-bit target with the margin expected once the gap to the stronger Stern/BJMM attacks is accounted for.

Structured elaboration

Why $n=3488, t=64$ specifically, not some other pair achieving the same $(n,t)$ "shape." Classic McEliece's actual NIST submission fixed this exact pair for its Category 1 (roughly AES-128-equivalent) parameter set after extensive analysis against the full ISD attack family (not just Prange); recommending the SAME pair here is a deliberate choice to anchor this proposal to a value that has survived multiple rounds of public cryptanalysis, rather than proposing an untested novel pair that merely "looks" similar in scale.

Code family: binary Goppa, not a structured alternative. Binary Goppa codes are chosen specifically because they have NO known efficient distinguisher separating a disguised Goppa parity-check matrix from a matrix of a truly random linear code (the "Goppa-code-distinguishing" assumption, a SEPARATE hardness assumption from ISD hardness itself, both of which must hold). Structured code families proposed to shrink the key (quasi-cyclic or quasi-dyadic variants, for instance) have repeatedly been broken by attacks exploiting exactly the added structure; Classic McEliece deliberately keeps the unstructured, "looks like nothing" property despite its size cost, a considered trade-off documented across multiple rounds of the standardization process.

Key size and performance consequence. Public key size for a systematic-form parity-check matrix is $k(n-k)$ bits (the free, unstructured part of the matrix); this is the direct cost of choosing an unstructured code, hundreds of kilobytes for any Category-1-or-above parameter set, the largest public key of any mainstream NIST PQC KEM family. In exchange, encryption and decryption are extremely fast (matrix-vector multiplication plus one efficient algebraic decode, no expensive number-theoretic operations), and the ciphertext itself is comparatively small (a syndrome vector of length $n-k$ bits, not the full $n$-bit codeword), so the SIZE cost of this scheme is concentrated almost entirely in the public key, not in per-message bandwidth, an important distinction for any protocol where the key is exchanged once and reused across many messages.

Worked example

import math

def log2_comb(n, k):
    return (math.lgamma(n + 1) - math.lgamma(k + 1) - math.lgamma(n - k + 1)) / math.log(2)

def derive_k(n, t):
    m = math.ceil(math.log2(n))
    return n - m * t, m

def prange_log2_workfactor(n, k, t):
    return log2_comb(n, k) - log2_comb(n - t, k)

n, t = 3488, 64
k, m = derive_k(n, t)
wf = prange_log2_workfactor(n, k, t)
pk_bits = k * (n - k)
print(f"n={n}, t={t}, m={m}, k={k}")
print(f"Prange classical log2(workfactor) = {wf:.1f}")
print(f"public key size = {pk_bits} bits = {pk_bits/8/1024:.1f} KiB")

Output:

n=3488, t=64, m=12, k=2720
Prange classical log2(workfactor) = 142.8
public key size = 2088960 bits = 255.0 KiB

The derived $k=2720$ matches the officially published mceliece348864 dimension exactly (cross-verified live against NIST's own submission data). Prange's work factor of $2^{142.8}$ sits comfortably above the 128-bit target: this margin is expected, not evidence of over-conservatism, since Prange is the WEAKEST ISD variant and the officially targeted 128-bit level is calibrated against the stronger Stern/BJMM attacks, which reduce this Prange baseline by a polynomial-in-the-exponent factor this simplified calculation does not itself compute. The resulting $\approx 255$ KiB public key is the direct, unavoidable cost of the unstructured-code choice: over 150 times larger than a comparable lattice-based KEM's public key (roughly 1 to 1.5 kilobytes at a similar security level), the central performance trade-off this scheme accepts in exchange for its unusually long, largely unbroken track record on the core hardness assumption.

Trade-offs and pitfalls

• Common mistake: reporting the Prange work factor as the scheme's actual security level. As with any Prange-based estimate, Prange is a valid weakest-attack baseline, never the number to quote as "the" security level; the real evaluation requires the strongest known ISD variant (BJMM and successors), which this simplified calculation does not itself compute.
• 255 KiB is a real deployment cost, not a rounding error, for any protocol that cannot amortize the public key across many uses. A one-shot ephemeral key exchange pays this cost on every single handshake; a scheme designed for long-lived, reused keys (a static server key fetched once and cached) amortizes it far better. Parameter selection in isolation cannot answer "is this size acceptable," that depends entirely on the deployment's specific key-reuse pattern.
• Common mistake: assuming a smaller $t$ (fewer correctable errors) is a straightforward way to shrink the public key without a security cost. Since $k = n - mt$, DECREASING $t$ for fixed $n$ INCREASES $k$, which increases $k(n-k)$'s value up to the point where $k=n/2$ maximizes it, so the size-vs-security relationship is not monotonic in the simple direction intuition suggests; any proposed parameter change needs the full $(n,k,t)$ recomputed and re-evaluated together, not a single value tweaked in isolation.
• Two separate hardness assumptions underpin this recommendation, and parameter guidance addresses only one of them. The Prange/ISD work-factor calculation addresses SYNDROME-DECODING hardness; it says nothing about the SEPARATE Goppa-code-distinguishing assumption (that the disguised public matrix is indistinguishable from a generic random-code matrix), which is why deliberately choosing the conservative, unstructured Goppa family (rather than a smaller but structured alternative) is itself part of the security recommendation, not a detail orthogonal to it.