I wrote: >>
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.
Jerrold Leichter wrote:
You're using Kolgomorv/Chaitin complexity here, but unfortunately that's a
bit hard to apply.
It works for me. It is in principle hard to apply exactly, but in practice it's easy to apply to a good-enough approximation.
In particular, for any given PRNG I can readily exhibit the compressed representation of its output, namely the PRNG itself along with the initial internal state.
> 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.
Yes, I stand corrected. I sloppily wrote "string" when I should have written "strings". Specifically, the set of strings collectively cannot be compressed at all. As for each string individually, it is not compressible either, except possibly for trivially rare cases and/or trivial amounts of compression.
*Any* string has a shorter representation - if I get to specify the model *after* you choose the string.
Yes, for one particular string, or very small set of strings. You get to choose the model, but you only get to choose once. So you can only compress a trivially small subset of all the output strings, unless we're talking about a trivial degree of compression. In any case, you derive no cryptanalytic advantage from compression based on an ad-hoc model, so you might as well not bother, and just stick to some convenient standard model.
> 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.
Isn't that what I said, as quoted above? I said it was conditionally compressible. It should go without saying that knowing the trapdoor information, i.e. the internal state, is the sufficient condition for feasible compressibility.
More generally: We're talking about "stretching" entropy here.
Well, I can agree that that's what we _should_ be talking about. I like to speak of an SRNG (stretched random number generator) as having a nonzero lower bound on the entropy density of the output, as opposed to a traditional PRNG where the entropy density is asymptotically zero.
> 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.
When I wanted to stretch entropy, I implemented the Yarrow
approach, i.e. encrypted counter plus systematic reseeding:
http://www.av8n.com/turbid/paper/turbid.htm#sec-srandom
It's not slow, and appears incomparably stronger than the
SHA^i example. Indeed it does not have any serious weaknesses that I know of. If anybody knows of any flaws, please explain!
The idea that revealing just the hash of random bits "doesn't reduce the
effective entropy" sounds great, but it's naive.
We agree it's naive. Indeed it's just wrong, as I've said N times over the last couple of days. And please let's not talk about "effective" entropy. I have no idea what "ineffective" entropy is supposed to be, and I can't imagine any way that makes sense to distinguish "effective" entropy from plain old entropy.
--------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
