Sampling of Min-Entropy Relative to Quantum Knowledge
Let X(1), ..., 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(1) ... 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 model-using a standard sample-and-hash protocol-is fully secure against quantum adversaries, thus solving a long-standing open problem.
sampling min-entropy bounded-storage model privacy amplification quantum cryptography quantum extractors randomness extraction