Paper 2014/678
A Counterexample to the Chain Rule for Conditional HILL Entropy
Stephan Krenn, Krzysztof Pietrzak, Akshay Wadia, and Daniel Wichs
Abstract
Most entropy notions $H(.)$ like Shannon or minentropy satisfy a chain rule stating that for random variables $X,Z$ and $A$ we have $H(XZ,A)\ge H(XZ)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 unpredictabilityentropy. For HILL entropy, the computational analogue of minentropy, the chain rule is of special interest and has found many applications, including leakageresilient 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(XZ)$ is large but $H_\infty(XZ,A)$ is basically zero. Our counterexample just makes the minimal assumption that ${\bf NP}\nsubseteq{\bf P/poly}$. Under the stronger assumption that injective oneway 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.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 A major revision of an IACR publication in TCC 2013
 Keywords
 Computational EntropyHILL EntropyChain RuleLossy FunctionsDeniable Encryption
 Contact author(s)
 krzpie @ gmail com
 History
 20140831: received
 Short URL
 https://ia.cr/2014/678
 License

CC BY
BibTeX
@misc{cryptoeprint:2014/678, author = {Stephan Krenn and Krzysztof Pietrzak and Akshay Wadia and Daniel Wichs}, title = {A Counterexample to the Chain Rule for Conditional {HILL} Entropy}, howpublished = {Cryptology {ePrint} Archive, Paper 2014/678}, year = {2014}, url = {https://eprint.iacr.org/2014/678} }