Paper 2016/1186

On the Complexity of Breaking Pseudoentropy

Maciej Skorski

Abstract

Pseudoentropy has found a lot of important applications to cryptography and complexity theory. In this paper we focus on the foundational problem that has not been investigated so far, namely by how much pseudoentropy (the amount seen by computationally bounded attackers) differs from its information-theoretic counterpart (seen by unbounded observers), given certain limits on attacker's computational power? We provide the following answer for HILL pseudoentropy, which exhibits a \emph{threshold behavior} around the size exponential in the entropy amount: \begin{itemize} \item If the attacker size ($s$) and advantage ($\epsilon$) satisfy $s \gg 2^k\epsilon^{-2}$ where $k$ is the claimed amount of pseudoentropy, then the pseudoentropy boils down to the information-theoretic smooth entropy \item If $s \ll 2^k\epsilon^2$ then pseudoentropy could be arbitrarily bigger than the information-theoretic smooth entropy \end{itemize} Besides answering the posted question, we show an elegant application of our result to the complexity theory, namely that it implies the classical result on the existence of functions hard to approximate (due to Pippenger). In our approach we utilize non-constructive techniques: the duality of linear programming and the probabilistic method.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Minor revision. TAMC 2017
Keywords
nonuniform attackspseudoentropysmooth entropyhardness of boolean functions
Contact author(s)
maciej skorski @ gmail com
History
2017-03-28: last of 2 revisions
2017-01-01: received
See all versions
Short URL
https://ia.cr/2016/1186
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/1186,
      author = {Maciej Skorski},
      title = {On the Complexity of Breaking Pseudoentropy},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1186},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/1186}},
      url = {https://eprint.iacr.org/2016/1186}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.