Entropy Definition (was Re: passphrases with more than 160 bits of entropy)

[John Denker]

John Kelsey wrote:

> As an aside, this whole discussion is confused by the fact that there
> are a bunch of different domains in which entropy is defined.  The
> algorithmic information theory sense of entropy (how long is the
> shortest program that produces this sequence?) is miles away from the
> information theory sense of entropy, and even that has a bunch of
> different flavors.  

I would have said almost the opposite.  The great power and beauty
of the entropy idea is that it has the *same* meaning across many
domains.  Entropy is defined in terms of probability, period.  Any
other definition is either
   a) exactly equivalent,
   b) an approximation, valid under this-or-that restrictive conditions, or
   c) wrong.

With some slight fiddling to get the normalization right, 1/2
raised to the power of (program length) defines a probability
measure.  This may not be "the" probability you want, but it
is "a" probability, and you can plug it into the entropy definition.

The problem is almost never understanding the definition of
entropy.  The problem is almost always ascertaining what is
the correct probability measure applicable to the problem
at hand.

Don't get me started about "universal" probability measures.
That has an arcane narrow technical meaning that is verrry widely
misunderstood.


> 0 occurs with probability 1/2
> each other number from 1 to 2^{160}+1 happens with probability
> 2^{-161}.
> 
> The Shannon entropy on this distribution is 81.5 bits. 

I think it is very close to 81 bits, not 81.5, but that is a minor
point that doesn't change the conclusion:

>  But if you
> tried to sample it once to generate an 80-bit Skipjack key, half the
> time, I'd guess your key on my first try.  

Yeah, but if I sample it N times, with high probability I can generate
a large number of very good keys.  This problem is faced by (and solved
by) any decent TRNG.


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com