Welcome to the resource topic for 2008/503
Title:
Non-Malleable Extractors and Symmetric Key Cryptography from Weak Secrets
Authors: Yevgeniy Dodis, Daniel Wichs
Abstract:We study the question of basing symmetric key cryptography on weak secrets. In this setting, Alice and Bob share an n-bit secret W, which might not be uniformly random, but the adversary has at least k bits of uncertainty about it (formalized using conditional min-entropy). Since standard symmetric-key primitives require uniformly random secret keys, we would like to construct an authenticated key agreement protocol in which Alice and Bob use W to agree on a nearly uniform key R, by communicating over a public channel controlled by an active adversary Eve. We study this question in the information theoretic setting where the attacker is computationally unbounded. We show that single-round (i.e. one message) protocols do not work when k < n/2, and require poor parameters even when n/2< k << n. On the other hand, for arbitrary values of k, we design a communication efficient two-round (challenge-response) protocol extracting nearly k random bits. This dramatically improves the only previously known protocol of Renner and Wolf~\cite{RennerW03}, which required O(\lambda) rounds where \lambda is the security parameter. Our solution takes a new approach by studying and constructing non-malleable'' seeded randomness extractors --- if an attacker sees a random seed $X$ and comes up with an arbitrarily related seed $X'$, then we bound the relationship between $R= \Ext(W;X)$ and $R' = \Ext(W;X')$. We also extend our two-round key agreement protocol to the fuzzy’’ setting, where Alice and Bob share ``close’’ (but not equal) secrets W_A and W_B, and to the Bounded Retrieval Model (BRM) where the size of the secret W is huge.
ePrint: https://eprint.iacr.org/2008/503
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 .