---
res:
bibo_abstract:
- "A chain rule for an entropy notion H(.) states that the entropy H(X) of a variable
X decreases by at most l if conditioned on an l-bit string A, i.e., H(X|A)>=
H(X)-l. More generally, it satisfies a chain rule for conditional entropy if H(X|Y,A)>=
H(X|Y)-l.\r\n\r\nAll natural information theoretic entropy notions we are aware
of (like Shannon or min-entropy) satisfy some kind of chain rule for conditional
entropy. Moreover, many computational entropy notions (like Yao entropy, unpredictability
entropy and several variants of HILL entropy) satisfy the chain rule for conditional
entropy, though here not only the quantity decreases by l, but also the quality
of the entropy decreases exponentially in l. However, for \r\nthe standard notion
of conditional HILL entropy (the computational equivalent of min-entropy) the
existence of such a rule was unknown so far.\r\n\r\nIn this paper, we prove that
for conditional HILL entropy no meaningful chain rule exists, assuming the existence
of one-way permutations: there exist distributions X,Y,A, where A is a distribution
over a single bit, but $H(X|Y)>>H(X|Y,A)$, even if we simultaneously allow
for a massive degradation in the quality of the entropy.\r\n\r\nThe idea underlying
our construction is based on a surprising connection between the chain rule for
HILL entropy and deniable encryption. @eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Stephan
foaf_name: Krenn, Stephan
foaf_surname: Krenn
foaf_workInfoHomepage: http://www.librecat.org/personId=329FCCF0-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Krzysztof Z
foaf_name: Pietrzak, Krzysztof Z
foaf_surname: Pietrzak
foaf_workInfoHomepage: http://www.librecat.org/personId=3E04A7AA-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Akshay
foaf_name: Wadia, Akshay
foaf_surname: Wadia
bibo_doi: 10.1007/978-3-642-36594-2_2
bibo_volume: 7785
dct_date: 2013^xs_gYear
dct_language: eng
dct_publisher: Springer@
dct_title: A counterexample to the chain rule for conditional HILL entropy, and
what deniable encryption has to do with it@
...