entropy depletion

Jerrold Leichter jerrold.leichter at smarts.com
Fri Jan 7 12:15:24 EST 2005


| > 
| > .... random number generator this way. ....  Just what *is*
| > good enough?
| 
| That's a good question.  I think there is a good answer.  It
| sheds light on the distinction of pseudorandomness versus
| entropy:
| 
|   A long string produced by a good PRNG is conditionally
|   compressible in the sense that we know there exists a shorter
|   representation, but at the same time we believe it to be
|   conditionally incompressible in the sense that the adversaries
|   have no feasible way of finding a shorter representation.
| 
| In contrast,
| 
|   A long string produced by a HESG is unconditionally, absolutely
|   incompressible. There does not exist a shorter representation.
|   There cannot possibly exist a shorter representation.
You're using Kolgomorv/Chaitin complexity here, but unfortunately that's a
bit hard to apply.  *Any* string has a shorter representation - if I get to
specify the model *after* you choose the string.  K/C complexity is robust
when you talk about sets of possible strings, because playing around with
the machine can only shorten a fixed number of them.  Turning that into a
notion useful for cryptography is a bit tougher - and in any case, if you
want to get at PRNG's, you need to get at K/C complexity "with trapdoor
information":  The bit stream may *look* uncompressible, but given the
internal state, it is easily produced.

More generally:  We're talking about "stretching" entropy here.  There are
certainly theoretical results in that direction, the one usually mentioned
being the BBS bit generator, which takes k bits of entropy and gives you
p(k) (for some polynomial p) bits that are polynomially-indistinguishable
from random bits.  But you (a) need some significant work to set this up and
prove it; (b) BBS generators are slow.

A simpler approach that does work (in some sense) is:  Choose a random
starting value R, and a number k.  Compute SHA^i(R) for i from 0 to k.  Emit
these values *backwards*.  Then given the first k-1 outputs, an attacker
cannot determine the next one (under the standard hypotheses about SHA).

Unfortunately, this is useless as, say, a key generator:  If you send me
the k-1'st output for use as a key, I can't determine what your *next* key
will be - but I can trivially read your preceding k-2 sessions.

The idea that revealing just the hash of random bits "doesn't reduce the
effective entropy" sounds great, but it's naive.  It's like the argument
that if H is a good hash function, then H(K || message) is a good MAC.  Not
quite.
							-- Jerry

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



More information about the cryptography mailing list