random

[Darren New]

Alex Martelli wrote:
> 
> "Mark 'Kamikaze' Hughes" <kamikaze at kuoi.asui.uidaho.edu> wrote in message
> news:slrn9hi99k.9ns.kamikaze at kuoi.asui.uidaho.edu...
>     ...
> >   A true random number generator is not one that requires an infinite
> > amount of information to predict, it is one that is *impossible* to
> > predict, regardless of how much information you have.
> 
> <shrug> OK, that's your definition.  Do you agree with Ullrich's
> apparent thesis that _any_ physical system is such a 'true random
> number generator' because of inevitable quantum effect _no
> matter at how macroscopic a level you look at the system_,

No. Systems that are designed to not show quantum effects (like
computers) are very easy to predict reliably. Not 100%, but
99.99999999999999999% or better. Hence, they're not random, because I
can almost always predict them. But since they're quantum systems, I
cannot 100% predict them.

> and secondarily that 'true randomness' (he calls it 'perfect')
> only exists at all _because_ of quantum effects?

I think it's more that 'true randomness' doesn't exist where there isn't
any physical system involved, such as in a mathematical formalism.

> If this is NOT what you mean, then let's find out what you
> DO mean by "impossible to predict" if it's not some quantum
> sophistry:-).

"Impossible to predict with >50% likelyhood of success."

Of course, it's *always* possible to predict what number will come up on
the dice. Just go to Vegas and watch people do it. The trick is being
*correct* with better-than-expected probability.

> Are all of these a "true random
> number generator" by your definition?

Generally.

>  Couldn't I for example
> in principle predict the outcome of dice being rolled, if I did
> have a sufficient but finite amount of information on the
> state of the dice? 

No.

> There only seem to be macroscopic phenomena
> involved 

This is incorrect. The dice bounce because of interactions between atoms
in the dice and atoms in the table. Ensuring that there is sufficient
such interactions is one of the rules of craps.

> > > Meanwhile I still see nothing 'sinful' in dealing with
> > > randomness finitely,
> >
> >   It's simple.  If you have a pseudo-random number generator, you will
> > eventually repeat,
> 
> If the 'eventually repeat' is sufficiently longer than the
> time to the expected heat death of the Universe, for
> example, is that a real problem?  Any more than it is

Let's put it this way. I'll run a Keno game with ping-pong balls
bouncing arund in a cage. I'll let anyone who wants to examine the balls
as much as they like, and the machine, and etc.

You run a Keno game using a computer to generate the random numbers. You
let anyone who wants examine your programs, OS, hardware, etc. 

Lets see who makes money and who loses money.

(This actually happened in Atlantic City. Someone one several times over
the course of 6 months, because the computer was starting over with the
same sequence of games every time the casino lost power. I think it's
safe to say this isn't random.)

> before it's any use.  Now, what difference does it make whether
> the bits in the pad are generated by using a system that is
> _impossible_ to predict (sufficient amplification of some
> tastefully chosen quantum effect, say -- assuming quantum
> effects ARE indeed intrinsically unpredictable), or one that
> WOULD be possible to predict EXCEPT for the little detail of
> needing *a sufficiently large amount* of information that is
> just not there?  N coin-flips, for example, to generate N bits.

Needing a sufficiently large amount of information that isn't availble
and never has been and never will be means that it's impossible to
predict, yes?
 
> Each flip is presumably predictable (with a probability as
> close to 1 as one wishes) GIVEN information about initial
> coin state and forces applied,

Well, no. This is the assumption you keep making that's incorrect. This
is exactly 100% precisely what quantum physics says. The flip is *not*
predictable with a probability as close to 1 no matter how much
informaiton about the initial coin state and forces applied. Really. It
just isn't.

Besides, this gets into another problem. The one-time pad is *not*
random. If it were random, you wouldn't be able to decrypt the message.
The one time pad was *randomly generated*, but once it's generated, it's
not random any more. I can with 100% accuracy predict exactly what
sequence of bits I generated for the one time pad.

> Now what, if anything, is different about using some program
> implementing a given algorithm to generate the pad?  What
> else except the amount of bits of information that are needed
> for the prediction?  I.e., the amount of randomness.

The fact that one can look at the output of your algorithm (if it's not
a very good one) and deduce what the algorithm is and all the starting
points. 

If, for example, your algorithm is to feed a counter into DES with a
fixed key and use the output as your random number sequence, then I have
only 2^56 different keys to try to figure out what key you used. The
reason? Because I know when I got it right.

If I can tell when I have the *right* answer, then the sequence isn't
random.

> If high
> enough, if a large-enough number M of bits of information is
> needed to predict the N bits on the pad, then the system is
> as secure as with N coin-flips.

This is incorrect. If you need (say) 256 bits of key material, I'll have
a difficult time brute-forcing the key before the universe dies.
However, if I *do* happen to *guess* the right key, I'll know it. *Even*
if you generated 256 coin flips, and then used them with an algorithm to
generate 100K of pseudo-random data with an algorithm I know. Now, the
likelyhood of me guessing is very tiny, but it's not zero. The
likelyhood of me guessing your OTP is very tiny, but it's not zero. The
difference is that if I do guess you're OTP, I won't know that I did.

-- 
Darren New / Senior MTS & Free Radical / Invisible Worlds Inc.
       San Diego, CA, USA (PST).  Cryptokeys on demand.
     This is top-quality raw fish, the Rolls-Rice of Sushi!