---
res:
bibo_abstract:
- "Most entropy notions H(.) like Shannon or min-entropy satisfy a chain rule stating
that for random variables X,Z, and A we have H(X|Z,A)≥H(X|Z)−|A|. That is, by
conditioning on A the entropy of X can decrease by at most the bitlength |A| of
A. Such chain rules are known to hold for some computational entropy notions like
Yao’s and unpredictability-entropy. For HILL entropy, the computational analogue
of min-entropy, the chain rule is of special interest and has found many applications,
including leakage-resilient cryptography, deterministic encryption, and memory
delegation. These applications rely on restricted special cases of the chain rule.
Whether the chain rule for conditional HILL entropy holds in general was an open
problem for which we give a strong negative answer: we construct joint distributions
(X,Z,A), where A is a distribution over a single bit, such that the HILL entropy
H HILL (X|Z) is large but H HILL (X|Z,A) is basically zero.\r\n\r\nOur counterexample
just makes the minimal assumption that NP⊈P/poly. Under the stronger assumption
that injective one-way function exist, we can make all the distributions efficiently
samplable.\r\n\r\nFinally, we show that some more sophisticated cryptographic
objects like lossy functions can be used to sample a distribution constituting
a counterexample to the chain rule making only a single invocation to the underlying
object.@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
orcid: 0000-0003-2835-9093
- 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
orcid: 0000-0002-9139-1654
- foaf_Person:
foaf_givenName: Akshay
foaf_name: Wadia, Akshay
foaf_surname: Wadia
- foaf_Person:
foaf_givenName: Daniel
foaf_name: Wichs, Daniel
foaf_surname: Wichs
bibo_doi: 10.1007/s00037-015-0120-9
bibo_issue: '3'
bibo_volume: 25
dct_date: 2016^xs_gYear
dct_language: eng
dct_publisher: Springer@
dct_title: A counterexample to the chain rule for conditional HILL entropy@
...