2
$\begingroup$

My goal is to create a random $k$ bit string. My question can be divided in two parts.

  • If a $n$ bit string $s$ is computationally indistinguishable from a random $n$ bit string, can we say that the string $s$ has $n$ bit min entropy?
  • But for some reason I can't use the string $s$ directly, I need to convert it to another $n$ bit string $s'$. During conversion something bad happens. The probability of each bit being $0$ or $1$ is not $1/2$ anymore. It is $1/2+e$. Hence the min entropy of the bit string $n$ changes. Let the min-entropy of $s'$ be $l>k$. As hash functions are good randomness extractor, if I apply a hash function $H$ on the string $s'$ that produces $k$ bits, can I say the output of the hash function is a $k$ bit random string?

Thank you for your help.

Improve this question
$\endgroup$
5
  • $\begingroup$ Sounds like homework. What have you tried so far? $\endgroup$
    – bkjvbx
    Commented Jun 15, 2017 at 12:47
  • $\begingroup$ @PaulUszak sorry I did not understand your question. $\endgroup$
    – Rick
    Commented Jun 15, 2017 at 12:57
  • $\begingroup$ Let the min-entropy be l > k. What's l? $\endgroup$
    – Paul Uszak
    Commented Jun 15, 2017 at 13:26
  • $\begingroup$ @PaulUszak the min-entropy of derived string $s'$. I have updated the question too. $\endgroup$
    – Rick
    Commented Jun 15, 2017 at 13:47
  • $\begingroup$ @bkjvbx What makes you think that it is a homework question. I can assure yu it is not. It is something where I have got stuck in my project. $\endgroup$
    – Rick
    Commented Jun 15, 2017 at 13:48

2 Answers 2

Reset to default
3
$\begingroup$

Addressing the first point, then no. Min entropy is the smallest estimate of all ways of measuring entropy. If you consider a string for cryptographic purposes, it's traditional to take the most conservative approach of entropy estimation. That's the safest way if you wear a tin foil hat.

Min entropy is:-

min H

If s (or X) is random, the individual byte probabilities will be uniformly distributed. Some Pr(x) will be higher than others. This range may actually be quite large because randomness can be quite pesky. Since min entropy takes the max Pr(x) of the range, min entropy will always be lower. In practice, it may only be 1 - 2% lower for random data. It will be much lower though for non random data like language.

As a picture, this is a histogram of 1MB of really random data:-

histrogram

We can assume that this is unbiased. Yet there is significant variation in the individual byte probabilities (the random thing). Ergo there must be a max probability. This leads to a min entropy value of 7.93 bits /byte. So for an output of 1MB, you can only count on 992000 bytes of entropy for cryptographic purposes. That's 0.9% less than you might naively expect. Incidentally the chi for this gives p = 0.15.

As to your second point, I don't think that there is any consensus on this site. Some say that a hash entropy extractor can only extract half of the original entropy. Most of this work is highly theoretical though and I am unconvinced of it's applicability to reality. On the other hand there are commercial devices that can extract more than half. I personally believe now that an extractor can extract all source entropy.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you for your answer. If we relax the condition a little more. Suppose, I don't want $k$ to be a random number. Instead, I want $k$ to be a computationally indistinguishable string from random sring. Then, can the above method assure me of that? Let's take the bias $e\approx 2^{15}$ $\endgroup$
    – Rick
    Commented Jun 16, 2017 at 9:40
  • $\begingroup$ @user2764478 2 to minus 15 I take it? $\endgroup$
    – Paul Uszak
    Commented Jun 16, 2017 at 10:07
  • $\begingroup$ @user2764478 Err, I'm not sure that a string can be computationally indistinguishable from random yet have a 2-15 bias. That's not much bias and will be very apparent in a long run. That's how they broke RC4 with similar magnitude biases. $\endgroup$
    – Paul Uszak
    Commented Jun 16, 2017 at 10:40
  • $\begingroup$ yes I meant $2^{-15}$ in each bit. That is I think a $n$ bit string will have a bias $O(2^{-15\cdot n})$ $\endgroup$
    – Rick
    Commented Jun 16, 2017 at 11:58
1
$\begingroup$

Hash functions are not always good randomness extractors. As a trivial example, I could make a k=512 hash consisting of a SHA-1 checksum padded to 512 bytes.

If you have a good randomness extractor, and your string has $l$ bits of min-entropy, then it should be able to provide you a random string of $l$ bits from that string (by definition). Truncate it to $k$ and you have your proof.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thank you for your answer. Now can you please help me with my first question, If a $n$ bit string $s$ is computationally indistinguishable from a random $n$ bit string, can we say that the string $s$ has $n$ bit min entropy? $\endgroup$
    – Rick
    Commented Jun 15, 2017 at 20:19
  • $\begingroup$ What is the probability of any one given string occurring? If the probability of every string occurring is uniform, then all of the definitions of entropy line up. $\endgroup$
    – Cort Ammon
    Commented Jun 15, 2017 at 20:37
  • $\begingroup$ Well, I can't exactly calculate the probability of a string occuring. But from the definition of indistinguishibility we know a good adversary cannot distinguish a random string and $s$ with more than negligible probability. $\endgroup$
    – Rick
    Commented Jun 15, 2017 at 20:41
  • $\begingroup$ I'm afraid that your definition of entropy extraction isn't so well defined. Many here believe that you'll only get L/2 bits out of a hash extractor. See this question that gets to the heart of this open issue : crypto.stackexchange.com/questions/41967/… $\endgroup$
    – Paul Uszak
    Commented Jun 15, 2017 at 21:05
  • $\begingroup$ Entropy is a feature of the ensembles themselves. Indistinguishably doesn't necessarily mean their entropies are identical. It has several limits applied to it. For example, it's only concerned with polynomial time algorithms to distinguish one ensemble from the other. $\endgroup$
    – Cort Ammon
    Commented Jun 15, 2017 at 21:16

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.