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 (
Metadata
- Available format(s)
- 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
-
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}, url = {https://eprint.iacr.org/2016/1186} }