---
res:
bibo_abstract:
- 'The famous Leftover Hash Lemma (LHL) states that (almost) universal hash functions
are good randomness extractors. Despite its numerous applications, LHL-based extractors
suffer from the following two limitations: - Large Entropy Loss: to extract v
bits from distribution X of min-entropy m which are ε-close to uniform, one must
set v ≤ m - 2log(1/ε), meaning that the entropy loss L = def m - v ≥ 2 log(1/ε).
For many applications, such entropy loss is too large. - Large Seed Length: the
seed length n of (almost) universal hash function required by the LHL must be
at least n ≥ min (u - v, v + 2log(1/ε)) - O(1), where u is the length of the source,
and must grow with the number of extracted bits. Quite surprisingly, we show that
both limitations of the LHL - large entropy loss and large seed - can be overcome
(or, at least, mitigated) in various important scenarios. First, we show that
entropy loss could be reduced to L = log(1/ε) for the setting of deriving secret
keys for a wide range of cryptographic applications. Specifically, the security
of these schemes with an LHL-derived key gracefully degrades from ε to at most
ε + √ε2-L. (Notice that, unlike standard LHL, this bound is meaningful even when
one extracts more bits than the min-entropy we have!) Based on these results we
build a general computational extractor that enjoys low entropy loss and can be
used to instantiate a generic key derivation function for any cryptographic application.
Second, we study the soundness of the natural expand-then-extract approach, where
one uses a pseudorandom generator (PRG) to expand a short "input seed"
S into a longer "output seed" S′, and then use the resulting S′ as the
seed required by the LHL (or, more generally, by any randomness extractor). We
show that, in general, the expand-then-extract approach is not sound if the Decisional
Diffie-Hellman assumption is true. Despite that, we show that it is sound either:
(1) when extracting a "small" (logarithmic in the security of the PRG)
number of bits; or (2) in minicrypt. Implication (2) suggests that the expand-then-extract
approach is likely secure when used with "practical" PRGs, despite lacking
a reductionist proof of security! © 2011 International Association for Cryptologic
Research.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Boaz
foaf_name: Barak, Boaz
foaf_surname: Barak
- foaf_Person:
foaf_givenName: Yevgeniy
foaf_name: Dodis, Yevgeniy
foaf_surname: Dodis
- foaf_Person:
foaf_givenName: Hugo
foaf_name: Krawczyk, Hugo
foaf_surname: Krawczyk
- foaf_Person:
foaf_givenName: Olivier
foaf_name: Pereira, Olivier
foaf_surname: Pereira
- foaf_Person:
foaf_givenName: Krzysztof Z
foaf_name: Krzysztof Pietrzak
foaf_surname: Pietrzak
foaf_workInfoHomepage: http://www.librecat.org/personId=3E04A7AA-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-9139-1654
- foaf_Person:
foaf_givenName: François
foaf_name: Standaert, François-Xavier
foaf_surname: Standaert
- foaf_Person:
foaf_givenName: Yu
foaf_name: Yu, Yu
foaf_surname: Yu
bibo_doi: ' 10.1007/978-3-642-22792-9_1'
bibo_volume: 6841
dct_date: 2011^xs_gYear
dct_publisher: Springer@
dct_title: Leftover hash lemma revisited@
...