TY - JOUR

T1 - Sampling of min-entropy relative to quantum knowledge

AU - König, Robert

AU - Renner, Renato

N1 - Funding Information:
Manuscript received November 30, 2009; revised January 24, 2011; accepted January 26, 2011. Date of current version June 22, 2011. R. König was supported by NSF Grants PHY-04056720, PHY-0803371, and SNF PA00P2-126220. R. Renner was supported by the Swiss National Science Foundation under Grant 200021-119868. R. König is with the Institute for Quantum Information, California Institute of Technology, Pasadena, CA 91125 USA (e-mail: [email protected]). R. Renner is with the Institute for Theoretical Physics, ETH Zurich, 8093 Zurich, Switzerland (e-mail: [email protected]). Communicated by P. Hayden, Associate Editor for Quantum Information Theory. Digital Object Identifier 10.1109/TIT.2011.2146730 1See Lemma V.1 of Section V-B for a mathematically precise statement. 2Nisan and Zuckerman considered the special case where is classical.

PY - 2011/7

Y1 - 2011/7

N2 - Let X1, ⋯, Xn be a sequence of n classical random variables and consider a sample Xs1, ⋯, Xsr of r ≤ n positions selected at random. Then, except with (exponentially in r) small probability, the min-entropy Hmin(Xs1, ⋯, Xsr) of the sample is not smaller than, roughly, a fraction r/n} of the overall entropy Hmin(X1⋯Xn), 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 Hmin 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.

AB - Let X1, ⋯, Xn be a sequence of n classical random variables and consider a sample Xs1, ⋯, Xsr of r ≤ n positions selected at random. Then, except with (exponentially in r) small probability, the min-entropy Hmin(Xs1, ⋯, Xsr) of the sample is not smaller than, roughly, a fraction r/n} of the overall entropy Hmin(X1⋯Xn), 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 Hmin 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.

KW - Bounded-storage model

KW - min-entropy

KW - privacy amplification

KW - quantum cryptography

KW - quantum extractors

KW - randomness extraction

KW - sampling

UR - http://www.scopus.com/inward/record.url?scp=79959564588&partnerID=8YFLogxK

U2 - 10.1109/TIT.2011.2146730

DO - 10.1109/TIT.2011.2146730

M3 - Article

AN - SCOPUS:79959564588

SN - 0018-9448

VL - 57

SP - 4760

EP - 4787

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 7

M1 - 5895072

ER -