---
res:
bibo_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) diﬀers 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 threshold behavior
around the size exponential in the entropy amount:– If the attacker size (s) and
advantage () satisfy s (formula presented) where k is the claimed amount of pseudoentropy,
then the pseudoentropy boils down to the information-theoretic smooth entropy.
– If s (formula presented) then pseudoentropy could be arbitrarily bigger than
the information-theoretic smooth entropy. Besides answering the posted question,
we show an elegant application of our result to the complexity theory, namely
that it implies the clas-sical 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.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Maciej
foaf_name: Skórski, Maciej
foaf_surname: Skórski
foaf_workInfoHomepage: http://www.librecat.org/personId=EC09FA6A-02D0-11E9-8223-86B7C91467DD
bibo_doi: 10.1007/978-3-319-55911-7_43
bibo_volume: 10185
dct_date: 2017^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/978-331955910-0
dct_language: eng
dct_publisher: Springer@
dct_title: On the complexity of breaking pseudoentropy@
...