PaperlayerView exact revision on arXiv

Source-linked AI summary

Composability in quantum cryptography

Joern Mueller-Quade, Renato Renner

arXiv:1006.2215v1quant-phcs.CR

TL;DR

The paper addresses the difficulty of safely composing cryptographic components when security definitions may not remain valid under composition. It reviews QKD security and composable frameworks, and concludes that QKD can realize unconditionally secure protocols from the secure-channel model without a new proof; it also notes a limitation of the universal framework.

  • Problem

    Security definitions are not generally closed under composition, so an application may be insecure even when its individual components are secure.

    Source: §1 · p. 1

  • Method

    The paper reviews QKD security criteria, illustrates sequential composition with a continuous key stream, and explains the universal composability framework and its composition theorem.

    Source: §6 · p. 15

  • Results

    Every unconditionally secure protocol possible in the secure-channel model is also possible with QKD, without requiring a new proof.

    Source: §6 · p. 15

  • Takeaways & Limitations

    The universal composability framework provides strong guarantees for using secure protocols in arbitrary applications and for concurrent composition.

    Source: §6 · p. 15

    The accessible-information attack is presented as intuition rather than a rigorous proof, with details referred to elsewhere.

    Source: §2.5 · p. 8

Abstract

from arXiv · show

In this article, we review several aspects of composability in the context of quantum cryptography. The first part is devoted to key distribution. We discuss the security criteria that a quantum key distribution protocol must fulfill to allow its safe use within a larger security application (e.g., for secure message transmission). To illustrate the practical use of composability, we show how to generate a continuous key stream by sequentially composing rounds of a quantum key distribution protocol. In a second part, we take a more general point of view, which is necessary for the study of cryptographic situations involving, for example, mutually distrustful parties. We explain the universal composability framework and state the composition theorem which guarantees that secure protocols can securely be composed to larger applications

1 Introduction

Composing secure cryptographic components does not automatically produce a secure application, so composability requires carefully chosen definitions and a suitable framework. The article reviews this challenge in quantum cryptography, distinguishing QKD’s fixed adversary structure from settings where arbitrary parties may be corrupted.

1 Introduction

  • Security definitions are not generally closed under composition, so an application can be insecure even when its individual components are secure.A monolithic proof for a larger cryptosystem is error prone, motivating modular design and universally composable frameworks.Source: §1 · p. 1
  • The review treats QKD security and composability first, then considers composability for general security applications.QKD is described as the most prominent application of quantum cryptography.Source: §1 · p. 1
  • Usual QKD treatment assumes Alice and Bob are honest, whereas the general setting allows arbitrary parties to be corrupted.QKD’s fixed adversary structure leaves only a third party with access to the communication channels as malicious.Source: §1 · p. 1

2 Quantum Key Distribution (QKD)

This section examines QKD security criteria for composable use, including composing keys with applications and across repeated rounds. It explains why accessible information alone may not establish composable secrecy and motivates proving security directly using the trace-distance secrecy criterion.

2.1 QKD in a Nutshell

  • QKD distributes secret key bits over an insecure quantum channel; quantum disturbances can reveal attacks, while authenticated classical communication requires Alice and Bob to share a short initial key.If disturbance tests find excessive errors, the protocol aborts; otherwise, Alice and Bob generate a key from the distributed signals.Source: §2.1 · p. 2

2.2 Security Criteria

  • A QKD protocol’s ideal security requires correctness, secrecy, and robustness; approximate security means indistinguishability from an ideal protocol, with component errors adding as ε = εc + εs + εr.Correctness is tied to error correction, while secrecy depends on disturbance estimation and privacy amplification.Source: §2.2 · pp. 3–4

2.3 Composing QKD with Other Cryptographic Primitives

  • When an ε1-secure QKD protocol supplies a key to an ε2-secure application, their composition is ε1 + ε2-secure; with one-time-pad encryption, ciphertexts are ε1-indistinguishable from uniform randomness.A perfectly secret key makes one-time-pad encryption indistinguishable from ideal encryption, so the application contributes ε2 = 0.Source: §2.3 · p. 5

2.4 Example Application: Generating a Continuous Key Stream

  • Repeated QKD rounds can generate a continuous key stream by using part of each fresh key for authentication in the next round and adding the remainder to the stream.With suitable choices of stream length and protocol parameters, increasing the number of signals per round makes the stream’s total security parameter arbitrarily small.Source: §2.4 · pp. 6–7

2.5 An Explicit Attack Exploiting Non-Composability

  • The section warns that non-composable secrecy definitions can cause problems and introduces accessible information, defined through measurements of the adversary’s quantum system, as an information measure for the key.Accessible information maximizes the Shannon mutual information between the key and the outcome over measurements of the adversary’s system.Source: §2.5 · p. 7
  • The secrecy criterion implies small accessible information: for small ε, Iacc(SA : E) is small, with the bound Iacc(SA : E) ≤ 2nε + 4h(ε).Thus the implication from composable secrecy to accessible-information security holds, but not its converse.Source: §2.5 · p. 7
  • Despite arbitrarily small accessible information, the example key is unsafe for one-time-pad use: knowing the first n message bits lets an adversary recover the final bit with certainty.The example therefore shows that small accessible information does not by itself guarantee safe use in a larger application.Source: §2.5 · pp. 7, 9
  • The example is a proof of principle, and the explanation for small accessible information is intuitive rather than a rigorous proof; details are referred to.The parameters were not optimized.Source: §2.5 · pp. 7–8
  • The conditioned state of E is independent of (S1,...,Sn), so I(S1...Sn : Z) = 0; Sn+1 is the parity of random bits R1,...,Rn, and its correlation with Z is small even for arbitrary measurements.For a slightly modified example, a quantitative analysis gives I(SA, Z) < 2^(−n−2).Source: §2.5 · pp. 8–9
  • Composable security derived from an accessible-information bound requires that bound to be exponentially small in key size, a threshold most known proofs using accessible information do not meet.The argument makes the result of Ben-Or et al. [3] essentially tight.Source: §2.5 · p. 9
  • Security proofs should directly bound trace distance; suitable privacy-amplification hashes, such as two-universal hashing, yield the criterion when raw-key entropy is sufficient [35], with specific examples in [14] [42].The Shor–Preskill argument [40] can also produce such a bound but applies only to specific protocol types.Source: §2.5 · p. 9

3 Composability of General Secure Applications

This section takes up composition for general cryptographic tasks, presenting a quantum security model and its composition theorem. The theorem states that secure protocols in this model can be used in arbitrary applications and composed concurrently.

3 Composability of General Secure Applications

  • The second part of the article addresses security definitions for general cryptographic tasks and composing secure protocols into complex applications.Source: §3 · p. 9
  • The quantum security model's composition theorem says a protocol secure in the model can be used in an arbitrary application without lowering overall security.It also permits any number of protocols proven secure in the model to be used concurrently while remaining secure in the model.Source: §3 · p. 10
  • The article treats the quantum security model intuitively and abstractly, omitting many details and referring readers to [43] [4] [45].It notes that even the classical account in is 128 pages.Source: §3 · p. 10
  • Although coin flipping, bit commitment, and oblivious transfer lack unconditional quantum security [1] [25], some applications remain possible under assumptions independent of classical computational assumptions [37, 13].Examples of such assumptions include limits on an adversary's quantum storage or ability to maintain coherence in large quantum states.Source: §3 · p. 10
  • The model can also analyze classical protocols against quantum adversaries, including whether quantum attacks add more than computational speedup.The article says this question was answered in the context of composability.Source: §3 · p. 10

4 Defining Security

General cryptographic applications involve mutually distrustful parties and require more than a list of standalone security properties. The section motivates simulation-based definitions by showing how composition can expose vulnerabilities, including through quantum information spanning subprotocols.

4 Defining Security

  • Secure function evaluation requires correctness and privacy, but these alone may not ensure input independence or other desired security properties.The list approach risks omitting properties because it is unclear whether the list is complete.Source: §4 · p. 10

4.1 The Simulation Paradigm

  • Simulation-based security compares a real protocol with an ideal protocol and requires an ideal attacker to reproduce the real attacker's output using only corrupted players' inputs and outputs.The ideal attacker cannot access real messages or secrets unavailable from those inputs and outputs.Source: §4.1 · pp. 10–11
  • Retrospective simulation preserves correctness and secrecy, but does not support composition or protocols accepting inputs later in execution.The definition discussed here also does not yet allow composition.Source: §4.1 · p. 11

4.2 A Motivating Example: Secure Composition as a Problem

  • Composition can make a larger application insecure: the examples include a classical subprotocol message passed into another and quantum information entangled across subprotocols.The latter example shows that quantum information need not remain confined to individual subprotocols.Source: §4.2 · p. 11, §4.2.2 · p. 12

4.2.1 Malleability—a Classical Example

  • With textbook RSA, Bob can transform Alice's encrypted bid into an encryption of twice her bid, illustrating malleability as a larger-application weakness.The passage distinguishes this application-level problem from a weakness of textbook RSA by itself.Source: §4.2.1 · pp. 11–12

4.3 Types of Protocol Composition

  • Simple composition permits surrounding messages to enter a subprotocol, while concurrent composition adds interleaved instances whose messages may affect one another.Composition-secure simulation must work in arbitrary application contexts rather than only in retrospect.Source: §4.3 · p. 12

5 The Universal Composability Framework

The universal composability framework augments simulation-based security with an environment that can emulate surrounding protocols. Its composition theorem supports substitution and concurrent composition, while the review also describes consequences and limits of these guarantees.

5 The Universal Composability Framework

  • The UC framework adds an environment machine that interacts with the protocol and attacker and can emulate arbitrary surrounding protocols.The environment can choose inputs, observe outputs, and communicate with the adversary during execution.Source: §5 · pp. 12–13

5.1 The Composition Theorem

  • If ρ securely realizes F, replacing F by ρ preserves realization of the larger application; the theorem also covers polynomially many concurrent instances.Combining simple and concurrent composition yields the stated guarantee for applications using multiple instances.Source: §5.1 · p. 14

5.2 Information Theoretical Security and Quantum Adversaries

  • Statistical UC security against a classical adversary also gives security in the quantum composability setting, supporting use of QKD-based secure channels in applications.The review notes secure multiparty computation with an honest majority as an example.Source: §5.2 · p. 14

5.3 Impossibility of Bit Commitment

  • Without additional assumptions, bit commitment is impossible with computational security in the UC framework, including in the quantum case.Possible setup assumptions include a Common Reference String, trusted public-key infrastructure, or tamper-proof hardware.Source: §5.3 · p. 14

5.4 Composability in the Bounded Quantum Memory Model

  • Bounded-quantum-memory protocols may compose sequentially but not generally; differing memory limits for attackers and simulators can make the security relation non-transitive.A proposed way around this is to make the adversary's memory bound an explicit parameter.Source: §5.4 · p. 15, §5.3 · p. 15

6 Conclusions

The review presents composable security for QKD and general cryptographic applications, including sequential generation of a continuous key stream. It concludes that UC guarantees enable secure-channel protocols to be used with QKD, while strong guarantees can require additional assumptions and hardware-model limitations remain open.

6 Conclusions

  • The review constructs a scheme for generating a continuous key stream by sequentially composing QKD rounds.It also discusses security criteria and an attack exploiting a weakness of a non-composable secrecy definition.Source: §6 · p. 15
  • Every unconditionally secure protocol possible with secure channels is also possible with QKD, without a new proof.The review attributes this consequence to secure composition of quantum protocols into unconditionally secure classical protocols.Source: §6 · p. 15
  • UC's strong guarantees can make tasks such as bit commitment impossible without added assumptions, leaving a trade-off that remains open.The review also identifies flexible modeling of underlying hardware as desirable because security proofs typically assume models that practical implementations do not strictly match.Source: §6 · pp. 15–16
Loading 1006.2215v1…