Sampling of min-entropy relative to quantum knowledge

Abstract

Let X_1, ..., X_n be a sequence of n classical random variables and consider a sample of r positions selected at random. Then, except with (exponentially in r) small probability, the min-entropy of the sample is not smaller than, roughly, a fraction r/n of the total min-entropy of all positions X_1, ..., X_n, which is optimal. Here, we show that this statement, originally proven by Vadhan [LNCS, vol. 2729, Springer, 2003] for the purely classical case, is still true if the min-entropy is measured relative to a quantum system. Because min-entropy quantifies the amount of randomness that can be extracted from a given random variable, our result can be used to prove the soundness of locally computable extractors in a context where side information might be quantum-mechanical. In particular, it implies that key agreement in the bounded-storage model (using a standard sample-and-hash protocol) is fully secure against quantum adversaries, thus solving a long-standing open problem.

48 pages, latex

References in corpus (11)

• The operational meaning of min- and max-entropy
• Min- and Max- Relative Entropies and a New Entanglement Monotone
• Coding Theorem and Strong Converse for Quantum Channels
• Symmetry implies independence
• Cryptography from Noisy Storage
• A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs
• The Bounded Storage Model in The Presence of a Quantum Adversary
• Conditional Density Operators and the Subjectivity of Quantum Operations
• Universally composable privacy amplification against quantum adversaries
• A New Proof of the Channel Coding Theorem via Hypothesis Testing in Quantum Information Theory
• Unconditional security of continuous-variable quantum key distribution

Cited by in corpus (35)

• The Security of Practical Quantum Key Distribution
• Quantum Random Number Generators
• The operational meaning of min- and max-entropy
• Entropic Uncertainty Relations and their Applications
• Fully device independent quantum key distribution
• Leftover Hashing Against Quantum Side Information
• Unconditional security from noisy quantum storage
• Trevisan's extractor in the presence of quantum side information
• Device-independent randomness expansion against quantum side information
• A Comprehensive Review of Quantum Random Number Generators: Concepts, Classification and the Origin of Randomness
• Entanglement sampling and applications
• Noisy channel coding via privacy amplification and information reconciliation
• A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs
• Experimental Realization of Device-Independent Quantum Randomness Expansion
• Real-Time Source Independent Quantum Random Number Generator with Squeezed States
• Security of quantum key distribution from generalised entropy accumulation
• Dual universality of hash functions and its applications to quantum cryptography
• A framework for quantum-secure device-independent randomness expansion
• Simple Protocols for Oblivious Transfer and Secure Identification in the Noisy-Quantum-Storage Model
• Quantum Side Information: Uncertainty Relations, Extractors, Channel Simulations
• Quantum-proof randomness extractors via operator space theory
• The Physics of Quantum Information: Complementarity, Uncertainty, and Entanglement
• Hiding Ignorance Using High Dimensions
• Variations on Classical and Quantum Extractors
• Numerical Framework for Semi-Device-Independent Quantum Random Number Generators
• Cryptomite: A versatile and user-friendly library of randomness extractors
• Inevitability of knowing less than nothing
• Bitwise Quantum Min-Entropy Sampling and New Lower Bounds for Random Access Codes
• Sampled sub-block hashing for large input randomness extraction
• Reciprocal ontological models show indeterminism of the order of quantum theory
• Quantum-Proof Extractors: Optimal up to Constant Factors
• Better short-seed quantum-proof extractors
• Average Rényi Entanglement Entropy in Gaussian Boson Sampling
• Short seed extractors against quantum storage
• Computational Monogamy of Entanglement and Non-Interactive Quantum Key Distribution