Quantum Cryptographic
Protocols

The Broader Landscape of Quantum Cryptographic Protocols

The term “quantum cryptography” is often used as a synonym for QKD, but the field encompasses a far richer set of primitives. QKD addresses one problem: securely distributing a shared secret key between two parties who trust each other but distrust the channel. Many cryptographic tasks involve parties who partially distrust each other, operate in multi-party settings, or need security guarantees beyond confidentiality.

Two types of quantum advantage: Quantum protocols can improve on classical alternatives in two distinct ways. First, they can achieve information-theoretic (unconditional) security for tasks where only computational security is classically achievable — such as digital signatures. Second, they can achieve tasks that are provably impossible with any classical protocol, even with computational assumptions — such as certain coin-flipping protocols with bounded bias.

The conjugate coding root: Most quantum cryptographic constructions trace back to Stephen Wiesner's 1968 manuscript on conjugate coding — the idea of encoding classical bits in non-orthogonal quantum states drawn from two conjugate bases. No-cloning prevents an adversary from copying these states; measurement in the wrong basis disturbs them. Conjugate coding underlies QKD, quantum money, quantum oblivious transfer reductions, and the first quantum digital signature proposals.

How Quantum Digital Signatures Work

Classical digital signatures (RSA, ECDSA) derive their security from computational hardness assumptions: forgery requires factoring or solving discrete logarithms, which is computationally infeasible classically but not quantum-mechanically. Quantum digital signatures (QDS) derive security from physical principles: the no-cloning theorem and the indistinguishability of non-orthogonal quantum states prevent forgery regardless of computational power.

Core design principle: The original Gottesman-Chuang QDS scheme (2001) had the signer distribute quantum public keys — many copies of a fixed quantum state — to all recipients. No-cloning prevented forgery. However, this required long-term quantum memory to store the public keys, which was the main barrier to practicality. The breakthrough was the realisation (Dunjko, Wallden, Kent, Andersson, 2014) that the quantum exchange phase and the signing phase could be separated, with authentication using classical symmetric keys derived from the quantum channel — eliminating the quantum memory requirement entirely.

Security guarantees: A QDS scheme provides: (1) unforgeability — no third party can forge a valid signature; (2) non-repudiation — the signer cannot deny having signed a message; (3) transferability — a verified signature can be forwarded to a third party who can also verify it. All three hold information-theoretically — no assumptions about computational hardness are needed.

Field test: A measurement-device-independent QDS (MDI-QDS) protocol was demonstrated over a 200-square-kilometre metropolitan network (Yin et al. 2017), signing binary messages with security level ~10⁻⁷. MDI protocols are immune to detector side-channel attacks — a major vulnerability class in QKD implementations — by routing all measurements through an untrusted relay.

Why OT Matters and How Quantum Helps

Oblivious transfer is the most important primitive in secure multi-party computation: Kilian (1988) proved that any two-party secure computation can be implemented given a single OT oracle. If OT is secure, then general secure computation — private set intersection, private voting, genome analysis on encrypted data, secure auctions — becomes achievable. Classical OT requires computational hardness assumptions (e.g., RSA or DH). A computationally unbounded adversary (or a future quantum computer) breaks all classical OT constructions.

The quantum impossibility: Naively one might hope for information-theoretically secure quantum OT, but this is impossible in the plain model. The same mathematical argument that rules out quantum bit commitment (Mayers 1996, Lo-Chau 1997) implies that quantum OT is also impossible information-theoretically without setup assumptions. This is one of the fundamental impossibility results of quantum cryptography.

The bounded quantum storage model: Damgård, Fehr, Salvail, and Schaffner (2005) showed that OT becomes information-theoretically secure if the adversary's quantum memory is bounded — specifically, if the adversary cannot store more than some fraction of the transmitted qubits. This assumption is physically motivated: quantum memories decohere rapidly, and adversaries cannot store billions of qubits. Under this assumption, simple protocols transmitting n qubits achieve security if the adversary can store fewer than n/2 qubits. No computational hardness is required.

Conjugate coding reduction: In the quantum world, bit commitment and OT are information-theoretically equivalent (BC ⇒ OT), which is a strictly quantum phenomenon — classically, bit commitment does not imply OT. This equivalence means that any commitment scheme constructed from quantum mechanics directly yields an OT protocol, and vice versa.

Quantum Coin Flipping — A Bounded But Not Perfect Advantage

Coin flipping allows two mistrustful parties to agree on a random bit without a trusted third party. In the classical setting, it is impossible to construct a fair coin-flipping protocol with information-theoretic security: a dishonest party can always bias the outcome toward their preferred result with probability greater than 1/2.

The quantum situation: Quantum coin flipping cannot achieve perfect fairness either — a result proven by Lo and Chau (1998) using teleportation. However, quantum protocols can guarantee that no party can bias the outcome with probability greater than 1/√2 ≈ 0.707. This is a strict improvement over the classical bound of 1/2 + some advantage. Quantum coin flipping protocols achieving bias exactly 1/√2 − 1 ≈ 0.207 exist but are difficult to implement practically.

Practical realisation: The bounded bias translates to partial but meaningful protection: even a cheating party cannot guarantee their preferred outcome. This has applications in secure protocol initiation and fair scheduling. Experimental demonstrations have been performed over fibre channels in controlled settings.

Quantum Bit Commitment — The Canonical Impossibility

Bit commitment requires a committer to “lock in” a bit value that they reveal later, while (1) the receiver cannot learn the bit before reveal (hiding), and (2) the committer cannot change the bit after committing (binding). Both properties together make commitment a building block for zero-knowledge proofs, secure two-party computation, and e-voting.

The impossibility: Mayers (1996) and Lo and Chau (1997) independently proved that unconditionally secure quantum bit commitment is impossible in the plain model — without trusted setup. Any protocol that is perfectly hiding can be made non-binding by the committer, because the committer can use quantum entanglement to maintain a superposition over committed values and retroactively choose which bit to reveal. This result — often called the Mayers-Lo-Chau impossibility — was a significant setback for early quantum cryptography.

Workarounds: Commitment becomes achievable with: (a) computational assumptions (one-way functions suffice classically; quantum one-way functions suffice in QROM), (b) bounded quantum storage — if the receiver cannot store too many qubits, their ability to distinguish between committed values is limited, (c) trusted setup (common reference string), or (d) relativistic constraints — exploiting the speed-of-light to prevent the committer from signalling between commit and reveal phases. Relativistic bit commitment has been experimentally demonstrated over intercontinental distances.

Bell Inequalities as a Security Foundation

Standard quantum cryptographic protocols assume the parties trust their own devices: the source produces the states it claims, the detectors measure correctly, and the random number generators are unbiased. Device-independent (DI) protocols replace all these assumptions with a single testable condition: that the observed measurement statistics violate a Bell inequality, which is impossible for any local hidden variable theory.

Why this matters for QKD: In device-independent QKD (DI-QKD), Alice and Bob share entangled states from an untrusted source and perform measurements using untrusted detectors. The only assumption is that their labs are causally isolated (no side-channel from one lab to the other) and that quantum mechanics holds. A loophole-free Bell test certifies that genuine entanglement was shared, which in turn certifies randomness and security of the key. This closes the gap between theoretical security proofs (which assume ideal devices) and real implementations (which may have exploitable physical imperfections).

Experimental status: The three loophole-free Bell tests of 2015 (Delft, NIST, Vienna) were milestones. DI-QKD was experimentally demonstrated in 2022 by three independent groups, achieving modest but positive key rates over short distances. The primary challenge is efficiency: DI-QKD requires very high detection efficiencies (~90%+) to close the detection loophole, and current experiments achieve key generation at rates of bits per second over short distances — far from commercially viable.