Paper Info
Title
Nonuniform Indistinguishability And Unpredictability Hardcore Lemmas: New Proofs And Applications To Pseudoentropy
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 epsilon-computationally close, there are events A and B of probability 1 - epsilon such that the distributions of X vertical bar A and Y vertical bar B are "computationally" identical.Using only the standard min-max 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 metric-entropy sources of poor quality. In this case we significantly improve security parameters, comparing to the best known techniques.
Year
DOI
Venue
2015
10.1007/978-3-319-17470-9_8
INFORMATION THEORETIC SECURITY (ICITS 2015)
DocType
Volume
ISSN
Journal
9063
0302-9743
Citations 
PageRank 
References 
0
0.34
11
Authors
1
Name
Order
Citations
PageRank
Maciej Skorski100.34