On the complexity of breaking pseudoentropy

M. Skórski, in:, G. Jäger, S. Steila (Eds.), Springer, 2017, pp. 600–613.


Conference Paper | Published | English
Editor
;
Department
Series Title
LNCS
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.
Publishing Year
Date Published
2017-04-01
Volume
10185
Page
600 - 613
Conference
TAMC: Theory and Applications of Models of Computation
Conference Location
Bern, Switzerland
Conference Date
2017-04-20 – 2017-04-22
IST-REx-ID

Cite this

Skórski M. On the complexity of breaking pseudoentropy. In: Jäger G, Steila S, eds. Vol 10185. Springer; 2017:600-613. doi:10.1007/978-3-319-55911-7_43
Skórski, M. (2017). On the complexity of breaking pseudoentropy. In G. Jäger & S. Steila (Eds.) (Vol. 10185, pp. 600–613). Presented at the TAMC: Theory and Applications of Models of Computation, Bern, Switzerland: Springer. https://doi.org/10.1007/978-3-319-55911-7_43
Skórski, Maciej. “On the Complexity of Breaking Pseudoentropy.” edited by Gerhard Jäger and Silvia Steila, 10185:600–613. Springer, 2017. https://doi.org/10.1007/978-3-319-55911-7_43.
M. Skórski, “On the complexity of breaking pseudoentropy,” presented at the TAMC: Theory and Applications of Models of Computation, Bern, Switzerland, 2017, vol. 10185, pp. 600–613.
Skórski M. 2017. On the complexity of breaking pseudoentropy. TAMC: Theory and Applications of Models of Computation, LNCS, vol. 10185. 600–613.
Skórski, Maciej. On the Complexity of Breaking Pseudoentropy. Edited by Gerhard Jäger and Silvia Steila, vol. 10185, Springer, 2017, pp. 600–13, doi:10.1007/978-3-319-55911-7_43.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar
ISBN Search