On the complexity of breaking pseudoentropy Conference Paper

Author(s): Skórski, Maciej
Title: On the complexity of breaking pseudoentropy
Title Series: LNCS
Affiliation IST Austria
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 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.
Keywords: Pseudoentropy; Hardness of boolean functions; nonuniform attacks; smooth entropy
Conference Title: TAMC: Theory and Applications of Models of Computation
Volume: 10185 LNCS
Conference Dates: April 20 - 22, 2017
Conference Location: Bern, Switzerland
Publisher: Springer  
Date Published: 2017-01-01
Start Page: 600
End Page: 613
DOI: 10.1007/978-3-319-55911-7_43
Open access: yes (repository)
IST Austria Authors
Related IST Austria Work