[Cryptography] Are there random sources?

[Jerry Leichter]

Ron Garret just posted a link pointing to an overview of some recent results on producing a strong random source from two weaker random sources.  And, of course, we have many long discussions here about how to build random sources from physical hardware.

It's worth raising the question:  Is all this theory actually based on anything?  Does the physical world actually *have* any random sources?  The answer is more subtle than you might think.

If classical physics described our universe, the answer would be straight-forward:  No!  While thermodynamics talks about randomness, that randomness is not intrinsic to the physics - it's a reflection of our ignorance of detailed physical micro-states.  Yes, we describe a gas as a bunch of randomly moving particles - but classically, in principle, we could know the positions of momenta of all the individual particles, after which the deterministic classical laws would allow us (again in principle) to predict the future state of all the particles at any point in the future.  (Curiously, if you reverse time, you can construct classical non-deterministic scenarios - but let's not go there, they don't help you generate random values.)  The apparent randomness of classical physics is more a chaotic behavior than actual randomness.

But of course we know our universe is described by quantum mechanics, which is random "to the core", right?  Well ... not according to John Conway.  In a wonderful series of lectures on the fancifully named "Free Will Theorem" he and Simon Kochen proved (http://web.math.princeton.edu/facultypapers/Conway/) argues that whatever the core of QM is, it's *not* randomness.  The Free Will Theorem (listen to the lectures to see why it's been given that nickname) proves that, if anything even vaguely like quantum mechanics is a true description of the universe, then there exists an experiment whose outcome can be 0 or 1, and a complete description of the entire state of the universe before the experiment is run is insufficient to predict (other than as a 50/50 probability) what the next output will be.  It's interactions like this that are the ultimate basis of all "random" physical processes.

But ... random?  Sort of.  Conway points out that when we talk about computation using probabilistic machines, we have an alternative, completely equivalent, description:  The machine runs a deterministic machine which is given access to a special tape containing "random", initially unknown 0's and 1's, and when it needs to toss a coin, the machine simply reads the next square on the tape.  But ... the tape can be made part - a hidden part, but that doesn't matter - of the universe.  The Free Will Theorem then says that *even if you have access to that tape* - now part of the previous state of the universe - you can't determine the outcome of the experiment.

Now, I don't claim to understand just what that means about the "choices" in QM.  Then again, Conway - who's a hell of a lot brighter than I am - says he doesn't understand it either.  So I don't feel bad about it.  :-)

Whatever is going on here, it tells us is that at least our conception of probabilistic machines; and perhaps our conception of "randomness" as a whole; apparently *doesn't correspond to anything physical*.  Both are useful abstractions, like the "infinite lines with zero width" of Euclidean geometry; but they live only in their theories, not out here in the world.

So should we take away from this the message that using randomization in cryptography is a pointless exercise?  Hardly.  Even if the world *were* classical, as a *practical* matter the chaotic nature of various kinds of thermodynamic properties are quite good enough to build secure "true random number generators".  No, they aren't "really" random - in principle, someone with a God's view of the universe could predict their values - but God is not an Opponent one can hope to defend against in any case!

It does suggest, however, that attempts to *define* randomness are misdirected. The more you try to pin it down, the more you drive yourself into a realm of mathematical theorizing that doesn't correspond to anything in physical reality.

Treat random number generation as an *engineering* problem - to which a great deal of physical and engineering theory, as well as recent computer science theory - can be applied to good effect, and useful solutions exist.

                                                        -- Jerry