3
$\begingroup$

What is entropy? I do not understand it at all. One article states:

When there is an equal chance for all items to appear, we have a uniform distribution. In uniform distribution the entropy is high.

I'm confused. If entropy is high, we should consider that disorder is high too, but in a uniform distribution we don't have disorder because all items have the same chance to appear.

Is it possible for someone to explain entropy in cryptography and make this concept clear for me?

$\endgroup$
1
  • $\begingroup$ Here's an example string from a uniform distribution (over the printable ASCII characters): "5e>-1BdRPPofc?}^". Here's one from a highly non-uniform distribution: "AAAABHCAAABZABAB". I'd consider strings from the uniform distribution (both in this example and in general) to be more disordered. $\endgroup$ – Gordon Davisson Jan 23 at 17:07
6
$\begingroup$

In cryptography and information theory, Shannon entropy $H(X)$ is a characteristic of a source $X$ of discrete symbols; e.g. a characteristic of a dice. It's usually expressed per symbol produced, and with unit the bit (per symbol). It tells the expected/average number of bits necessary to encode the value of a symbol, knowing the characteristics of the source. In particular, the entropy of a known¹ deterministic source (such as a Pseudo Random Number Generator with known¹ seed) is $0$.

Assuming the symbols can take values $x_i$, are produced independently at random (that is, earlier outcomes have no influence on later ones), and each symbol $x_i$ has fixed probability $p(x_i)\ge0$ with $1=\sum p(x_i)$, then $$H(X)=\ \sum_{i\text{ with }p(x_i)\ne0}p_i\,\log_2\frac1{p(x_i)}$$

For example, a fair dice has entropy $H(X)=6\,\left(\frac16\log_26\right)=\log_26\approx2.585\ldots\,$bit/symbol. Another dice, biased towards generating 6 with probability $1/5$, and the 5 other sides having probability $4/25$, has $H(X)=\frac15\log_25\,+5\,\left(\frac4{25}\log_2\frac{25}4\right)\approx2.579\ldots\,$bit/symbol.

This illustrate the fact that for a given number $n$ of symbols, entropy per symbol is maximal at $\log_2 n\,$bit/symbol when all the symbols have the same probability, that is uniform distribution. The article mentioned in the question has it right!

Intuitive justification: when things have a high probability to be in a corner (uneven distribution), there is less disorder/entropy than when they are spread evenly all around. In the later case it takes more information to describe where each thing is.


¹ What happens if we remove known is a matter of perspective. Any PRNG implementable with finite resources has zero entropy, for we can define all it's output with a finite amount of data. On the other hand, for practical adversaries, a Cryptographically Secure PRNG that outputs integers symbols in $[0,n)$ is indistinguishable from a true RNG with entropy of $\log_2 n\,$bit per symbol and the same output domain.

$\endgroup$
4
$\begingroup$

There are many misconceptions of entropy, so you're in good company. I.e.-

“My greatest concern was what to call it. I thought of calling it ‘information’, but the word was overly used, so I decided to call it ‘uncertainty’. When I discussed it with John von Neumann, he had a better idea. Von Neumann told me, “You should call it entropy, for two reasons. In the first place your uncertainty function has been used in statistical mechanics under that name, so it already has a name. In the second place, and more important, nobody knows what entropy really is, so in a debate you will always have the advantage.”

-Claude Shannon.

And you're right in that entropy is maximal in a uniform distribution. But you're confusing 'uniform' with 'disorder'. In an IID uniform distribution, the observer cannot predict the next value with any certainty greater than $\frac{1}{n}$ for a set of $n$ possible values. Now compare that to a normal distribution, say $N(\mu, \sigma^2)$. It has a mean value of $\mu$. We can expect that the next value from a normal distribution will be more probably $\mu$ than any other. Can you see therefore how a uniform distribution is less ordered than others?

The 'order' comes from the ability to predict the next value. The minimal ability to predict the next value arises from a uniform distribution. Hence most disordered. Language eh?

$\endgroup$
1
  • 2
    $\begingroup$ Right, as a distribution it is very orderly. But its output is very disorderly. $\endgroup$ – bmm6o Jan 21 at 18:33
0
$\begingroup$

I will try and answer with a different perspective than the other 2 excellent answers, namely I want look at properties of entropy that may help bridge the intuition and the actual definition.

Shannon's entropy is a measure of information or (rather of uncertainty) of a source. With this in mind lets look at a quick example to build intuition around the uniform case.

Who wants to go skiing?: Imagine the case of 3 kids and every day you ask whether they would want to go outside in the snow and maybe do some skiing.

Kid Chance to say yes
$kid_1$ 6 days out of 7
$kid_2$ 1 day out of 7
$kid_3$ a bit moody so 50/50

Based on this example which kid's answer will have most uncertainty? In this example clearly, $kid_3$ is the most "unpredictable". However $kid_1$ and $kid_2$ seem to be the "same". i.e: they answer "similarly" if you switch "yes" and "no" ($kid_2$ is like $kid_1$ if $kid_1$ woke up on the left foot...)

Properties of a measure of information

Taking a step back from the toy example let's look at some properties we would want when we measure "information".

  1. Information should depend somehow on the number of answers: Going back to the kids.. Assume that in addition they each have 7 ski outfits and use some strategy to choose the outfit everyday, then intuitively the uncertainty around the outfits "seems" somehow greater than the uncertainty about going out or not.
  2. Information should somehow depend on probabilities: Well it does not matter that I have 7 outfits if I have a favorite one that I will always choose, there is not uncertainty here. Additionally: There should be some sort of symmetry. Looking at the "yes/no" answers of $kid_1$ and $kid_2$, we see that intuitively the uncertainty in both case is not fundamentally different.(labels don't matter)
  3. Information should somehow be additive: When we know of $kid_1$ decision to go out we've obtained some information. If we knew the decision of all kids we intuitively have $3$ times more information. However, this is problematic because there is $4$ times more possibilities in the latter case. This sort of hints towards the $\log(\cdot)$ that will appear in the entropy function.

Putting all of this together leads to the definition of the Shannon entropy:

For a chance variable $X$ taking values in $\mathcal X$ and distributed according to $P_X$, the Shannon entropy of $X$ is $$H_b(X) = \Sigma_{x \in supp(P_x)}P_X[x]*\log_b\frac{1}{P_X[x]} = \mathop{\mathbb{E}}_X[-\log_b P_X(X)] $$ Where, $supp(P_X) = \{x \in \mathcal X: P_X[x] > 0 \}$. $b$ is just the "unit" of uncertainty. $b = 2$ is the most common choice, in which case the entropy unit is a bit.

Final remark: an interesting aspect of entropy is that Shannon did not seem too bothered about the unicity of his definition. However, Aleksandr Khinchin showed that the family of functions $H_k(p_1,\ldots,p_n) = c \cdot \Sigma pi\log\frac{1}{p_i}$ are the only function that satisfy conditions(I did not state all of them!) of an information measure. [Aleksandr Y. Khinchin, “On the fundamental theorems of information theory (Russian),” Uspekhi Matematicheskikh Nauk XI, vol. 1, pp. 17–75, 1956.]

I hope this helps bridging together the intuition and the formalism.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy