Linux RNG paper

leichter_jerrold at emc.com leichter_jerrold at emc.com
Fri Mar 24 09:17:47 EST 2006


| Min-entropy of a probability distribution is 
| 
| -lg ( P[max] ), 
| 
| minus the base-two log of the maximum probability.  
| 
| The nice thing about min-entropy in the PRNG world is that it leads to
| a really clean relationship between how many bits of entropy we need
| to seed the PRNG, and how many bits of security (in terms of
| resistance to brute force guessing attack) we can get.
Interesting; I hadn't seen this definition before.  It's related to a
concept in traditional probability theory:  The probability of ruin.  If
I play some kind of gambling game, the usual analysis looks at "the
value of the game" strictly as my long-term expectation value.  If,
however, I have finite resources, it may be that I lose all of them
before I get to play long enough to make "long-term" a useful notion.
The current TV game show , Deal Or No Deal, is based on this:  I've yet
to see a banker's offer that equals, much less exceeds, the expected
value of the board.  However, given a player's finite resources - they
only get to play one game - the offers eventually become worth taking,
since the alternative is that you walk away with very little.  (For
that matter, insurance makes sense only because of this kind of
analysis:  The long-term expectation value of buying insurance *must*
be negative, or the insurance companies would go out of business -
but insurance can still be worth buying.)
							-- Jerry

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



More information about the cryptography mailing list