2013 | OriginalPaper | Buchkapitel
A Counterexample to the Chain Rule for Conditional HILL Entropy
And What Deniable Encryption Has to Do with It
verfasst von : Stephan Krenn, Krzysztof Pietrzak, Akshay Wadia
Erschienen in: Theory of Cryptography
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
A chain rule for an entropy notion
H
(·) states that the entropy
H
(
X
) of a variable
X
decreases by at most ℓ if conditioned on an ℓ-bit string
A
, i.e.,
H
(
X
|
A
) ≥
H
(
X
) − ℓ. More generally, it satisfies a chain rule for
conditional
entropy if
H
(
X
|
Y
,
A
) ≥
H
(
X
|
Y
) − ℓ.
All 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 ℓ, but also the
quality
of the entropy decreases exponentially in ℓ. However, for the standard notion of conditional HILL entropy (the computational equivalent of min-entropy) the existence of such a rule was unknown so far.
In 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
HILL
(X|Y)≫
H
HILL
(X|Y,A), even if we simultaneously allow for a massive degradation in the quality of the entropy.
The idea underlying our construction is based on a surprising connection between the chain rule for HILL entropy and deniable encryption.