Victor Duchovni <[EMAIL PROTECTED]> writes: > Actually calculating the entropy for real-world functions and generators > may be intractable...
It is, in fact, generally intractable. 1) Kolmogorov-Chaitin entropy is just plain intractable -- finding the smallest possible Turing machine to generate a sequence is not computable. 2) Shannon entropy requires a precise knowledge of the probability of all symbols, and in any real world situation that, too, is impossible. Usually, the best you can do is produce (bad) bounds, and sometimes not even that. One thing that can be done, of course, is that you can prove, under certain assumptions, that it would take an intractable amount of computation to distinguish a particular PRNG from a true random sequence with greater than 50% probability. However, this is very much NOT the same as showing that the PRNG sequence contains an endless stream of entropy -- in fact, the unicity distance very clearly shows you how much "real" entropy you have, and it usually isn't much. Merely because "too much" computation would be needed does not mean that you've created entropy -- you've just made it hard for the opponent to get at your PRNG seed. "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin." -- John von Neumann Perry --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
