---
res:
  bibo_abstract:
  - "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.@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Maciej
      foaf_name: Skórski, Maciej
      foaf_surname: Skórski
  - foaf_Person:
      foaf_givenName: Alexander
      foaf_name: Golovnev, Alexander
      foaf_surname: Golovnev
  - foaf_Person:
      foaf_givenName: Krzysztof Z
      foaf_name: Pietrzak, Krzysztof Z
      foaf_surname: Pietrzak
      foaf_workInfoHomepage: http://www.librecat.org/personId=3E04A7AA-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0002-9139-1654
  bibo_doi: 10.1007/978-3-662-47672-7_85
  bibo_volume: 9134
  dct_date: 2015^xs_gYear
  dct_identifier:
  - UT:000364317700085
  dct_language: eng
  dct_publisher: Springer@
  dct_title: Condensed unpredictability @
...