4
$\begingroup$

I'm following a course that speaks about cryptography. In this course we talked about Min-Entropy ($H_{\infty}$) and Extractor. To show that an extractor $Ext:\{0,1\}^n \rightarrow \{0,1\}^l$ that outputs an uniformly random string doesn't exist if $H_{\infty} < n$ we take the special case $\ell=1$.

But I don't well understand the proof.

In this proof we take the preimage of $b$ where $b \in \{0,1\}$ is the output that maximizes the size of the preimage. So we will have $\|Ext^{-1}(b)\| \ge 2^{n-1}$. If then we take an $X$ uniform over $Ext^{-1}(b)$ we have a constant and I think that this is in contrast with the min-entropy equal to $n-1$.

I don't understand why we should take the preimage and how we take an uniform $X$.

Improve this question
$\endgroup$
5
  • $\begingroup$ Use \{ \} in mathjax to get $\{ \}$. You cannot have $n=n-1$ either so clean up your question. The expression "we have a constant" is meaningless, a constant what? $\endgroup$ Commented Apr 7, 2022 at 17:54
  • $\begingroup$ Why i can't have n = n-1 ? This is how the professor explained the proof. The meaning of 'have a constant' is that if you take an $Ext^{-1}(b) the output is always the same, so the min-entropy is 0. However this is how I 'understood' his explaination. Sorry but I don't know how explain the proof in different way, because I don't really understand it. $\endgroup$ Commented Apr 7, 2022 at 19:52
  • $\begingroup$ Hiya Ghost & welcome :-) $n=n-1$ is equivalent to $1=2$ mathematically. Do you mean extracting from a bit sequence $ \{0,1\} ^m $ were $m<n$? Thing is when dealing with randomness extraction, you never get a "uniformly random string " as there will always be a bias, $\epsilon$ such that $Pr(X=0, X=1) = \frac{1}{2} - \epsilon$. You might need a better professor. $\endgroup$ Commented Apr 8, 2022 at 12:05
  • $\begingroup$ I don't think that the professor is not good. The fault is mine for sure. Maybe I can whatch the lesson again and try to understand better. Thanks anyway. $\endgroup$ Commented Apr 8, 2022 at 12:23
  • 3
    $\begingroup$ Ask the prof! This seems to be genuine question. Any prof worth their salt should try and teach well-willing students. $\endgroup$ Commented Apr 10, 2022 at 10:41

1 Answer 1

Reset to default
1
$\begingroup$

The professor is presenting the fact that it is impossible to have deterministic extractor. We want to define a deterministic extractor as follows:

A function $Ext:\{0,1\}^n \rightarrow \{0,1\}^{\ell}$ is a $(k, \epsilon)$ deterministic extractor if for all distributions $X$ over $\{0,1\}^n$ such that $H_{\infty}(X) \geq k$, $Ext(X)$ is $\epsilon$ close to uniform distribution over $\{0,1\}^{\ell}$.

To show the impossibility, it is enough to show that for any $(k, \epsilon)$ deterministic extractor $Ext$ (where $k \leq n-1$ and $\epsilon$ is extremely small), there exists a distribution $X$ with high min-entropy (i.e., $H_{\infty}(X) \geq k$) and $Ext(X)$ cannot be $\epsilon$ close to uniform. To construct such an $X$, we examine the preimage of $Ext$. We consider the strongest setting where the extractor $Ext$ outputs just a single bit (i.e., $\ell$ = 1) while its input distribution $X$ has very high min-entropy, i.e., $k = n-1$. In other words, it is not even possible to construct a deterministic extractor that outputs just a single bit but the input distribution has significant randomness.

Let's consider the preimages $S_b = Ext^{-1}(b)$ where $b \in \{0,1\}$. Observe that $S_b \subseteq \{0,1\}^n$ and $S_0 \cup S_1 = \{0,1\}^n$. Therefore, by an averaging argument, $|S_b| \geq 2^{n-1}$ for some $b$. Without loss of generality, let it be $S_0$. Now, consider the distribution $X$ that is uniform over $S_0$. This means that

$$Pr[x \gets X] = \begin{cases} \frac{1}{|S_0|} & x \in S_0\\ 0 & x \notin S_0\end{cases}$$

Observe that for this distribution $X$, we have $$H_{\infty}(X) = \underset{x}{min} - \log(Pr[x \gets X]) = \log(|S_0|) \geq n-1$$

Moreover, for this particular distribution $X$, we have $Ext(X) = 0$. That is, the extractor is a constant function for $X$ which is far from being uniform.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Ah, the olde " it is impossible to have deterministic extractor" adage. So how do we have commercial, hobbyist and academic TRNGs? These philosophical arguments need major clarification as I'm pretty sure (and so are ent/diehard) that I can deterministically extract bits from completely rubbish entropy sources. $\endgroup$ Commented Aug 13, 2024 at 1:20
  • $\begingroup$ @PaulUszak Although my understanding of TRNGs is limited, I was able to learn that they employ randomness extractors by reading through some related posts (see post1 and post2). This begs the question: How are TRNGs deterministic? Is the seed for the randomness extractor fixed beforehand? I hope someone can respond to the queries you and I have. $\endgroup$ Commented Aug 13, 2024 at 4:47
  • $\begingroup$ Yes the seed is fixed and public, be it the algorithm and initialisation constants for hash based extractors or the fixed bits in a Toeplitz extractor. So the impossible seems possible and profitable, yet we endlessly read papers to the contrary... $\endgroup$ Commented Aug 13, 2024 at 12:30
  • $\begingroup$ And if it begs a "question", perhaps that question might be formally asked? $\endgroup$ Commented Aug 13, 2024 at 21:00
  • $\begingroup$ While not an expert myself, my impression is that the important assumption is that the seed is independent of the source. In the counterexample given in @MaheshSR's answer, the source clearly depends on the the extractor. And it's not because there is a mathematical impossibility of a deterministic extractor that works for all sources that you can't have deterministic extractors in practice. You just aren't going to encounter a source with the problematic distribution in the real world. $\endgroup$ Commented Jan 24 at 19:44

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.