Non-malleable Extractors & Symmetric Key Cryptography from Weak Secrets
Speaker: Yevgeniy Dodis , NYU
Date: April 3 2009
Time: 10:30AM to 12:00PM
Location: 32-G449
Contact: be, 3 6098, imbe
Relevant URL: http://eprint.iacr.org/2008/503
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 *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 *active* adversary Eve. We show
that non-interactive (single-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-message protocol extracting nearly k
random bits. This dramatically improves the only previously known
protocol of Renner and Wolf [RW03], which required O(s) rounds where s
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 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.
Joint work with Daniel Wichs from STOC 2009.
Paper available at http://eprint.iacr.org/2008/503
See other events that are part of CIS/Microsoft Seminars 2008/2009
See other events happening in April 2009
