IACR News item: 31 August 2014
Stephan Krenn, Krzysztof Pietrzak, Akshay Wadia, Daniel Wichs
ePrint ReportSuch 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 \\emph{single} bit, such that the HILL entropy $H_\\infty(X|Z)$ is
large but $H_\\infty(X|Z,A)$ is basically zero.
Our counterexample just makes the minimal assumption that
${\\bf NP}\\nsubseteq{\\bf P/poly}$. Under the stronger assumption that
injective one-way function exist, we can make all the distributions efficiently samplable.
Finally, 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.
Additional news items may be found on the IACR news page.