3
$\begingroup$

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$?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Does this paper (help) answer your question? cs.tau.ac.il/~amnon/Papers/RT.siam00.pdf $\endgroup$
    – user6584
    Commented Apr 23, 2023 at 11:30
  • $\begingroup$ @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? $\endgroup$
    – delete000
    Commented Sep 13, 2023 at 17:33

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.