Quantum Cryptography Beyond Quantum Key Distribution

Anne Broadbent; Christian Schaffner

Source-linked AI summary

Quantum Cryptography Beyond Quantum Key Distribution

Anne Broadbent, Christian Schaffner

arXiv:1510.06120v2Oct 21, 2015quant-ph

TL;DR

Quantum cryptography is often equated with QKD, despite broader cryptographic applications and important limitations. This paper surveys selected theoretical constructions and challenges beyond key exchange for readers without prior quantum-information knowledge.

Problem
Quantum cryptography encompasses uses beyond QKD, but the field is often equated with key distribution and includes fundamental limitations such as insecure quantum bit commitment.
Method
The paper surveys selected theoretical uses of quantum information for cryptography, together with limitations and challenges relevant to cryptographers unfamiliar with quantum information.
Results
The survey covers quantum protocols and applications including conjugate coding, oblivious transfer, limited-quantum-storage protocols, coin flipping, and quantum cryptographic limitations.
Takeaways & Limitations
Quantum information broadens cryptography beyond QKD while introducing challenges involving security assumptions, composability, rewinding, and adversarial quantum resources.
Takeaways & Limitations
The survey provides an overview of only a limited number of quantum-cryptography topics.

Abstract

from arXiv · show

Quantum cryptography is the art and science of exploiting quantum mechanical effects in order to perform cryptographic tasks. While the most well-known example of this discipline is quantum key distribution (QKD), there exist many other applications such as quantum money, randomness generation, secure two- and multi-party computation and delegated quantum computation. Quantum cryptography also studies the limitations and challenges resulting from quantum adversaries---including the impossibility of quantum bit commitment, the difficulty of quantum rewinding and the definition of quantum security models for classical primitives. In this review article, aimed primarily at cryptographers unfamiliar with the quantum world, we survey the area of theoretical quantum cryptography, with an emphasis on the constructions and limitations beyond the realm of QKD.

1 Introduction

Quantum cryptography extends beyond QKD to applications that exploit quantum information for new or stronger cryptographic functionalities. This survey introduces these constructions for cryptographers while examining quantum-specific impossibility results, adversarial challenges, and open problems.

Quantum cryptography includes quantum money, randomness generation, secure computation, delegated computation, and other applications beyond QKD.
The survey is intentionally selective, and topics such as everlasting security, quantum functionalities, key recycling, uncloneability, isolation assumptions, and leakage resilience receive limited or no coverage.
Quantum protocols can provide information-theoretic security where classical protocols offer computational security at best, or enable functionalities unavailable classically.
Conjugate coding underlies constructions including physically unforgeable quantum money, information-theoretically secure key expansion, and quantum reductions between bit commitment and oblivious transfer.
The survey also covers limitations including impossible information-theoretic quantum bit commitment and two-party computation, quantum rewinding, superposition oracle access, and position verification.
Position-based quantum cryptography remains open against resource-bounded adversaries, while efficient honest execution with exponentially costly attacks is posed as a central question.

2 Basics of Quantum Information

Quantum information represents states with qubits, evolves them through unitary operations, and extracts classical outcomes through measurement. Superposition, entanglement, uncertainty, and no-cloning create computational and cryptographic behavior that differs from classical information.

A qubit is a unit vector in a two-dimensional complex space and can be expressed as α|0⟩ + β|1⟩, including superpositions of basis states.
An n-qubit system can be a superposition of 2^n computational basis states and is described by 2^n complex coefficients.
Quantum evolution uses norm-preserving unitary matrices, and quantum algorithms are represented as circuits built from universal quantum gates such as X, Z, H, and CNOT.
Measurement produces a classical bit with probabilities determined by amplitudes, disturbs the quantum state, and can be performed in arbitrary bases.
Quantum systems cannot generally be cloned, so a single unknown state cannot be transformed into two identical copies or fully extracted into classical parameters.
Entanglement produces correlations stronger than classical shared randomness, exemplified by CHSH winning probability cos^2(π/8) ≈ 0.85 versus the classical 3/4 bound.

3 Quantum Cryptographic Constructions

The survey presents quantum cryptographic protocols whose common conceptual foundation is conjugate coding. It uses this pattern to organize constructions spanning quantum money, QKD, oblivious transfer, and limited-storage models.

Many surveyed quantum cryptographic protocols share a simple pattern of quantum information called conjugate coding.

3.1 Conjugate Coding

Conjugate coding encodes classical bits in randomly chosen quantum bases, making incompatible measurements destructive and limiting unauthorized duplication. This primitive supports quantum money and other protocols while remaining feasible in single-qubit prepare-and-measure implementations.

Conjugate coding encodes classical information into conjugate quantum bases and is also called quantum coding or quantum multiplexing.
The rectilinear basis R and diagonal basis D each encode a classical bit using distinct photon polarizations.
Measuring in one basis irrevocably destroys information about the encoding in the conjugate basis.
Without the encoding basis, a third party with one encoded state cannot create two states that pass the originator’s verification with high probability.
Heisenberg-style uncertainty formalizes the trade-off through H(P_X) + H(Q_X) ≥ 1 and supports security proofs in limited-quantum-storage settings.
Single-qubit prepare-and-measure conjugate coding is feasible with current technology, allowing derived protocols to inherit modest implementation requirements.
Conjugate coding is used in quantum money, including Wiesner’s private-key scheme and publicly verifiable variants based on computational assumptions.
Post-verification variants that return quantum encodings were found insecure, whether the state is always returned or only returned after valid verification.

3.2 Quantum Key Distribution

QKD is the most successful and widely surveyed application of quantum information to cryptography, using conjugate coding for information-theoretically secure key agreement. Its security theory includes error correction, symmetry-based, complementarity-based, and finite-key analyses, while implementations face side-channel vulnerabilities and authentication assumptions.

QKD is the most successful application of quantum information to cryptography and is surveyed here only briefly because many comprehensive references already exist.
BB84 uses conjugate coding: Alice sends randomly chosen single-qubit states, Bob measures in random bases, and basis comparisons enable eavesdropper detection.
Security proofs evolved from Shor–Preskill’s quantum-error-correction approach to Renner’s symmetry and de Finetti analysis and complementarity-based proofs.
Finite-key security revisits QKD proofs to obtain concrete security parameters for practical implementations.
Real-world QKD implementations are vulnerable to side-channel attacks because devices deviate from the idealized models used in security proofs.
QKD implementations can replace an initial short authentication secret with computational or eavesdropper-storage assumptions, yielding everlasting or long-term security.

3.3 Bit Commitment implies Oblivious Transfer

Quantum cryptography establishes a striking relationship between bit commitment and oblivious transfer: OT and BC are equivalent in the quantum world, and a conjugate-coding OT protocol can be secured using commitments. Proving security required techniques developed years after the protocol’s proposal.

OT and bit commitment are equivalent in the quantum world, unlike in the classical information-theoretic setting.
Oblivious transfer lets Alice send m0 and m1 while Bob receives only mc according to his choice bit c.
OT is universal for secure two-party computation, allowing arbitrary functions to be securely evaluated through repeated 1-out-of-2 transfers.
Bit commitment requires concealing Alice’s bit before reveal and binding her to that bit afterward.
The BBCS01 quantum OT protocol uses conjugate coding to send randomly prepared qubits and assumes bit commitment to constrain Bob’s basis choices.
Security proofs culminated in techniques by Damgård and colleagues, followed by Unruh’s formal proof that BC and OT are equivalent in the quantum UC model.

3.4 Limited-Quantum-Storage Models

Limited-quantum-storage models obtain information-theoretic security by restricting adversarial quantum memory or operations rather than relying solely on computational assumptions. These models support composable secure computation and have modest, experimentally demonstrated implementation requirements.

Bit commitment and general secure two-party computation are impossible in the unrestricted plain quantum model, motivating security under computational or physical restrictions.
The bounded-quantum-storage model limits adversaries to storing a restricted number of qubits while requiring no quantum storage from honest players.
The quantum bounded-storage model provides an unbounded gap between honest and dishonest storage requirements, unlike the classical model’s at-most-quadratic gap.
A bounded-storage OT protocol inserts a waiting time Δt after the quantum phase, forcing a dishonest receiver to use imperfect quantum memory before basis revelation.
The noisy-quantum-storage model allows arbitrary but imperfect quantum storage, modeling storage difficulty more realistically than a strict qubit limit.
Protocols can remain secure against adversaries restricted to specified quantum operations, including only adaptive single-qubit measurements performed at the protocol’s end.
Entropic uncertainty relations play a key role in security proofs for limited-quantum-storage protocols.
Limited-quantum-storage protocols support sequential and bounded concurrent composition, and their technological requirements resemble QKD while allowing nearby-player computations.

3.5 Delegated Quantum Computation

Delegated quantum computation addresses privacy when quantumly weak clients outsource computations to quantum servers. Universal blind quantum computation lets clients control private computations with minimal quantum capability, while related protocols extend delegation to encrypted data and classical clients under additional assumptions.

Delegated quantum computation seeks privacy when quantumly weak clients outsource computations to universal quantum computers.
Universal blind quantum computation lets a client prepare random single-qubit states and remotely drive a chosen computation without quantum memory or a quantum processor.
In uBQC, the server learns nothing about the computation, while only the client learns the output; the protocol has been experimentally demonstrated.
uBQC uses conjugate coding directly for a computational cryptographic task rather than merely measuring encoded states to extract classical information.
Quantum computing on encrypted data executes a public circuit on encrypted data while the client sends only random single-qubit states.
Delegated quantum computation can use a purely classical client if two universal quantum computers are assumed unable to communicate.

3.6 Quantum Protocols for Coin Flipping and Cheat-Sensitive Primitives

Quantum coin flipping and related primitives reveal sharp limits and partial achievements in quantum cryptography. Strong coin flipping has an unavoidable bias, while weak coin flipping can approach ideal performance, but imperfect commitment remains difficult to use compositionally.

Coin flipping: Weak quantum coin flipping protocols exist with arbitrarily small bias ε > 0.Mochon established existence through point games, and later work considerably simplified the proof.
Cheat-sensitive primitives: Optimal imperfect quantum bit commitment cannot be amplified to perfect commitment because one player can cheat with significant probability.This sharply limits its applicability as a building block for more advanced cryptographic primitives.
Cheat-sensitive primitives: Cheat-sensitive primitives can be useful as final products, but their behavior under composition remains unclear.A composability framework for cheat-sensitive quantum primitives is described as a challenging open question.

3.7 Device-Independent Cryptography

Device-independent cryptography uses Bell-inequality violations to certify quantum behavior and randomness even with untrusted devices. This supports randomness amplification, randomness expansion, and quantum key distribution, subject to assumptions such as no adversary communication with the devices.

Device-independent foundations: Bell-inequality violations, especially in the CHSH game, certify the quantumness of untrusted devices and imply intrinsic randomness in their outputs.The approach can support cryptography even when devices may have been constructed by the adversary.
Device-independent foundations: CHSH violations provide an exact quantitative relation between nonclassical correlations and measurement-outcome entropy.Robust self-testing further shows that near-optimal CHSH performance implies possession of a state close to an EPR pair.
Security mechanism: Monogamy of entanglement explains why measurements on an EPR state produce shared randomness unavailable to an eavesdropper.This supplies the security intuition behind device-independent cryptographic applications.
Applications: Device-independent protocols extend to randomness amplification and expansion, including arbitrary amplification of very weak sources in combined protocols.Experimental realizations of device-independent randomness are also reported.
Applications: Device-independent QKD assumes no communication between the adversary and the quantum devices, with current work targeting realistic noise levels.The first formal security proof for such a scheme was given by Vazirani and Vidick.

4 Quantum Cryptographic Limitations and Challenges

The survey examines quantum cryptography’s impossibility results and challenges, including failures of secure bit commitment and two-party computation, quantum rewinding, quantum security notions, and position-based protocols.

Quantum adversaries: Quantum adversaries also challenge classical cryptography through quantum rewinding and security definitions involving superposition access to oracles.Post-quantum cryptography studies classical schemes intended to remain secure against quantum adversaries.
Quantum bit commitment: Information-theoretically secure quantum bit commitment is impossible, despite early proposals and a claimed protocol later invalidated by a flaw in its security argument.The impossibility was generalized by Mayers, Lo, and Chau to all quantum protocols.
Quantum bit commitment: Quantum bit commitment fails because information-theoretic hiding lets the committer delay choosing the committed bit until opening.The purified-protocol argument uses the fact that equivalent reduced states imply a unitary transformation enabling either opening.
Two-party computation: Quantum communication cannot securely realize broad two-party functionalities: impossibility results cover one-sided computation, oblivious transfer, and information leakage in non-trivial primitives.For approximate correctness and security, security against one party can leave the other completely insecure.
Position-based quantum cryptography: Position verification seeks to prove a party’s geographical location, but proposed quantum schemes were broken, motivating entanglement-based attack analysis and new complexity models.A three-dimensional protocol is secure in the quantum-random-oracle model, while efficient schemes without random oracles remain open.

5 Conclusion and Open Problems

The survey concludes that quantum cryptography is an active interdisciplinary field whose theoretical power and limitations continue to expand. It highlights open problems spanning quantum-secure primitives, practical device-independent protocols, position verification, randomized functionalities, obfuscation, delegated computation, and quantum money.

Conclusion: Quantum cryptography combines cryptography, quantum physics, complexity theory, and information theory, while experimental implementations remain at the prototype level.The survey emphasizes continuing growth in theoretical understanding of both capabilities and limitations.
Open problems: Post-quantum cryptography needs better understanding of which cryptosystems quantum algorithms can break, because this informs security-parameter selection.The survey identifies quantum cryptanalysis as requiring further research.
Open problems: Device-independent protocols remain an open problem because practical schemes must tolerate a realistic amount of noise.The question applies to key distribution and possibly other applications.
Open problems: Position-based cryptography seeks protocols efficient for honest players but requiring attackers to use exponentially many resources, such as entangled qubits.The survey presents this as a central unresolved question.
Open problems: Open questions include constructing quantum-secure pseudorandom permutations and determining which randomized or quantum functionalities quantum protocols can implement.Classical Feistel-based permutation constructions may be insecure against quantum attacks.
Open problems: Further open problems ask whether quantum information supports highly secure program obfuscation, private or verifiable delegation by classical clients, and quantum public-key money from standard assumptions.Current quantum public-key money techniques rely on ad hoc assumptions.