CryptoDB
One-Round Authenticated Key Agreement from Weak Secrets
| Authors: | |
|---|---|
| Download: | |
| Abstract: | We study the question of information-theoretically secure authenticated key agreement from weak secrets. In this setting, Alice and Bob share a $n$-bit secret $W$, which might \emph{not} be uniformly random but the adversary has at least $k$ bits of uncertainty about it (formalized using conditional min-entropy). Alice and Bob wish to use $W$ to agree on a nearly uniform secret key $R$, over a public channel controlled by an \emph{active} adversary Eve. We show that non-interactive (single-message) protocols do not work when $k\le \frac{n}{2}$, and require poor parameters even when $\frac{n}{2} < k\ll n$. On the other hand, for arbitrary values of $k$, we design a communication efficient {\em two-message (i.e, one-round!)} 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 \emph{``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 one-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. |
BibTeX
@misc{eprint-2008-18157,
title={One-Round Authenticated Key Agreement from Weak Secrets},
booktitle={IACR Eprint archive},
keywords={secret-key cryptography / Information Theoretic Security, Key Agreement, Weak Secrets},
url={http://eprint.iacr.org/2008/503},
note={ wichs@cs.nyu.edu 14217 received 28 Nov 2008, last revised 3 Dec 2008},
author={Yevgeniy Dodis and Daniel Wichs},
year=2008
}