2007/12/28 by Robert Koenig, Robert König, Renato Renner · 67 citations
Computer Science · Mathematics · Physics and Astronomy · #Bounded function #Chaos-based Image/Signal Encryption #Combinatorics #Computability, Logic, AI Algorithms #Cryptography and Data Security #Discrete mathematics #Entropy (arrow of time) #Entropy rate #Joint quantum entropy #Kullback–Leibler divergence #Mathematical analysis #Mathematics #Min entropy #Physics #Principle of maximum entropy #Quantum #Quantum discord #Quantum entanglement #Quantum mechanics #Quantum relative entropy #Random variable #Randomness #Statistical physics #Statistics #Upper and lower bounds #quant-ph
paper · pdf · doi:10.1109/tit.2011.2146730
published in IEEE Transactions on Information Theory 57(7), 4760-4787 (Institute of Electrical and Electronics Engineers) · 48 pages, latex
arxiv created 2007/12/28 · openalex publication_date 2011/06/21 · arxiv updated 2012/06/04 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05
LetX1, …, Xnbe a sequence ofnclassical random variables and consider a sampleXs1, …, Xsrofr ≤ npositions selected at random. Then, except with (exponentially inr) small probability, the min-entropyHmin(Xs1 ⋯ Xsr)of the sample is not smaller than, roughly, a fractionr\over nof the overall entropyHmin(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-entropyHminis 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.