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

[John Kelsey]

>From: Jack Lloyd <lloyd at randombit.net>
>Sent: Mar 22, 2006 11:30 PM
>To: cryptography at metzdowd.com
>Subject: Re: Entropy Definition (was Re: passphrases with more than 160 bits of entropy)

...

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.  

For the information theory meanings of entropy, what you're really
talking about is a property of a probability distribution.  You can do
that in terms of Shannon entropy if you want to know about bounds on
average bandwidth requirements for transmitting symbols from that
distribution.  You can look at guessing entropy if you want to know
the -lg(expected work to guess the next symbol).  You can look at
min-entropy if you want a hard bound on how many symbols you need to
sample to derive a 128-bit key that won't ever expose you to
weaknesses based on how you selected it.  And so on.  

Shannon entropy is the one most people know, but it's all wrong for
deciding how many samples you need to derive a key.  The kind of
classic illustration of this is the probability distirbution:

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

...

>Yes. Let's say the contents of tommorrow's NY Times has n bits of entropy (we
>probably can't actually calculate n, but we know it is a finite and fixed
>value). And the LA Times from the same day will also have some amount of
>entropy (call it n'). However, the entropy of the two papers combined would
>(probably) not be n+n', but some number x st min(n,n') <= x <= n+n', because
>the two papers will report on many of the same issues, carry some of the same
>AP stories, and so forth. This redundant information doesn't increase the
>entropy (reading the same AP story in a second newspaper wouldn't give you any
>new information).

Right.  If the probabilities are independent, you can add the
entropies.  That's why they're defined in log terms.  

--John


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