Author_Institution :
Dept. of Comput. Sci., New York Univ., New York, NY, USA
Abstract :
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 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 and improved entropy loss for the leftover hash lemma.
Keywords :
cryptography; entropy; statistical distributions; cryptographic primitive; elementary inequality; entropy loss; leakage-resilient symmetric encryption; leftover hash lemma; nonmalleable extractor; seed-dependent condenser; uniform distribution; variance; weak expectation bound; Encryption; Entropy; Games; Information theory; Random variables;