# Inverse of leftover hash lemma

Let $$X$$ be a random variable over $$X \in {\mathcal {X}}$$ and let $$m>0$$. Let $$h: {\mathcal S} \times {\mathcal X} \rightarrow \{0,1\}^m$$ be a 2-universal hash function. If $$m \leq H_\infty (X) - 2\log\frac1\epsilon$$, then for $$S$$ uniform over $${\mathcal S}$$ we have $$\delta[(h(S,X),S),(U,S)] \leq \epsilon$$, where $$U$$ is uniform over $$\{0,1\}^m$$ and independent of $$S$$, $$H_\infty (X)$$ is the min-entropy of $$X$$, and $$\delta$$ is the total variation distance.

Are there any results describing what happens to $$\delta[(h(S,X),S),(U,S)]$$ when $$m > H_\infty (X)$$? For example, is there a known function $$f$$ such that $$\delta[(h(S,X),S),(U,S)] > f(m,X,\epsilon)$$ for $$m > H_\infty (X) + 2\log\frac1\epsilon$$?

• Does this paper (help) answer your question? cs.tau.ac.il/~amnon/Papers/RT.siam00.pdf Apr 23, 2023 at 11:30
• @user6584 You are probably referring to the results on $(k,\epsilon)$-extractors (Theorem 1.9). In this language, my question can be restated as: how badly, in terms of variation distance, will a function fail to be a $(k,\epsilon)$-extractor if $d$ is too low / $m$ is too high? Sep 13, 2023 at 17:33