Overcoming Weak Expectations: Yevgeniy Dodis, New York University

Starts:
10:00 am on Monday, March 18, 2013
Ends:
12:00 pm on Monday, March 18, 2013
Location:
MCS 137
Recently, there has been renewed interest in basing cryptographic primitives on weak secrets, where the only information about the secret is some non-trivial amount of (min-)entropy. From a formal point of view, such results require to upper bound the expectation of some function f(X), where X is a weak source in question. We show an elementary inequality which essentially upper bounds such "weak expectation" by two terms, the first of which is *independent* of f, while the second only depends on the variance of f under the *uniform* distribution. Quite remarkably, as relatively simple corollaries of this elementary inequality, we obtain some "unexpected" results, in several cases noticeably simplifying/improving prior techniques for the same problem. Examples include non-malleable extractors, leakage-resilient symmetric encryption, seed-dependent condensers, improved entropy loss for the leftover hash lemma, and alternative to the dense model theorem.