Sampling of Min-Entropy Relative to Quantum Knowledge

LetX₁, …, Xₙbe a sequence ofnclassical random variables and consider a sampleXs₁, …, Xsᵣofr ≤ npositions selected at random. Then, except with (exponentially inr) small probability, the min-entropyHₘᵢₙ(Xs₁ ⋯ Xsᵣ)of the sample is not smaller than, roughly, a fractionr nof the overall entropyHₘᵢₙ(X₁ ⋯ Xₙ), which is optimal. Here, we show that this statement, originally proved in [S. Vadhan, LNCS 2729, Springer, 2003] for the purely classical case, is still true if the min-entropyHₘᵢₙ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.