<p><a href="https://en.wikipedia.org/wiki/Leftover_hash_lemma" rel="nofollow noreferrer">Leftover hash lemma</a>:</p>
<blockquote>
<p>Let <span class="math-container">$X$</span> be a random variable over <span class="math-container">$X \in {\mathcal {X}}$</span> and let <span class="math-container">$m&gt;0$</span>. Let <span class="math-container">$h: {\mathcal S} \times {\mathcal X} \rightarrow \{0,1\}^m$</span> be a 2-universal hash function. If <span class="math-container">$m \leq H_\infty (X) - 2\log\frac1\epsilon$</span>, then for <span class="math-container">$S$</span> uniform over <span class="math-container">${\mathcal S}$</span> we have <span class="math-container">$\delta[(h(S,X),S),(U,S)] \leq \epsilon$</span>, where <span class="math-container">$U$</span> is uniform over <span class="math-container">$\{0,1\}^m$</span> and independent of <span class="math-container">$S$</span>, <span class="math-container">$H_\infty (X)$</span> is the <a href="https://en.wikipedia.org/wiki/Min-entropy" rel="nofollow noreferrer">min-entropy</a> of <span class="math-container">$X$</span>, and <span class="math-container">$\delta$</span> is the total variation distance.</p>
</blockquote>
<p>Are there any results describing what happens to <span class="math-container">$\delta[(h(S,X),S),(U,S)]$</span> when <span class="math-container">$m &gt; H_\infty (X)$</span>? For example, is there a known function <span class="math-container">$f$</span> such that <span class="math-container">$\delta[(h(S,X),S),(U,S)] &gt; f(m,X,\epsilon)$</span> for <span class="math-container">$m &gt; H_\infty (X) + 2\log\frac1\epsilon$</span>?</p>

CC BY-SA 4.0
2023-04-23T11:30:07.813Z
Does this paper (help) answer your question? http://www.cs.tau.ac.il/~amnon/Papers/RT.siam00.pdf
user6584
CC BY-SA 4.0
2023-09-13T17:33:57.080Z
@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?
delete000
<randomized-algorithms><randomness><hash-function><cryptography><sampling>
Inverse of leftover hash lemma
delete000
# Inverse of leftover hash lemma

(Asked by: username_0 on 2023-04-21)

[Leftover hash lemma](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/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$?

**Tags:** randomized-algorithms, randomness, hash-function, cryptography, sampling

> **Comments:**
> **username_1**: Does this paper (help) answer your question? http://www.cs.tau.ac.il/~amnon/Papers/RT.siam00.pdf  
> **username_0**: @username_1 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?  

---

## 0 answers

