Yevgeniy Dodis talk, Wednesday
David Kempe
We have another theory colloquium for the semester: Yevgeniy Dodis
from NYU will be giving a talk this Wednesday at 3:30.
Notice the unusual location. All the key information is below.
Looking forward to seeing many of you there.
(And mark Tuesday, 05/10, for big theory festivities: all my students,
Abhimanyu Das, Mahyar Salek, and Po-An Chen, will be defending their
PhD theses that day.)
Speaker: Prof. Yevgeniy Dodis, NYU
Title: Leftover Hash Lemma, Revisited
Time: Wednesday, 04/27, 3:30 PM
Location: GFS 118
Abstract:
The famous Leftover Hash Lemma (LHL) states that (almost) universal
hash functions are good randomness extractors. Despite its numerous
applications, LHL-based extractors suffer from the following two
drawbacks:
(1) Large Entropy Loss: to extract v bits from distribution X of
min-entropy m which are e-close to uniform, one must set v <= m -
2*log(1/e), meaning that the entropy loss L = m-v >= 2*log(1/e).
(2) Large Seed Length: the seed length n of universal hash function
required by the LHL must be linear in the length of the source.
Quite surprisingly, we show that both limitations of the LHL --- large
entropy loss and large seed --- can often be overcome (or, at least,
mitigated) in various quite general scenarios. First, we show that
entropy loss could be reduced to L=log(1/e) for the setting of
deriving secret keys for a wide range of cryptographic applications,
including *all* "unpredictability" applications (signatures, MACs,
etc.) and also some prominent "indistinguishability" applications,
including chosen plaintext (or ciphertext) attack secure (public- or
symmetric-key) encryption schemes. Specifically, the security of these
schemes gracefully degrades from e to at most e + sqrt(e *
2^{-L}).(Notice that, unlike standard LHL, this bound is meaningful
even for negative entropy loss, when we extract more bits than the the
min-entropy we have!)
Second, we study the soundness of the natural *expand-then-extract*
approach, where one uses a pseudorandom generator (PRG) to expand a
short "input seed" S into a longer "output seed" S', and then use the
resulting S' as the seed required by the LHL (or, more generally, any
randomness extractor). Unfortunately, we show that, in general,
expand-then-extract approach is not sound if the Decisional
Diffie-Hellman assumption is true. Despite that, we show that it is
sound either: (1) when extracting a "small" (logarithmic in the
security of the PRG) number of bits; or (2) in *minicrypt*.
Implication (2) suggests that the sample-then-extract approach is
likely secure when used with "practical" PRGs, despite lacking a
reductionist proof of security!
The paper can be found at http://eprint.iacr.org/2011/088
Bio:
Yevgeniy Dodis is an Associate Professor of computer science at New
York University, which he joined in 2001 after receiving his PhD at
MIT in 2000 and being a post-doc at IBM T.J.Watson Research center.
He also spent 2007-2008 academic year visiting the CRCS center at
Harvard University.
Dr. Dodis' research is primarily in cryptography and network security.
In particular, he worked in a variety of areas including
leakage-resilient cryptography, cryptography under weak randomness,
cryptography with biometrics and other noisy data, hash function and
block cipher design, protocol composition and information-theoretic
cryptography. Dr. Dodis has more than 90 scientific publications at
various conferences, journals and other venues, has been on program
committees of many international conferences (including FOCS, STOC,
CRYPTO and Eurocrypt), and gave numerous invited lectures and courses
at various venues. Dr. Dodis is the recipient of National Science
Foundation CAREER Award, IBM Faculty Award, Google Faculty Award and
Best Paper Award at 2005 Public Key Cryptography Conference. As an
undergraduate student, he was also a winner of the US-Canada Putnam
Mathematical Competition in 1995.
--
David Kempe <dke...@usc.edu>