Paper 2008/503
NonMalleable Extractors and Symmetric Key Cryptography from Weak Secrets
Yevgeniy Dodis and 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 minentropy). Since standard symmetrickey 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 singleround (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 tworound (challengeresponse) 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 ``nonmalleable'' 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 tworound 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.
Note: The previous title of this paper was "Oneround Authenticated Key Agreement from Weak Secrets". The technical content of the paper has not changed, but we corrected our terminology. In our previous version, we referred to our two message (challengeresponse) protocol as "oneround" of interaction. Although we were explicit and consistent about the meaning of "round", the anonymous STOC reviewers correctly pointed out that this terminology is nonstandard and confusing and thus we have corrected it (and changed the title) for the final version. We now use "round" to refer to a single exchanged message.
Metadata
 Available format(s)
 PDF PS
 Category
 Secretkey cryptography
 Publication info
 Published elsewhere. Full version of STOC 2009 paper.
 Keywords
 Information Theoretic SecurityKey AgreementWeak Secrets
 Contact author(s)
 wichs @ cs nyu edu
 History
 20090405: last of 4 revisions
 20081202: received
 See all versions
 Short URL
 https://ia.cr/2008/503
 License

CC BY
BibTeX
@misc{cryptoeprint:2008/503, author = {Yevgeniy Dodis and Daniel Wichs}, title = {NonMalleable Extractors and Symmetric Key Cryptography from Weak Secrets}, howpublished = {Cryptology ePrint Archive, Paper 2008/503}, year = {2008}, note = {\url{https://eprint.iacr.org/2008/503}}, url = {https://eprint.iacr.org/2008/503} }