Nonuniform Indistinguishability and Unpredictability Hardcore Lemmas: New Proofs and Applications to Pseudoentropy.
Maciej Skórski · 2015
Abstract. Hardcore lemmas are results in complexity theory which state that average-case hardness must have a very hard “kernel”, that is a subset of instances where the given problem is extremely hard. They find important applications in hardness amplification. In this paper we revisit the following two fundamental results: (a) The hardcore lemma for unpredictability, due to Impagliazzo (FOCS ’95). It states that if a boolean function f is “moderately ” hard to predict on average, then there must be a set of noticeable size on which f is “extremely ” hard to predict. (b) The hardcore lemma for indistinguishability, proved by Maurer and Tesaro (TCC’10), states that for two random variables X and Y which are -computationally close, there are events A and B of probability 1 − such that the distributions of X|A and Y |B are “computationally ” identical. Using only the standard min-max theorem and some basic facts about convex approximations in Lp spaces, we provide alternative modular proofs and some generalizations of these results in the nonuniform set-ting, achieving best possible bounds for (a) and slightly improving the known bounds for (b). As an interesting application, we show a strength-ening of the transformation between two most popular pseudoentropy variants: HILL and Metric Entropy, and apply it to show how to ex-tract pseudorandomness from a sequence of metric-entropy sources of poor quality. In this case we significantly improve security parameters, comparing to the best known techniques. 1