Welcome to the resource topic for 2004/219
Title:
Entropic Security and the Encryption of High Entropy Messages
Authors: Yevgeniy Dodis, Adam Smith
Abstract:Russell and Wang (Eurocrypt 2002) recently introduced an elegant,
information-theoretic notion called entropic security of
encryption: they required that the cipher text leak no predicate of
the plaintext (similar to semantic security (Goldwasser and Micali,
JCSS 1984)) but only as long as the distribution on messages has high
entropy from the adversary’s point of view. They show that this
notion of security can be achieved with very short keys for
entropically rich message spaces. Canetti, Miccianci and Reingold
(STOC, 1998) had previously constructed hash functions which satisfy a
similar entropic security condition. The output of such hash function
leaks no partial information about the input, provided the input has
sufficiently high entropy. This paper studies entropic security in
general, and its application to the encryption of high-entropy
messages.
(1) We elucidate the notion of entropic security. Our results apply to
all entropically-secure primitives, including both encryption and hash
functions. We strengthen the formulation of Canetti and Russell and
Wang: we require that an entropically-secure primitive leak no
function whasoever of its input, while the previous works focus only
on predicates. This stronger formulation is much closer to the
original notion of semantic security. We also show that entropic
security is equivalent to indistinguishability on pairs of input
distributions of sufficiently high entropy. This equivalence
generalizes the conventional equivalence between indistinguishability
and semantic security. Indistinguishability, in turn, is related to
randomness extraction from non-uniform distributions. The proof of
the equivalence of hiding predicates to hiding all functions is quite
involved, and requires very different techniques from those of
Goldwasser and Micali.
(2) We use the equivalence above, and the connection to randomness
extraction, to prove several new results on entropically-secure
encryption. We obtain:
(a) Two general frameworks for constructing entropically secure
encryption schemes, one based on expander graphs and the other on
XOR-universal hash functions. These schemes generalize the schemes of
Russell and Wang, yielding simpler constructions and proofs as well as
improved parameters. The best scheme uses a key of length
k=n-t+2log(1/eps)+O(1), where eps is a measure of leakage and
t is the initial min-entropy of the message.
(b) Lower bounds on the key length k for entropic security and
indistinguishability. In particular, we show near tightness of
Russell-Wang constructions: k > n-t. (In fact, for a large class
of schemes k >= n-t + log(1/eps).)
ePrint: https://eprint.iacr.org/2004/219
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .