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 nd important applications in hardness amplication. 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 XjA and YjB 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 signicantly improve security parameters, comparing to the best known techniques.
['Maciej Skorski']
Nonuniform Indistinguishability and Unpredictability Hardcore Lemmas: New Proofs and Applications to Pseudoentropy