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 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:
\begin{enumerate}[(a)]
\item The hardcore lemma for unpredictability, due to Impagliazzo (FOCS '95). It states that if a boolean function
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint. MINOR revision.
- Keywords
- Hardcore LemmasPseudoentropy
- Contact author(s)
- maciej skorski @ gmail com
- History
- 2015-02-24: 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}, url = {https://eprint.iacr.org/2015/117} }