Security Models in
Quantum Cryptography

What a Security Proof Actually Says

A security proof in cryptography is a mathematical reduction: it shows that if an efficient adversary can break the protocol, then an efficient algorithm can solve some problem that is assumed hard (e.g., factoring, Learning With Errors). The proof does not guarantee absolute security — it transfers the problem of breaking the protocol to the assumed-hard problem. If that assumption is later broken, the proof tells us nothing.

Three ingredients of every proof: (1) A security model that specifies what the adversary is allowed to do, (2) a security definition that specifies what it means to win, and (3) a reduction that transforms any adversary breaking the definition into a solver for the hard problem. Changing any of these three changes what the proof guarantees.

Quantum security proofs introduce new challenges: Classical reductions rely on techniques — such as rewinding a prover, programming a random oracle, or rewinding a simulator — that do not transfer to quantum adversaries. Quantum measurement disturbs state. Copying a quantum state is forbidden by no-cloning. Superposition queries to a hash function extract information inaccessible to classical adversaries. Each of these forces re-examination of classical proof machinery.

Trace Distance — The Fundamental Security Measure for QKD

For quantum key distribution, security cannot be measured purely by mutual information (the classical metric). Eve may hold a quantum state entangled with the key and delay her measurement until after the key is used — at which point classical information theory provides no bound on what she can learn. The correct measure is trace distance.

Given the joint state ρ_KE of the key K and Eve's system E at the end of the protocol, and the ideal state τ_K ⊗ ρ_E where the key is perfectly uniform and independent of Eve, composable security requires:

½ ‖ ρ_KE − τ_K ⊗ ρ_E ‖₁ ≤ ε

This trace distance bound ε quantifies how distinguishable the real key state is from a perfect key. Crucially, it bounds Eve's advantage in any task she might use the key for — including tasks involving her quantum memory and future quantum measurements. This makes it the correct metric for composable security proofs, unlike mutual information which only bounds what Eve can extract at a single fixed point in time.

Practical significance: BB84 with privacy amplification achieves ε exponentially small in the privacy amplification length. The finite-key regime — where Alice and Bob exchange a finite number of quantum states — requires careful accounting of smooth min-entropy, statistical estimation errors, and error correction leakage to establish a rigorous composable bound.

How the Paradigm Works

The real/ideal world paradigm is the foundation of modern simulation-based security proofs. Rather than defining security as a list of properties a protocol must satisfy, it asks a single question: can any computationally bounded environment tell the difference between interacting with the real protocol and interacting with an idealised, perfectly secure version?

The ideal functionality F is a trusted black box that captures the intended security properties in their purest form. For key distribution, F simply hands identical, uniformly random, secret keys to Alice and Bob while Eve receives nothing correlated. For a commitment scheme, F enforces both hiding and binding simultaneously and perfectly. F is the definition of what “secure” means for that task.

The real protocol π runs among the actual parties with no trusted third party. The adversary A attacks the real execution: delivering messages, corrupting parties, timing side channels. The simulator S is the mathematical tool used in the proof: it runs in the ideal world alongside F, with access only to F's inputs and outputs, and must generate a simulated transcript indistinguishable from A's real-world view.

The fundamental challenge in quantum proofs: Classical simulators use rewinding — they copy an adversary's state and re-run it from a checkpoint. The no-cloning theorem prohibits copying a quantum state. This means rewinding-based proof techniques fail against quantum adversaries, and new simulator constructions (such as straight-line simulators that never rewind) must be found for each protocol class. This is one of the deepest obstacles in quantum cryptographic security theory.

The ROM and Its Quantum Problem

The Random Oracle Model (ROM), introduced by Bellare and Rogaway in 1993, models a hash function as an ideal random function accessible only as a black-box oracle. Proofs in the ROM show that if the oracle behaves randomly, the scheme is secure — a strong heuristic for well-designed hash functions. The ROM is extremely productive: schemes like RSA-OAEP, Schnorr signatures, and many others have clean ROM proofs but no standard-model alternative.

The quantum problem: In the ROM, the adversary makes classical queries: one input per query, one output. A quantum adversary can query the oracle in superposition — a single query evaluates the hash function on an exponential number of inputs simultaneously. This superposition access breaks the classical proof technique of “programming the oracle” (making the oracle return a specially crafted value at a key point), because programming requires knowing which input the adversary will query next, which measurement of a quantum state would disturb.

QROM (Boneh et al. 2011): The Quantum Random Oracle Model gives the adversary quantum superposition access to the oracle. Schemes proven secure in the QROM are heuristically secure against quantum adversaries. Critically, ROM-security does not imply QROM-security: there exist constructions that are provably secure in the ROM and provably insecure in the QROM. The NIST PQC process explicitly requires QROM security proofs for schemes that use hash functions as security-critical components.

The Composability Problem

Standalone security proves that a single, isolated execution of a protocol is secure. But real systems do not run in isolation. A QKD protocol generates a key that is then used by an encryption scheme. That encryption scheme runs alongside an authentication protocol. The entire stack runs on a network where hundreds of other protocols execute concurrently. Standalone security says nothing about this situation.

A concrete failure: Consider a QKD protocol proven secure using mutual information: the key K satisfies I(K ; E) ≈ 0 at the end of the protocol. Now Alice and Bob use K to encrypt a message M under the one-time pad. Eve holds a quantum state correlated with K. She delays her measurement. She now measures her state given M — using the encryption as a quantum side-channel. Mutual-information security provided no bound for this scenario because it measured Eve's information before the key was used. The proof was valid but the guarantee was useless for the actual application. Trace-distance composable security closes this gap by bounding Eve's advantage in any task using the key, including tasks involving her quantum memory and future measurements.

Sequential composition: In QKD, Alice and Bob may need to run multiple protocol rounds to generate a long key. Sequential composition ensures that running the protocol n times produces n composably secure key segments that can be concatenated. Without the sequential composition theorem, no argument of this kind is valid.

The UC Framework for Quantum Protocols

Universal Composability (UC), formalised by Canetti (2001) and extended to the quantum setting by Ben-Or and Mayers (2004) and Unruh (2010), is the strongest composability guarantee available. A protocol π is UC-secure if it UC-realises an ideal functionality F: for every efficient adversary A in the real world, there exists an efficient simulator S in the ideal world such that no efficient environment Z can distinguish the two executions. The environment Z plays the role of any surrounding system the protocol might be embedded in — it is unboundedly adaptive in what it sends and observes.

The universal composition theorem states: if π UC-realises F, then replacing every call to F in any larger protocol ρ with a call to π produces a protocol that UC-realises whatever ρ realises. This modular substitution preserves all security guarantees, even in the presence of arbitrary concurrent protocol executions. It is the formal foundation for building cryptographic systems from independently proven components.

The quantum challenge to rewinding: The rewinding technique — a cornerstone of classical UC simulation — copies the adversary's internal state and re-runs it. No-cloning prohibits this for quantum adversaries. Unruh's quantum UC framework requires constructing straight-line simulators that never rewind: they interact with the adversary only in the forward direction, extracting needed information without state copies. This restricts which protocols admit quantum UC proofs and forces fundamentally new simulation arguments.