Sampling of min-entropy relative to quantum knowledge

Let X₁, ⋯, X_n be a sequence of n classical random variables and consider a sample X_s1, ⋯, X_sr of r ≤ n positions selected at random. Then, except with (exponentially in r) small probability, the min-entropy H_min(X_s1, ⋯, X_sr) of the sample is not smaller than, roughly, a fraction r/n} of the overall entropy H_min(X₁⋯X_n), 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-entropy H_min 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 modelusing a standard sample-and-hash protocolis fully secure against quantum adversaries, thus solving a long-standing open problem.