| >
| > .... 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 [EMAIL PROTECTED]
