PQC Research Series — Part 4

Tightness of Security Reductions: Why “Provably Secure” Does Not Mean Deployable

Author: Mayckon Giovani
Date: May 2, 2026
Series: PQC Research Series
Tags: PQC, Formal Methods, Cryptography, Systems

TL;DR

“Provably secure” means: if an adversary breaks scheme $\Pi$, then a reduction algorithm $\mathcal{R}$ can solve an underlying problem $P$. Tightness is the quantitative part of that implication: how much advantage and how much runtime are lost when translating an attack on $\Pi$ into a solver for $P$. If the loss factor is large (non-tight), the proof consumes security margin and forces parameter inflation. In PQC, that inflation is not cosmetic: it amplifies bandwidth, RAM, cache pressure, side-channel surface, and failure probability engineering (sampling, rejection, decoding). A reduction is not the system. It is a translation between problems, and translations have loss. (1) (2) (3)

Key takeaways

• Tightness is an engineering input, not a proof-theory detail: loose reductions force larger parameters to recover the target margin.
• A reduction loss factor $f(\lambda)$ costs about $\log_2 f(\lambda)$ bits of security headroom; at scale, $f$ is often driven by query counts ($q_H$, $q_S$) and multi-user/multi-target settings.
• In ROM/QROM, common tactics (forking, rewinding, oracle programming) frequently inject explicit $q_H$-dependent losses; in QROM those losses are harder to avoid and often less tight. (4) (5) (6)
• “NIST level” labels are not proofs: they are the output of cost models (BKZ/sieving heuristics + hardware assumptions) composed with non-tight reduction chains. (7) (8)
• Formal verification can prove that an implementation refines a spec; it cannot repair a loose reduction or a wrong cost model.

0. Context

The PQC conversation in production environments is still dominated by a shallow equivalence:

scheme is “provably secure” $\Rightarrow$ system is secure.

That inference is invalid even before you talk about side-channels or implementation bugs. Security proofs in modern cryptography are conditional, parameterized, and mediated by reductions. The proof does not say “$\Pi$ is secure.” It says “if $\Pi$ is broken with advantage $\varepsilon$ in time $t$, then $P$ is solvable with advantage $\varepsilon'$ in time $t'$.” Tightness is the gap between $(\varepsilon,t)$ and $(\varepsilon',t')$.

The operational consequence is that reductions consume margin. If the reduction is loose, and you want an operational claim like “128-bit confidentiality margin under my threat model,” you must inflate parameters until the reduction loss is absorbed. In lattice cryptography that inflation is paid in large public keys, large ciphertexts/signatures, higher RAM, higher cache traffic, and larger constant-time code paths. That is where “provably secure” becomes either “deployable” or “a lab artifact.”

1. Problem Statement

Fix a security parameter $\lambda \in \mathbb{N}$. Let $\Pi[\lambda]$ be a scheme (KEM, signature, AKE) instantiated at security parameter $\lambda$ and proven secure by reduction to an underlying problem $P[\lambda]$ (DL, RSA, LWE/SIS, etc).

Let $\mathsf{Game}_\Pi$ be the security game for $\Pi$ (IND-CCA, EUF-CMA, AKE, …). Define the adversary’s advantage as usual:

A reduction-based proof typically has the form:

For every adversary $A$ that breaks $\Pi$ with advantage $\varepsilon$ in time $t$ and at most $(q_H, q_S, \dots)$ oracle queries, there exists an algorithm $B$ that solves $P$ with advantage at least $\varepsilon'$ in time $t'$.

The central quantitative question is: how much security is lost in the translation $A \mapsto B$?

Concretely, suppose the reduction $\mathcal{R}$ builds $B$ with oracle access to $A$:

We want to track:

1. advantage loss: a function $g$ such that
   $$\mathrm{Adv}_{P}(B;\lambda) \;\ge\; g(\mathrm{Adv}_{\Pi}(A;\lambda), \lambda, q_H, q_S,\dots),$$
2. time/query overhead: a function $h$ such that
   $$T(B) \;\le\; h(T(A), \lambda, q_H, q_S,\dots),$$
3. and the implicit assumption: that the deployed implementation matches the model in which $\mathcal{R}$ operates (ROM vs standard model vs QROM; single-user vs multi-user; single-target vs multi-target; leakage-free vs leakage models).

The proof is only operationally meaningful after you translate those functions into:

• concrete parameter sizes,
• a concrete attacker cost model,
• and system constraints (RAM/CPU/network/leakage budgets).

2. Formal Model

2.1 Loss factor as an explicit function

In most cryptographic reductions, advantage loss appears as an inequality of the form:

where $f(\cdot)$ is the loss factor and $\Delta(\lambda)$ collects negligible/statistical terms (abort probability, simulation distance, decryption failure, etc).

Equivalently, rearranging the reduction:

The reduction is tight if $f(\cdot)$ is close to $1$ (or at least a small constant / low-degree polynomial with small coefficients) in the regime that matters, and loose if $f$ is large and grows in the relevant operational parameters.

To talk about tightness without hand-waving, define the tightness ratio:

This definition is deliberately adversarial: it asks “how bad can the translation be” for the class of attacks the reduction claims to cover.

2.2 Concrete security translation: loss eats bits

Operationally we do not talk in “$\varepsilon$.” We talk in “bits.” A common concrete-security stance is:

for any feasible attacker $B$ (where $\kappa$ is an effective bit-security function induced by a cost model).

Combining with the reduction gives:

If you want a scheme-level bound like $2^{-\kappa_\Pi}$, you need:

So the security margin you must provision at the assumption layer is:

This is the cleanest way to say what people usually avoid saying: tightness loss is paid as extra bits, and extra bits are paid as CPU/RAM/bandwidth.

2.3 Time overhead and “tight” lies

Advantage is not the only axis. Many reductions amplify runtime:

and $c(\cdot)$ is sometimes large (multiple invocations, rewinding, “guess the right query index,” etc).

Two reductions can have identical advantage loss but radically different runtime overheads. In PQC deployments, runtime overhead affects parameter selection indirectly: if the reduction requires many replays or rewinds, the “feasible adversary” class changes, and the bound becomes meaningless for the time regime you care about.

This is why exact-security work matters: it forces you to write the constants and the query-dependence instead of burying it in “poly.” Bellare–Rogaway-style exact security is the discipline that makes “provable” actually consumable by engineering. (1)

3. System Constraints

In a clean paper model, the only resource is “polynomial time.” In a deployed system, the constraint set is a vector:

Loose reductions push parameters up, which pushes every component of that budget:

• bandwidth/packetization: larger public keys and signatures fragment handshakes and stress middleboxes;
• RAM/cache: lattice arithmetic is memory-hungry; larger parameters increase cache-miss leakage and constant-time difficulty;
• latency: slow verification/signing affects consensus nodes, IIoT gateways, VPN concentrators;
• entropy: many PQC schemes are randomness-intensive; constrained RNG becomes a first-class failure mode (especially at boot);
• side-channel surface: larger code, more branches, more table accesses, more sampling logic → more leakage opportunities;
• failure probability engineering: rejection sampling, decoding failures, and “abort on overflow” logic must be bounded and monitored.

This is why the engineering question “is the reduction tight?” is not academic. It decides whether the parameters that make the theorem true still fit inside the machine you actually ship.

4. Core Argument / Insight

4.1 Why tightness matters operationally (security margin is a consumable)

Assume you are targeting a concrete security bound $\kappa_\Pi$ against a realistic attacker class. The proof gives you:

Now instantiate the operational reality:

• $q_H$ is not “small.” In protocols, hashes are everywhere: transcript hashing, domain separation, commitments, PRF/KDF usage, key schedules, prehashing, merkleization.
• multi-user and multi-target settings are the norm: a production system runs at scale, across many sessions, many keys, many certificates, many handshakes.

So $f$ is often dominated by terms like:

The punchline: the scheme’s “bit security” is not the assumption’s “bit security.” The proof spends some of it.

To make this concrete, consider a reduction with loss $f = q_H^2$. If a verifier in a large system induces (directly or indirectly) $q_H \approx 2^{20}$ effective oracle interactions per security epoch (not insane in transcript-heavy protocols), then:

Forty bits of headroom is not a rounding error. In lattices, forty bits is the difference between “fits in your MTU / fits in your L2 cache” and “now you have to redesign the protocol framing, the packetization, and the implementation strategy.”

If you do not do this translation explicitly, “provably secure” becomes a word that hides debt.

4.2 Example — Fiat–Shamir losses (tightness is often query-driven)

Fiat–Shamir (FS) is a canonical place where tightness is visible because the proof must account for the adversary’s random oracle queries. This matters in PQC because a large fraction of deployed post-quantum signatures and ZK systems are FS-shaped, and Part 3 already established that QROM makes the proof obligations sharper. (5) (9)

Classical ROM: forking-style losses

In ROM, security proofs for FS-based signatures often rely on the forking lemma (Pointcheval–Stern). The structure is:

1. Run the forger $A$ once, record its oracle queries.
2. Rewind $A$ with the same randomness, but answer one targeted oracle query differently.
3. If you get two valid transcripts with different challenges, extract the witness / discrete log / solution.

This almost always introduces a loss driven by the probability that you “hit the right query” and by the probability that the adversary forges at all. Exact-security analyses make this explicit; for Schnorr-type signatures, the reduction loss is at least linear in the number of hash queries $q_H$, and in many cases that loss is essentially optimal. (4) (10)

At an abstract level, a typical bound has the shape:

depending on the exact extraction strategy, the security definition, and whether you count rewinds in time.

The important engineering fact is not the exact exponent. It is that $q_H$ appears in the denominator. Large protocols induce large $q_H$.

QROM: the loss profile worsens unless you change technique

In QROM, the adversary can query $H$ in superposition. That breaks the classical mental model “record all queries and pick one to program.” Rewinding is not generic; programming the oracle is global; and the simulation must be careful about measurements and disturbance. (3) (11)

That is exactly why the QROM FS literature developed new tools (measure-and-reprogram, compressed oracle, adaptive reprogramming). Those tools exist, but they move the reduction burden into more complex bounds, and tightness is often where the cost shows up. (9) (6)

The practical lesson is not “avoid FS.” The lesson is: treat $q_H$ and reduction tightness as first-class protocol parameters. If you do not control oracle query surfaces (transcript structure, domain separation, protocol framing), you are implicitly paying in security margin.

4.3 Lattice cryptography and non-tight reduction chains

Lattice-based schemes (ML-KEM, ML-DSA, Falcon, and many variants) inherit two distinct kinds of non-tightness:

1. worst-case/average-case reduction losses (approximation factors and parameter regimes),
2. scheme-level transforms (e.g., turning CPA into CCA, ROM/QROM indirections, multi-target scaling).

Worst-case to average-case: approximation-factor inflation

The foundational LWE story is “average-case LWE is as hard as worst-case lattice problems,” but the reduction does not preserve the approximation factor tightly. In a typical regime:

That $\gamma(n)$ term is not a constant. It is an inflation factor in the hardness statement, and it is one of the reasons “security level” estimates are not cleanly derivable from a theorem. (12) (2)

Concrete security is cost-model + reduction chain

At the deployment layer, you do not size parameters from a reduction alone. You size them via:

For lattices, the attack model is dominated by BKZ/sieving-style heuristics, and the mapping to “bits” is done by tools like the lattice estimator. (7) (8)

That means a PQC “security category” is not a theorem. It is a statement about a stack of assumptions:

• the underlying lattice problem hardness (for quantum or classical attackers),
• the accuracy of BKZ/sieving cost models (time vs memory vs parallelism),
• the translation from those costs to your adversary budget,
• plus the reduction loss factors incurred by your scheme transform and protocol embedding.

This is not pessimism. This is the minimum honest structure of the claim.

4.4 The security margin illusion (why “Category 5” can still be fragile)

The industry likes crisp labels: “128-bit,” “Category 3,” “PQC-ready.” In practice:

1. security margins move when cost models move;
2. reductions move when the oracle model changes (ROM vs QROM) or when the environment changes (single-user vs multi-user);
3. deployments move when system constraints force optimizations that violate proof assumptions (biased sampling, caching secrets, skipping constant-time discipline).

Even for standardized schemes, the operational story is dominated by system budgets. ML-DSA (FIPS 204) produces signatures in the kilobyte range, and SLH-DSA (FIPS 205) produces signatures in the multiple kilobyte to tens of kilobyte range depending on parameter set; those are not philosophical costs, they are MTU, log storage, and firmware-update costs. (13) (14)

4.5 Tightness vs deployability (the engineering boundary)

If you want to treat tightness as an engineering artifact, you need to model the whole chain:

flowchart LR
  A["Assumption hardness (P)"] --> B["Reduction loss f(lambda, qH, N, ...)"]
  B --> C["Scheme parameters (sizes, rates, failure bounds)"]
  C --> D["Implementation artifacts (CPU, RNG, memory, constant-time)"]
  D --> E["Operational envelope (latency, MTU, telemetry, incident response)"]

Loose reductions apply pressure at step (B). Pressure then propagates through (C) and (D) into (E). That is the honest reason “provably secure” does not mean “deployable.” Deployment is a boundary condition on parameters; tightness decides whether you can satisfy it without lying.

4.6 Embedded / edge consequences (where loose reductions become safety hazards)

Edge environments (IIoT gateways, Cortex-M-class devices, industrial controllers) do not fail gracefully under parameter inflation:

• RAM is measured in kilobytes; stack spills are crashes.
• cache behavior is not noise; it is a leakage oracle.
• timers are coarse; constant-time costs are amplified.
• entropy at boot is weak; randomness reuse is a realistic failure mode.
• power is a security channel (power analysis) and a reliability constraint (brownouts).

So a reduction that “only” costs $\Delta\kappa$ bits often translates into:

• larger polynomials/NTT buffers,
• more sampling work per signature,
• more memory traffic per verification,
• and a larger surface for side-channel and fault attacks.

This is not theoretical. It is the lived reality of trying to ship PQC in adverse environments.

4.7 Formal verification cannot fix loose reductions

Formal verification is the right tool for proving:

• memory safety / absence of UB,
• refinement between spec and implementation,
• constant-time properties (under a model),
• protocol state-machine invariants,
• deterministic behavior under concurrency constraints.

It cannot prove:

• that the reduction $f(\cdot)$ is tight,
• that your parameter sizing is adequate under the evolving lattice attack landscape,
• that your threat model is aligned with the oracle interface (ROM vs QROM),
• or that your cost model matches the attacker’s hardware and parallelism budget.

Formal verification can ensure you implemented the scheme you specified. It does not validate the meta-assumptions that connect that scheme to a concrete “bits of security” statement. If the reduction is loose, you are still forced into parameter inflation; if the cost model is wrong, you are still exposed; if the threat model is wrong, your proof is still irrelevant.

4.8 Case studies: ML-DSA, Falcon, SLH-DSA (different failure modes, same tightness problem)

ML-DSA (Dilithium lineage): reasonable performance, big artifacts

ML-DSA is engineered for relatively efficient signing/verification compared to many alternatives, but signatures and public keys are large enough to be operationally visible. When tightness losses force parameter inflation, the first thing that breaks is not “the theorem.” It is certificate chains, protocol framing, and embedded memory budgets. (13)

Falcon: smaller signatures, fragile implementations

Falcon’s attraction is compact signatures, but the implementation surface is correspondingly sharper: floating-point hazards, subtle side-channel vectors, and constant-time difficulty can dominate the risk profile. Tightness does not save you if the system cannot preserve the model boundary. (This is why NIST treats Falcon as an additional standardization track rather than “the default.”) (15)

SLH-DSA (SPHINCS+ lineage): conservative assumptions, brutal operational cost

SLH-DSA is attractive as a non-lattice hedge, but it is operationally heavy. Loose reductions are not the main story here; the story is that even with conservative assumptions, the deployment cost is so high that teams will be tempted into unsafe shortcuts (truncation, caching, under-verified paths). Tightness and deployability are still linked: if your system cannot tolerate the overhead, you will violate assumptions. (14)

4.9 The core argument

Tightness determines whether security survives reality.

A proof without a deployable tightness profile is a claim about an object you cannot safely instantiate at scale. In PQC, that gap becomes visible because artifacts are big and the system boundary is tight: bandwidth, RAM, and leakage are not optional.

If you want a professional security claim, you must treat tightness as a first-class design constraint, and you must show how parameter sizing absorbs the loss without collapsing system safety.

5. Implications

1. Reduction loss must be part of the spec. Document $f(\lambda, q_H, N, \dots)$, not just the underlying assumption.
2. Query surfaces must be engineered. Protocol framing, transcript structure, and domain separation are not “implementation details.” They determine $q_H$.
3. Concrete security must be treated as a living artifact. BKZ/sieving and hardware models move; you need telemetry and a reparameterization plan.
4. Hardware-aware co-design is mandatory. If your target includes constrained nodes, assume that parameter inflation will push you into leakage and correctness failure modes.
5. Formal verification remains necessary but insufficient. It closes the spec→binary gap; it does not validate the reduction→bits→ops gap.

6. Continuity Hook

Part 5 will focus on leakage-aware adversarial models and the “constant-time fallacy”: how side-channel interfaces turn clean reductions into irrelevant statements, and how to treat constant-time and erasure as formal properties rather than best-effort hardening.

7. References

Evidence

• Exact-security framing and why constants/tightness matter: Bellare–Rogaway. (1)
• Forking lemma and ROM-era tightness limits in FS-shaped signatures: Pointcheval–Stern; Seurin. (4) (10)
• QROM shifts the proof interface and changes tightness profiles: Boneh et al.; Unruh; Don et al.; Grilo et al. (3) (5) (9) (6)
• Concrete lattice attack cost modeling is heuristic and must be composed with reductions: Chen–Nguyen; the lattice estimator. (7) (8)
• Standardized PQC schemes have nontrivial artifact sizes that turn tightness into operations: FIPS 204 / FIPS 205. (13) (14)

Checklist

• For every claim, write the full implication: attack on $\Pi$ $\Rightarrow$ solver for $P$, with explicit $(\varepsilon,t,q_H,N)$ dependence.
• Compute $\Delta\kappa \approx \log_2 f$ and provision that headroom explicitly in parameter sizing.
• Treat $q_H$ as a protocol parameter (transcript structure, domain separation, aggregation strategy).
• Validate that parameter inflation does not violate system budgets (MTU/RAM/cache) and does not force unsafe shortcuts.
• Keep a reparameterization playbook: telemetry, versioned suite IDs, and removal deadlines for legacy parameter sets.

Further reading

• Bellare–Rogaway, “The Exact Security of Digital Signatures: How to Sign with RSA and Rabin” (1996). (1)
• Pointcheval–Stern, “Security Proofs for Signature Schemes” (EUROCRYPT 1996). (4)
• Seurin, “On the Exact Security of Schnorr-Type Signatures in the ROM” (ePrint 2012/029). (10)
• Boneh et al., “Random Oracles in a Quantum World” (ePrint 2010/428). (3)
• Unruh, “Post-Quantum Security of Fiat-Shamir” (ePrint 2017/398). (5)
• Don–Fehr–Majenz–Schaffner, “Fiat-Shamir in the QROM” (ePrint 2019/190). (9)
• Grilo–Hövelmanns–Hülsing–Majenz, “Tight Adaptive Reprogramming in the QROM” (ePrint 2020/1361). (6)
• Peikert, “A Decade of Lattice Cryptography” (2016). (2)
• Chen–Nguyen, “BKZ 2.0” (ASIACRYPT 2011). (7)
• LWE estimator. (8)
• NIST FIPS 204 (ML-DSA). (13)
• NIST FIPS 205 (SLH-DSA). (14)