---
_id: '648'
abstract:
- lang: eng
  text: '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.'
alternative_title:
- LNCS
author:
- first_name: Maciej
  full_name: Skórski, Maciej
  id: EC09FA6A-02D0-11E9-8223-86B7C91467DD
  last_name: Skórski
citation:
  ama: 'Skórski M. On the complexity of breaking pseudoentropy. In: Jäger G, Steila
    S, eds. Vol 10185. Springer; 2017:600-613. doi:<a href="https://doi.org/10.1007/978-3-319-55911-7_43">10.1007/978-3-319-55911-7_43</a>'
  apa: 'Skórski, M. (2017). On the complexity of breaking pseudoentropy. In G. Jäger
    &#38; S. Steila (Eds.) (Vol. 10185, pp. 600–613). Presented at the TAMC: Theory
    and Applications of Models of Computation, Bern, Switzerland: Springer. <a href="https://doi.org/10.1007/978-3-319-55911-7_43">https://doi.org/10.1007/978-3-319-55911-7_43</a>'
  chicago: Skórski, Maciej. “On the Complexity of Breaking Pseudoentropy.” edited
    by Gerhard Jäger and Silvia Steila, 10185:600–613. Springer, 2017. <a href="https://doi.org/10.1007/978-3-319-55911-7_43">https://doi.org/10.1007/978-3-319-55911-7_43</a>.
  ieee: '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.'
  ista: 'Skórski M. 2017. On the complexity of breaking pseudoentropy. TAMC: Theory
    and Applications of Models of Computation, LNCS, vol. 10185, 600–613.'
  mla: Skórski, Maciej. <i>On the Complexity of Breaking Pseudoentropy</i>. Edited
    by Gerhard Jäger and Silvia Steila, vol. 10185, Springer, 2017, pp. 600–13, doi:<a
    href="https://doi.org/10.1007/978-3-319-55911-7_43">10.1007/978-3-319-55911-7_43</a>.
  short: M. Skórski, in:, G. Jäger, S. Steila (Eds.), Springer, 2017, pp. 600–613.
conference:
  end_date: 2017-04-22
  location: Bern, Switzerland
  name: 'TAMC: Theory and Applications of Models of Computation'
  start_date: 2017-04-20
date_created: 2018-12-11T11:47:42Z
date_published: 2017-04-01T00:00:00Z
date_updated: 2021-01-12T08:07:39Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-319-55911-7_43
editor:
- first_name: Gerhard
  full_name: Jäger, Gerhard
  last_name: Jäger
- first_name: Silvia
  full_name: Steila, Silvia
  last_name: Steila
intvolume: '     10185'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://eprint.iacr.org/2016/1186.pdf
month: '04'
oa: 1
oa_version: Submitted Version
page: 600 - 613
publication_identifier:
  isbn:
  - 978-331955910-0
publication_status: published
publisher: Springer
publist_id: '7125'
quality_controlled: '1'
scopus_import: 1
status: public
title: On the complexity of breaking pseudoentropy
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 10185
year: '2017'
...