Title: Key Derivation Without Entropy Waste
Speaker: Yevgeniy Dodis, NYU
Date: Wednesday, September 25, 2013 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We revisit the classical question of converting an imperfect source X of min-entropy k into a usable m-bit cryptographic key for some underlying application P. If P has security delta (against some class of attackers) with a uniformly random m-bit key, we seek to design a key derivation function (KDF) h that allows us to use R=h(X) as the key for P and results in comparable security delta' close to delta. Seeded randomness extractors provide a generic way to solve this problem provided that k > m + 2*log(1/delta), and this lower bound on k (called "RT-bound") is known to be tight in general. Unfortunately, in many situation the "waste" of 2*log(1/delta) bits of entropy is significant, motivating the question of designing KDFs with less waste for important special classes of sources X or applications P.I will discuss several positive and negative results in this regard.
The most surprising of them will be a positive result for all unpredictability applications P, yielding a provably secure KDF with entropy "waste" only loglog(1/delta) - an expenential improvement over the RT-bound.
See: http://www.math.rutgers.edu/~sk1233/theory-seminar/F13/