Paper 2008/503 Original: eprint.iacr.org/2008/503 ↗

Non-Malleable Extractors and Symmetric Key Cryptography from Weak Secrets

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.