Source-linked AI summary
Leftover Hashing Against Quantum Side Information
Marco Tomamichel, Christian Schaffner, Adam Smith, Renato Renner
TL;DR
The paper addresses the limitation of the classical Leftover Hash Lemma when side information is quantum rather than classical. It generalizes the lemma to quantum side information and arbitrary δ-almost two-universal hash families, showing that conditional smooth min-entropy characterizes extractable uniform randomness up to additive log(1/∆) terms. The result supports privacy amplification and related cryptographic uses in quantum settings.
Problem
Classical treatments of randomness extraction do not generally cover side information stored in quantum systems, which can preserve knowledge about outputs differently from classical side information.
Method
The paper extends conditional min-entropy, uniformity, and the Leftover Hash Lemma to quantum side information and δ-almost two-universal hash families.
Results
The generalized lemma applies to arbitrary δ-almost two-universal families and reaches the smooth min-entropy extraction bound up to additive terms of order log(1/∆).
Takeaways & Limitations
Conditional smooth min-entropy is an accurate measure of the uniform randomness extractable from X conditioned on quantum side information E.
Abstract
from arXiv · showhide
The Leftover Hash Lemma states that the output of a two-universal hash function applied to an input with sufficiently high entropy is almost uniformly random. In its standard formulation, the lemma refers to a notion of randomness that is (usually implicitly) defined with respect to classical side information. Here, we prove a (strictly) more general version of the Leftover Hash Lemma that is valid even if side information is represented by the state of a quantum system. Furthermore, our result applies to arbitrary delta-almost two-universal families of hash functions. The generalized Leftover Hash Lemma has applications in cryptography, e.g., for key agreement in the presence of an adversary who is not restricted to classical information processing.
I. INTRODUCTION
The paper begins by introducing uniform-randomness extraction, then extends the setting to side information stored in a quantum state.
- The discussion first considers extracting uniform randomness from a random variable.
- It then extends randomness extraction to side information potentially stored in a quantum state.
A. Randomness Extraction
The Leftover Hash Lemma asks how much randomness can be extracted from X despite correlated side information E, and answers that sufficiently high conditional min-entropy enables near-uniform hashed output.
- The extraction problem is to compute a string Z from X that is completely unknown, or uniform, conditioned on correlated side information E.The section also asks for the maximum size and computation method of Z.
- The extractable length ℓ is approximately the conditional min-entropy Hmin(X|E).The hash output is formed using a function selected from a two-universal family.
- A two-universal hash family maps X to {0, 1}^ℓ, and the output Z := f(X) is, on average over f, ∆-close to uniform conditioned on E.
- For any fixed joint distribution of X and E, some fixed function f extracts almost uniform randomness.This follows from the average guarantee over the hash-family choices.
- Two-universal hashing supports privacy amplification, transforming a weakly secret key into a highly secret key against an adversary with partial knowledge.
B. Quantum Side Information
Classical side-information models are insufficient in general because quantumly stored information can preserve knowledge about extractor outputs that classical information of the same size would not. The paper therefore extends min-entropy, uniformity, and the Leftover Hash Lemma to quantum side information.
- Quantum side information can leave extractor outputs partially known even when same-sized classical side information makes them almost uniform.
- The paper studies randomness extraction when E is quantum-mechanical, including cases where E is partly or fully classical.
- A quantum-conditioned uniform output has joint state ωZ⊗ρE, with ωZ the maximally mixed state.Approximate uniformity is defined by trace distance from ωZ⊗σE.
- Trace distance is used because it corresponds to distinguishing advantage and reduces to statistical distance in the classical case.
- Conditional min-entropy extends to quantum E and measures the probability of guessing X with an optimal strategy using E.
- The number ℓ of perfectly uniform bits extractable relative to E is upper bounded by Hmin(X|E).This bound is presented as a converse to the extraction bound.
- Smooth min-entropy accommodates approximately uniform extraction, and the extended lemma reaches its bound up to additive terms of order log(1/∆).
C. Almost Two-Universal Hashing
The paper considers hash families with collision probability δ beyond the standard two-universal case, where δ = 1/|Z|.
- A family is two-universal when distinct inputs collide with probability at most δ := 1/|Z|.
- The notion extends to δ-almost two-universal families with arbitrary collision probabilities δ.
- The standard two-universal family is the special case δ = 1/|Z|.
- The classical Leftover Hash Lemma has a generalization to δ-almost two-universal hash functions, bounding the distance from uniform for an extracted ℓ-bit string.
D. Main result
The paper generalizes the Leftover Hash Lemma to quantum side information and arbitrary δ-almost two-universal hash families. Its bound is essentially achievable, while the standard two-universal specialization requires a separate tighter proof.
- D. Main result: The main result applies to δ-almost two-universal hash families when side information E is quantum.The classical special case δ = 2^-ℓ was previously known, but the arbitrary-δ statement is new.
- D. Main result: On average over the hash choice, Z := f(X) is Δ-close to uniform conditioned on quantum E.The output range is {0, 1}^ℓ, and the bound is expressed using conditional min-entropy.
- D. Main result: The extractable-bit bound can be reached up to additive terms of order log(1/Δ).This establishes smooth conditional min-entropy as an accurate measure of extractable uniform randomness.
- D. Main result: Substituting δ = 2^-ℓ into the first bound gives a less tight formula than the specialized bound in (8).The tighter expression therefore requires a separate proof.
E. Applications and Related Work
The generalized lemma supports privacy amplification and randomness extraction when adversaries or devices may retain quantum side information. Combined with suitable hash constructions, it can shorten random seeds while preserving extractable key length up to a logarithmic term.
- E. Applications and Related Work: Quantum Leftover Hash Lemmas support privacy amplification against adversaries whose side information is gathered during key agreement and may be quantum.This is particularly relevant to quantum cryptography and quantum key distribution.
- E. Applications and Related Work: A suitable δ-almost two-universal construction can shorten the seed from Θ(n) to a length proportional to ℓ and log n.Here n is the original partially secret string length and ℓ is the extracted key length.
- E. Applications and Related Work: The extracted secret-key length is reduced only by a term proportional to log 1/Δ compared with two-universal hashing.The generalized lemma also permits extending existing cryptographic security proofs to δ-almost two-universal families.
- E. Applications and Related Work: The classical technique of XORing a source with a δ-biased mask has also been shown to produce a uniformly distributed string against quantum side information.This result is cited as related work on randomness extraction with quantum side information.
- E. Applications and Related Work: Trevisan-style extractors have been studied to obtain seed lengths O(polylog n), with key length ℓ ≈ Hmin(X) − log dim H_E in one cited result.Later work extends this to conditional min-entropies, which can yield larger key lengths.
- E. Applications and Related Work: The quantum lemma should replace the classical lemma when extracted randomness must remain random conditioned on a device’s internal quantum state.Using the classical lemma there would implicitly assume that the device does not exploit quantum mechanics.
F. Organization of the paper
The paper develops the smooth-entropy framework, proves generalized Leftover Hash Lemmas, and then applies known hash constructions to shorter-seed randomness extraction. An appendix contains material noted as potentially independently interesting.
- F. Organization of the paper: Section II reviews smooth entropy concepts needed for the proof.These concepts support the later formulation in terms of smooth min-entropy.
- F. Organization of the paper: Section III proves the generalized Leftover Hash Lemma, including two-universal and δ-almost two-universal versions in terms of smooth min-entropy.The relevant statements are Theorems 9 and 10.
- F. Organization of the paper: Section IV combines known δ-almost two-universal hash constructions and discusses their use for randomness extraction with shorter random seeds.The paper also points to practical privacy-amplification implementations in the surrounding discussion.
- F. Organization of the paper: Appendix B may be of independent interest.The supplied passage ends before stating the appendix’s specific content.
II. SMOOTH ENTROPIES
This section defines smooth min-entropy and related quantum entropies and metrics for quantifying uncertainty with quantum side information. It also establishes that collision entropy bounds min-entropy and that smoothing can preserve classical–quantum structure.
- Distance measures: Purified distance is monotone under trace non-increasing completely positive maps, including projections.It upper-bounds trace distance and supports the smoothing constructions used later.
- Smooth min-entropy: Smooth min-entropy maximizes conditional min-entropy over states within an ε-ball defined using purified distance.The smoothing framework uses sub-normalized states and purified-distance neighborhoods.
- Conditional min-entropy: Conditional min-entropy quantifies uncertainty about system A given quantum side information B.For classical–quantum states, it admits a guessing-probability interpretation.
- Collision entropy: Conditional collision entropy is defined through Γ_C(ρ_AB|σ_B), and collision entropy provides an upper bound on min-entropy.The latter relation is identified as a main technical contribution proved in the appendix.
III. PROOF OF THE LEFTOVER HASH LEMMA
The proof models privacy amplification with quantum side information as a completely positive map and bounds output distance from uniform through collision entropy and smooth min-entropy. The resulting theorems cover both two-universal and δ-almost two-universal hashing in the strong-extractor regime.
- State transformation: Randomness extraction maps a CQ input state ρ_XE and random hash choice F to an output state ρ_FZE via a trace-preserving CPM.The extracted string is Z=f(X), while F is retained as published hash-function information.
- Collision-entropy bound: Lemma 5 bounds the output collision entropy for a δ-almost two-universal family in terms of the input collision entropy.The proof evaluates the hash-family average using the collision bound for distinct inputs.
- Strong extractor regime: The bounds concern Δ(Z|FE), conditioning on both the extracted hash output’s published function F and quantum side information E.This is the strong extractor setting, where the selected hash function is published after use.
- Two-universal hashing: Theorem 6 gives a smooth-min-entropy bound on distance from uniform for two-universal hashing.The proof combines the collision-entropy estimate with smoothing and monotonicity of purified distance.
- δ-almost two-universal hashing: Theorem 7 extends the distance-from-uniform bound to δ-almost two-universal hashing, with an additional smoothing parameter ¯ε.The proof introduces a second nearby CQ state before applying the collision-entropy estimate.
- Recovery of the lemma: Setting ε=0 in the later theorems recovers the introductory Leftover Hash Lemma.The theorem statements can also be expressed using distance from uniform averaged over the choice of hash function.
IV. EXPLICIT CONSTRUCTIONS WITH SHORTER SEEDS
This section develops explicit two-universal and δ-almost two-universal hash families, then combines them to reduce the random-seed length from dependence on the input length toward dependence on the extracted key length.
- Design objective: The construction scenario uses an n-bit input X, quantum side information E, and a seed length s=log|F| that should remain small.Small seeds matter in implementations where the chosen hash function must be communicated, such as QKD.
- Polynomial construction: A polynomial-based family over a finite field is δ-almost two-universal with δ=(r−1)/|F|.The verification uses that a degree-(r−1) polynomial has at most r−1 zeros.
- Concatenation: Concatenating δ1-almost and δ2-almost two-universal families yields a (δ1+δ2)-almost two-universal family.The composed family consists of functions f2∘f1.
- Baseline construction: The standard two-universal construction recovers Renner’s result when seed length is not optimized.Its proof uses a family with s=log|F|=n.
- Shorter seeds: Theorem 10 constructs a family whose seed length s is proportional to the output length ℓ rather than the input length n.The construction concatenates a polynomial-based hash to k bits with a two-universal hash from k bits to ℓ bits, giving s=2k.
- Shorter-seed guarantee: The concatenated construction achieves δ1+δ2≤1+4ε^2 over 2^ℓ for its almost-two-universal guarantee.The bound follows from the chosen block parameter and the two-universal second stage.
Appendix A: Technical Results
The appendix supplies technical tools for manipulating purifications, projections, operator norms, and smoothed CQ states. These results support the quantum-information bounds used in the main proof.
- Purifications and extensions: Purifications and extensions can be chosen to preserve purified distance between states.The extension statement applies the purification result to a larger bipartite system.
- Dual operators: Every linear operator on one subsystem of a pure bipartite state has a dual operator on the other subsystem.The dual action is expressed using a transpose in the Schmidt basis.
- Projection bounds: Projecting a state does not increase its purified distance from the projected state’s comparison framework.The proof uses a fidelity bound based on tr(Πρ)≤tr(ρ).
- Operator inequality: A three-operator Hölder inequality is stated for linear operators and the trace norm.This inequality is used in the technical collision-entropy arguments.
- CQ smoothing: Smoothing a CQ state need not destroy its CQ structure.Measuring the classical register preserves proximity and does not decrease min-entropy, so an optimum can be chosen CQ.
Appendix B: Alternative Entropic Quantities
Appendix B develops alternative conditional min- and max-entropy quantities, their smooth versions, and relationships needed for the paper’s entropy bounds. It establishes invariance, duality, and equivalence properties, then connects collision entropy to min-entropy.
- Definitions: The appendix defines conditional min-entropy and an alternative min-entropy, along with their smooth versions for systems A conditioned on B.The smooth max-entropies are subsequently defined as duals of the smooth min-entropies.
- Invariance and duality: Max-entropies are well-defined because min-entropies are invariant under local isometries on the purifying system and therefore independent of the chosen purification.The alternative max-entropy is defined through duality, and corresponding invariance properties are established for local isometries.
- Equivalence results: The two smooth min-entropies and two smooth max-entropies are pairwise equivalent up to terms in log ε.The appendix states this equivalence as a central lemma, with constants depending on ε and ε′.
- Technical lemmas: Lemma 21 constructs a nearby state with controlled conditional min-entropy by projecting onto suitable eigenspaces while keeping purified distance at most ε.The proof selects a projector retaining sufficient weight of ρ_B and bounds the relevant operator norm using the dual projector.
- Collision-entropy relation: The appendix relates collision entropy to min-entropy through relative-entropy inequalities and applies the result to prove Lemma 3.The proof applies the intermediate bound to the state and marginal optimizing the conditional min-entropy.