Paper 2015/117
Nonuniform Indistinguishability and Unpredictability Hardcore Lemmas: New Proofs and Applications to Pseudoentropy
Maciej Skorski
Abstract
Hardcore lemmas are results in complexity theory which state that averagecase 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: \begin{enumerate}[(a)] \item 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. \item The hardcore lemma for indistinguishability, proved by Maurer and Tessaro (TCC'10), states that for two random variables $X$ and $Y$ which are $\epsilon$computationally close, there are events $A$ and $B$ of probability $1\epsilon$ such that the distributions of $XA$ and $YB$ are ``computationally'' identical. \end{enumerate} Using only the standard minmax theorem and some basic facts about convex approximations in $L_p$ spaces, we provide alternative modular proofs and some generalizations of these results in the nonuniform setting, achieving best possible bounds for (a) and slightly improving the known bounds for (b). As an interesting application, we show a strengthening of the transformation between two most popular pseudoentropy variants: HILL and Metric Entropy, and apply it to show how to extract pseudorandomness from a sequence of metricentropy sources of poor quality. In this case we significantly improve security parameters, comparing to the best known techniques.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. MINOR revision.
 Keywords
 Hardcore LemmasPseudoentropy
 Contact author(s)
 maciej skorski @ gmail com
 History
 20150224: received
 Short URL
 https://ia.cr/2015/117
 License

CC BY
BibTeX
@misc{cryptoeprint:2015/117, author = {Maciej Skorski}, title = {Nonuniform Indistinguishability and Unpredictability Hardcore Lemmas: New Proofs and Applications to Pseudoentropy}, howpublished = {Cryptology ePrint Archive, Paper 2015/117}, year = {2015}, note = {\url{https://eprint.iacr.org/2015/117}}, url = {https://eprint.iacr.org/2015/117} }