Join Log in
Score:2
GhostMaggiore avatar Crypto

Extractor and Min-Entropy proof

ph flag
GhostMaggiore

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

72
0 + 0
kodlu avatar
sa flag
kodlu
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?
0
Reply
GhostMaggiore avatar
ph flag
GhostMaggiore
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.
0
Reply
Paul Uszak avatar
cn flag
Paul Uszak
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.
0
Reply
GhostMaggiore avatar
ph flag
GhostMaggiore
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.
0
Reply
Maarten Bodewes avatar
in flag
Maarten Bodewes
**Ask the prof**! This seems to be genuine question. Any prof worth their salt should try and teach well-willing students.
3
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.