PQC Research Series — Part 1

Formal Threat Models for Post-Quantum Systems

Author: Mayckon Giovani
Date: April 24, 2026
Series: PQC Research Series
Tags: PQC, Formal Methods, Cryptography, Systems

0. Context

This article formalizes the adversary models that actually sit underneath “post-quantum security” claims.

Most production discussions about PQC are framed as a primitive replacement problem: swap an ECDH group for an ML-KEM parameter set; swap RSA/ECDSA for ML-DSA or SLH-DSA; keep the rest unchanged.

That framing is incomplete. A security statement is only meaningful relative to a threat model that specifies:

• what computation model the attacker runs (classical PPT vs quantum polynomial-time),
• what interfaces the attacker has (classical vs quantum/superposition oracle access),
• what resources are bounded (time, memory, and query budgets),
• and what the system boundary is (what is and is not coherently queryable, what leaks, what must be erased).

Post-quantum migration fails silently when these are left implicit. This is not philosophical; it is a specification error. In particular, the Quantum Random Oracle Model (QROM) is not “ROM but stronger.” It is a different oracle interface and forces different proof techniques, different failure modes, and different deployment assumptions. (1)

1. Problem Statement

Let $\lambda \in \mathbb{N}$ be a security parameter. A cryptographic system $\Pi$ is a set of algorithms and stateful components composed into a protocol:

We want a threat model that supports machine-checkable security claims of the form:

where:

• $\mathcal{M}$ is the oracle model / interface regime (e.g., ROM vs QROM),
• $A$ is an adversary whose capabilities belong to an admissible class $\mathcal{C}(\lambda)$,
• $\mathrm{Adv}$ is the advantage of $A$ in some security game (IND-CCA, EUF-CMA, AKE, etc),
• and $\mathcal{C}(\lambda)$ encodes explicit resource bounds.

The core modeling problem is to define $\mathcal{C}(\lambda)$ such that it captures the operational adversary we must assume in PQC deployments:

1. Classical adversaries (probabilistic polynomial-time, classical oracle access).
2. Quantum adversaries with classical oracle access (quantum computation, but the environment only answers classical queries).
3. Quantum adversaries with quantum oracle access (superposition queries), which induces QROM-style analysis.

Then we must define a resource vector that is explicit enough to be operationally relevant:

where $T$ is time, $M_c$ is classical memory, $M_q$ is quantum memory (qubits), $q_H^c$ and $q_H^q$ are classical vs quantum queries to a hash/oracle $H$, and $\mathcal{O}$ is the set of other interfaces (e.g., signing oracle, decapsulation oracle, network endpoints).

The reason to insist on this vector is that PQC security often collapses into “it’s 128-bit” language without any statement about what costs 128-bit under quantum constraints, and which part of the system gives the attacker those costs.

2. Formal Model

2.1 Notation and conventions

• $\lambda$ is the security parameter.
• $\ell(\lambda)$ is an output length (typically $\ell(\lambda)=\lambda$ or $\ell(\lambda)=2\lambda$).
• $H: \{0,1\}^{\ast}\rightarrow \{0,1\}^{\ell(\lambda)}$ denotes a random oracle.
• $\mathrm{negl}(\lambda)$ denotes a negligible function.
• “PPT” is probabilistic polynomial-time.
• “QPT” is quantum polynomial-time (uniform family of poly-size quantum circuits).

I will write security games in the standard game-based style: the challenger samples secrets, exposes oracles, the adversary outputs a bit, and advantage is the distinguishing gap.

2.2 Classical adversary (PPT + classical oracle access)

A classical adversary $A$ is a PPT algorithm. In the ROM, $A$ can query the random oracle $H$ on classical inputs:

Formally, $A$ is an oracle algorithm $A^{H,\mathcal{O}}(1^\lambda)$ that can make at most $q_H^c(\lambda)$ classical queries to $H$ and at most $q_O(\lambda)$ classical queries to each oracle $O\in\mathcal{O}$, running in time $T(\lambda)$.

The ROM proof toolbox relies on:

• lazy sampling (define $H(x)$ on first query),
• programming (set $H(x^\star)$ to a chosen value),
• and transcript extraction via recorded queries.

These are not generic moves in the quantum setting.

2.3 Quantum adversary (QPT) with classical oracle access

The first quantum strengthening is computational, not interface.

Let $A_Q$ be a QPT adversary. Concretely, for each $\lambda$, $A_Q$ is a quantum circuit $C_\lambda$ with polynomially many gates, acting on a polynomial number of qubits, with access to classical oracles.

In this model, $A_Q$ can run quantum algorithms (Shor, Grover, quantum walks, etc.) but can only query the oracle $H$ by measuring an input $x$ and receiving a classical output $H(x)$. This is a meaningful model for certain deployments where an oracle is only accessible through an inherently classical interface (e.g., rate-limited remote services that do not provide coherent access).

However, it is not a safe default for hash functions, because a public hash function is not a remote service: it is an algorithm. If its description is public, a quantum adversary can implement it coherently. That is why QROM exists.

2.4 Quantum adversary with quantum oracle access (QROM)

In QROM, the random oracle is not an abstract lookup table that returns values. It is a unitary transformation that can be queried on superpositions of inputs. (1) (2)

Fix an output length $\ell(\lambda)$. Let $H$ be sampled uniformly at random from all functions $\{0,1\}^{n}\rightarrow \{0,1\}^{\ell(\lambda)}$ for some fixed input length $n$ (or use a prefix-free encoding to reduce variable-length inputs to fixed-length blocks).

Define the oracle unitary:

where $\oplus$ is bitwise XOR in $\{0,1\}^{\ell(\lambda)}$ (and $|y\rangle$ is an $\ell(\lambda)$-qubit register).

A QROM adversary $A_Q$ is allowed to interleave its own unitaries $U_1,\dots,U_k$ with calls to $U_H$:

for at most $q_H^q(\lambda)$ oracle calls. The final measurement produces the adversary’s output.

This single change (from classical query to coherent oracle access) breaks the ROM reduction move “record all random oracle queries and reprogram one point,” because:

• there is no classical transcript of queries (queries are quantum states),
• measuring the query register disturbs the adversary’s state,
• and the adversary can query many points at once in a superposition state.

This is not a nuisance detail. It is a structural change in what “knowing $H(x)$” means.

2.5 Resource accounting: queries, memory, time

The statement “secure against quantum adversaries” is incomplete until we pin down the resource regime.

In practice, we need a resource accounting that is explicit enough to:

1. map to parameter choices,
2. map to operational constraints (HSM/IIoT/embedded),
3. survive protocol composition.

I use the following canonical resource vector:

Interpretations:

• $T$ (time) is gate complexity: the number of elementary quantum gates in the circuit description of $A$ (or a conservative upper bound).
• $M_q$ is the maximum number of qubits kept coherent at any time (quantum workspace + oracle query registers).
• $M_c$ is classical memory (bits or words) used by $A$.
• $q_H^q$ is the number of quantum oracle calls to $U_H$.
• $q_H^c$ is the number of classical evaluations of $H$ (which a quantum adversary can simulate by measuring its input register and computing).
• other $q_O$ correspond to protocol or hardware interfaces (e.g., a signing oracle can represent a compromised signing service; a decapsulation oracle can model error-oracle exposure; a network oracle can model active MitM capability).

This matters because quantum attacks are often query-bounded.

For example, for brute-force search in an unstructured space of size $N=2^k$, Grover’s algorithm achieves $O(\sqrt{N})$ oracle queries and is optimal up to constant factors. (3) (4)

Thus, when a system claims “$k$-bit security,” the model must specify what oracle is being queried and how the query complexity maps to the system’s real interface.

2.5.1 Adversary classes as explicit sets

Define the admissible adversary classes as sets parameterized by $\lambda$ and by a budget vector $B$:

Then:

and, crucially,

where $A$ is explicitly allowed to invoke $U_H$ coherently.

This is the right shape for engineering because it makes the theorem boundary a function of explicit parameters:

If you cannot state $B$, you do not have a security target; you have a slogan.

2.6 A concrete game: QROM-EUF-CMA for Fiat–Shamir signatures

It is useful to anchor the model in a game where the ROM/QROM difference is not cosmetic.

Consider a Fiat–Shamir-style signature scheme $\Sigma_{\textsf{FS}}$ constructed from a $\Sigma$-protocol with hash $H$ providing the challenge.

The (simplified) QROM-EUF-CMA game is:

1. Challenger samples $(pk,sk)\leftarrow \textsf{KeyGen}(1^\lambda)$.
2. Adversary $A_Q$ gets $pk$ and oracle access to:
   • quantum random oracle $U_H$,
   • classical signing oracle $\textsf{Sign}(sk,\cdot)$.
3. $A_Q$ outputs $(m^\star,\sigma^\star)$.
4. $A_Q$ wins if $\textsf{Verify}(pk,m^\star,\sigma^\star)=1$ and $m^\star$ was not asked to $\textsf{Sign}$.

The QROM complication is that the reduction cannot simply “look at the query $H(\text{transcript})$ where the adversary fixed the challenge,” because there is no discrete query event.

This is why QROM proofs for Fiat–Shamir require specialized techniques (e.g., measure-and-reprogram, compressed oracle methodology). (5) (6) (2)

2.7 A reprogramming bound (why QROM proofs are delicate)

A common ROM move is to replace $H$ with $H'$ that differs on one input $x^\star$, and argue the adversary cannot notice. In QROM, this needs explicit query-bounds.

One generic form of bound (suppressing constants and depending on the exact modeling) is that for an adversary making at most $q$ quantum queries to a random function, the distinguishing advantage between two oracles that differ on a single point is upper-bounded on the order of:

The point is not the exact constant; the point is the structure:

• the bound depends quadratically on the quantum query budget,
• it depends exponentially on the output length,
• and therefore you cannot reprogram “for free.”

This is what forces QROM proofs to explicitly track $q_H^q$ and forces systems engineers to treat oracle query count as an explicit resource assumption, not an implicit “polynomial.”

3. System Constraints

Threat models that stop at “PPT vs QPT” are insufficient for systems work. They do not distinguish interfaces, and interfaces are where systems break.

I model system constraints as an explicit boundary condition on what the adversary can query coherently and what the adversary can only observe classically.

3.1 Interface classification: what is quantum-queryable?

In an actual PQC system, we have multiple classes of “oracles,” and only some are plausibly quantum accessible.

Let $\mathcal{I}$ be the set of interfaces exposed by the system:

For each interface $I\in\mathcal{I}$, define an access mode:

Examples:

• $\textsf{Hash}$ is typically quantum (public deterministic algorithm, implementable coherently).
• $\textsf{Net}$ is typically classical (network endpoints do not provide coherent oracle access).
• $\textsf{Sign}$ is classical unless the signing key is fully exposed in a way that allows coherent queries (rare in real systems; if it happens you already lost).
• $\textsf{Leak}$ is classical (side-channel leakage is measured data).

This interface typing lets you state something precise:

The adversary is QPT overall, but only has quantum access to $\textsf{Hash}$ and $\textsf{KDF}$; all other interfaces are classical.

Without this typing, people accidentally assume QROM where it is irrelevant, or worse, assume ROM where it is unsafe.

flowchart LR
    A["Adversary A_Q (QPT)"] -->|quantum queries q_H^q| H["Hash/KDF (U_H)"]
    A -->|classical messages| N["Network / protocol endpoints"]
    A -->|classical oracle queries| S["Signing / decapsulation services"]
    A -->|observations| L["Leakage channel (timing/cache/power)"]
    H --> A
    N --> A
    S --> A
    L --> A

3.2 Bounded coherence as a first-class constraint

Even when an interface is quantum accessible in principle, coherence budgets matter.

Let $\tau$ be a coherence-time parameter and let $M_q$ be the coherent qubit budget. For many practical quantum attack pipelines, the feasible query depth is bounded by error correction overhead:

for some system-dependent function $f$.

Pure complexity-theoretic models intentionally abstract this away. Systems engineering cannot.

If you are selecting parameters for a protocol deployed over a 10-year lifecycle, you need to express the security target in the form:

The budget must be stated because it is what “$k$-bit security” cashes out to in a world where quantum resources are not symmetric with classical ones.

3.3 Determinism, erasure, and state

PQC deployments often increase state volume: larger public keys, larger ciphertexts, more transcript data. That increases the amount of secret-dependent material that must be erased to preserve forward secrecy and reduce post-compromise exposure.

I treat erasure as an explicit system component:

and I require it as a proof obligation for any security claim that depends on ephemerality.

This is not theoretical hygiene. If your formal model assumes ephemeral secret keys are erased but your implementation does not actually erase (or cannot erase because of allocator behavior, crash dumps, or debug cores), then your security claim is false even if the primitive is post-quantum.

3.4 Leakage: the missing axis in “post-quantum” claims

The standard QROM definition does not model side channels. Real systems leak.

To make this explicit, introduce a leakage oracle $\mathcal{L}$:

where $s$ is secret state, $x$ is an input/control variable, $g$ is a leakage function (timing, cache, power), and $\eta$ is noise.

Then “post-quantum secure” becomes a claim about the joint model:

This is where academic proofs and systems reality diverge. Most PQC breakages in deployed environments will not be lattice breaks; they will be:

• RNG failures,
• side-channel leakage,
• state reuse,
• parser differentials,
• and operational misconfiguration.

If the threat model does not represent $\mathcal{L}$, it is incomplete for high-assurance work.

4. Core Argument / Insight

The classical-to-quantum transition breaks systems in one predictable way: it invalidates implicit assumptions.

If you read a security proof and you cannot locate (in the statement of the theorem) all three of the following:

1. the computation class of $A$ (PPT vs QPT),
2. the oracle access mode for each interface (classical vs quantum),
3. the resource bounds that the reduction depends on (especially $q_H^q$, $M_q$, and time depth),

then the proof is not a usable engineering artifact. It is a conditional statement missing its conditions.

This is not pedantry. It is the only way to avoid shipping “post-quantum” protocols that:

• are proven secure only in ROM but instantiated with public deterministic hash functions (making QROM the relevant model),
• assume ephemerality without enforcing erasure,
• assume bounded query counts while building an interface that enables unbounded offline hashing,
• or assume an adversary that cannot exploit time–memory tradeoffs while deploying hardware that makes those tradeoffs favorable.

4.1 Why QROM is structurally different from ROM

ROM is a model where the adversary sees a sequence:

QROM is a model where the adversary’s interaction with $H$ is a sequence of unitary evolutions; there is no classical transcript. The adversary’s “knowledge” about $H$ is encoded in a quantum state that can represent correlations across exponentially many inputs.

That destroys reduction strategies that depend on transcript surgery.

Zhandry’s compressed oracle methodology exists because it is the replacement for lazy sampling in the presence of quantum queries: you need a way to represent “what the adversary has learned” without measuring. (2)

4.2 A system-level invariance principle

For systems work, I enforce the following invariance principle:

A security claim must be invariant under changes in implementation that preserve the modeled interfaces, and must explicitly fail (by assumption violation) under changes that expand the interface.

Concretely:

• If your model assumes $\mathrm{mode}(\textsf{Hash})=\textsf{classical}$, then “replace $H$ by a public deterministic hash function” is an interface expansion (now quantum access is plausible), and your proof obligation must be revisited.
• If your model assumes erasure, then “switch allocators and stop zeroizing” is an assumption violation, and your proof obligation must fail by construction.

This is how you prevent the common failure where a proof remains “true” on paper while the deployed system drifts out of the theorem’s scope.

5. Implications

5.1 For protocol specifications: publish a threat-model matrix

Every PQC-facing protocol spec should publish a threat-model matrix that looks like:

If this table is absent, the system is underspecified.

5.2 For primitive selection: “quantum security level” is not a scalar

NIST-style “categories” are useful, but operationally you must still define what the attacker can do:

• Is the hash used in Fiat–Shamir modeled in QROM?
• Are you relying on tightness bounds that depend on $q_H^q$?
• Are you assuming that the attacker cannot get decryption/decapsulation oracles (in practice: error oracles)?

If a proof gives a reduction of the form:

then your deployment must treat $q_H^q$ as a real security budget variable, not “some polynomial.”

5.3 For high-assurance systems: integrate system constraints as obligations

For security-critical deployments (IIoT, control planes, global backends, blockchain consensus):

• add explicit erasure obligations,
• model leakage oracles for realistic side channels,
• model concurrency/state reuse constraints,
• and enforce configuration invariants (no silent downgrade of PQ components).

Otherwise “post-quantum” becomes a label attached to primitives while the system remains vulnerable through the same operational paths that already break classical systems.

6. Continuity Hook

This leads directly to the next problem: hardness assumptions and parameter regimes under quantum constraints are not just “LWE but with a quantum attacker.”

Part 2 will formalize a lattice-based hardness statement (LWE / Module-LWE) under QPT adversaries and connect it to a systems-meaningful cost model: time depth, memory, and realistic attack surfaces (including where the quantum speedups actually apply and where they do not).

7. References

• Boneh, Dagdelen, Fischlin, Lehmann, Schaffner, Zhandry — Random Oracles in a Quantum World. (eprint.iacr.org/2010/428) (1)
• Grover — A fast quantum mechanical algorithm for database search. (arXiv:quant-ph/9605043) (3)
• Bennett, Bernstein, Brassard, Vazirani — Strengths and Weaknesses of Quantum Computing (quantum query lower bounds). (arXiv:quant-ph/9701001) (4)
• Unruh — Post-Quantum Security of Fiat–Shamir. (eprint.iacr.org/2017/398) (5)
• Don, Fehr, Majenz, Schaffner — Security of the Fiat–Shamir Transformation in the Quantum Random-Oracle Model. (eprint.iacr.org/2019/190) (6)
• Zhandry — How to Record Quantum Queries, and Applications to Quantum Indifferentiability (compressed oracle methodology). (eprint.iacr.org/2018/276) (2)
• Watrous — Zero-Knowledge Against Quantum Attacks (quantum rewinding constraints). (PDF) (7)