Leftover Hash Lemma, Revisited
Boaz Barak, Yevgeniy Dodis, Hugo Krawczyk, Olivier Pereira, Krzysztof
Pietrzak, François-Xavier Standaert, and Yu Yu
Microsoft Research New England;
New York University;
IBM Research;
Université Catholique de Louvain;
CWI Amsterdam;
Université Catholique de Louvain;and
East China Normal University
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 drawbacks:
- Large Entropy Loss: to extract $v$ bits from
distribution $X$ of min-entropy $m$> which are
$\epsilon$-close to uniform, one must set $v \le m - 2*\log(1/\epsilon)$,
meaning that the entropy loss $L = m-v \ge 2*\log(1/\epsilon)$.
- Large Seed Length: the seed length $n$
of (almost) universal hash function required by the LHL must
be at least $n \ge \min(u-v, v + 2*\log(1/\epsilon))-O(1)$, where
$u$ is the length of the source.
Quite surprisingly, we show that both limitations of the LHL — large
entropy loss and large seed — can often be overcome (or,
at least, mitigated) in various quite general scenarios.
First, we show that entropy loss could be
reduced to $L = \log (1/\epsilon)$ 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 $\epsilon$ to at most
$\epsilon+\sqrt{\epsilon 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-thenextract
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!