Technical Program

Paper Detail

Paper Title Strong Chain Rules for Min-Entropy under Few Bits Spoiled
Paper IdentifierTU3.R6.2
Authors Maciej Skorski, IST Austria, Austria
Session New Developments in Renyi Entropy
Location Sorbonne, Level 5
Session Time Tuesday, 09 July, 14:30 - 16:10
Presentation Time Tuesday, 09 July, 14:50 - 15:10
Manuscript  Click here to download the manuscript
Abstract Abstract—It is well established that the notion of min-entropy fails to satisfy the chain rule of the form H(X; Y ) = H(XjY )+H(Y ), known for Shannon Entropy. The lack of a chain rule causes a lot of technical difficulties, particularly in cryptography where the chain rule would be a natural way to analyze how min-entropy is split among smaller blocks. Such problems arise for example when constructing extractors and dispersers. We show that any sequence of variables exhibits a very strong strong block-source structure (conditional distributions of blocks are nearly flat) when we spoil few correlated bits. This implies, conditioned on the spoiled bits, that splitting-recombination properties hold. In particular, we have many nice properties that min-entropy doesn’t obey in general, for example: strong chain rules, “information can’t hurt” inequalities, equivalences of average and worst-case conditional entropy definitions and others. Quantitatively, for any sequence X_1 ,...,X_t of random variables over an alphabet of size N we prove that, when conditioned on m = t*O(log log N + log log(1/\eps) + log t) bits of auxiliary information, all conditional distributions of the form X_i|X_{