---
_id: '1650'
abstract:
- lang: eng
  text: "We consider the task of deriving a key with high HILL entropy (i.e., being
    computationally indistinguishable from a key with high min-entropy) from an unpredictable
    source.\r\n\r\nPrevious to this work, the only known way to transform unpredictability
    into a key that was ϵ indistinguishable from having min-entropy was via pseudorandomness,
    for example by Goldreich-Levin (GL) hardcore bits. This approach has the inherent
    limitation that from a source with k bits of unpredictability entropy one can
    derive a key of length (and thus HILL entropy) at most k−2log(1/ϵ) bits. In many
    settings, e.g. when dealing with biometric data, such a 2log(1/ϵ) bit entropy
    loss in not an option. Our main technical contribution is a theorem that states
    that in the high entropy regime, unpredictability implies HILL entropy. Concretely,
    any variable K with |K|−d bits of unpredictability entropy has the same amount
    of so called metric entropy (against real-valued, deterministic distinguishers),
    which is known to imply the same amount of HILL entropy. The loss in circuit size
    in this argument is exponential in the entropy gap d, and thus this result only
    applies for small d (i.e., where the size of distinguishers considered is exponential
    in d).\r\n\r\nTo overcome the above restriction, we investigate if it’s possible
    to first “condense” unpredictability entropy and make the entropy gap small. We
    show that any source with k bits of unpredictability can be condensed into a source
    of length k with k−3 bits of unpredictability entropy. Our condenser simply “abuses"
    the GL construction and derives a k bit key from a source with k bits of unpredicatibily.
    The original GL theorem implies nothing when extracting that many bits, but we
    show that in this regime, GL still behaves like a “condenser" for unpredictability.
    This result comes with two caveats (1) the loss in circuit size is exponential
    in k and (2) we require that the source we start with has no HILL entropy (equivalently,
    one can efficiently check if a guess is correct). We leave it as an intriguing
    open problem to overcome these restrictions or to prove they’re inherent."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Maciej
  full_name: Skórski, Maciej
  last_name: Skórski
- first_name: Alexander
  full_name: Golovnev, Alexander
  last_name: Golovnev
- first_name: Krzysztof Z
  full_name: Pietrzak, Krzysztof Z
  id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
  last_name: Pietrzak
  orcid: 0000-0002-9139-1654
citation:
  ama: 'Skórski M, Golovnev A, Pietrzak KZ. Condensed unpredictability . In: Vol 9134.
    Springer; 2015:1046-1057. doi:<a href="https://doi.org/10.1007/978-3-662-47672-7_85">10.1007/978-3-662-47672-7_85</a>'
  apa: 'Skórski, M., Golovnev, A., &#38; Pietrzak, K. Z. (2015). Condensed unpredictability  (Vol.
    9134, pp. 1046–1057). Presented at the ICALP: Automata, Languages and Programming,
    Kyoto, Japan: Springer. <a href="https://doi.org/10.1007/978-3-662-47672-7_85">https://doi.org/10.1007/978-3-662-47672-7_85</a>'
  chicago: Skórski, Maciej, Alexander Golovnev, and Krzysztof Z Pietrzak. “Condensed
    Unpredictability ,” 9134:1046–57. Springer, 2015. <a href="https://doi.org/10.1007/978-3-662-47672-7_85">https://doi.org/10.1007/978-3-662-47672-7_85</a>.
  ieee: 'M. Skórski, A. Golovnev, and K. Z. Pietrzak, “Condensed unpredictability
    ,” presented at the ICALP: Automata, Languages and Programming, Kyoto, Japan,
    2015, vol. 9134, pp. 1046–1057.'
  ista: 'Skórski M, Golovnev A, Pietrzak KZ. 2015. Condensed unpredictability . ICALP:
    Automata, Languages and Programming, LNCS, vol. 9134, 1046–1057.'
  mla: Skórski, Maciej, et al. <i>Condensed Unpredictability </i>. Vol. 9134, Springer,
    2015, pp. 1046–57, doi:<a href="https://doi.org/10.1007/978-3-662-47672-7_85">10.1007/978-3-662-47672-7_85</a>.
  short: M. Skórski, A. Golovnev, K.Z. Pietrzak, in:, Springer, 2015, pp. 1046–1057.
conference:
  end_date: 2015-07-10
  location: Kyoto, Japan
  name: 'ICALP: Automata, Languages and Programming'
  start_date: 2015-07-06
date_created: 2018-12-11T11:53:15Z
date_published: 2015-06-20T00:00:00Z
date_updated: 2025-09-23T08:20:48Z
day: '20'
ddc:
- '000'
- '005'
department:
- _id: KrPi
doi: 10.1007/978-3-662-47672-7_85
ec_funded: 1
external_id:
  isi:
  - '000364317700085'
file:
- access_level: open_access
  checksum: e808c7eecb631336fc9f9bf2e8d4ecae
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T10:08:32Z
  date_updated: 2020-07-14T12:45:08Z
  file_id: '4693'
  file_name: IST-2016-675-v1+1_384.pdf
  file_size: 525503
  relation: main_file
file_date_updated: 2020-07-14T12:45:08Z
has_accepted_license: '1'
intvolume: '      9134'
isi: 1
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 1046 - 1057
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '259668'
  name: Provable Security for Physical Cryptography
publication_status: published
publisher: Springer
publist_id: '5500'
pubrep_id: '675'
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Condensed unpredictability '
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 9134
year: '2015'
...