[Cryptography] Are there random sources?

Ron Garret ron at flownet.com
Mon Dec 26 08:46:24 EST 2016


On Dec 25, 2016, at 6:13 PM, Jerry Leichter <leichter at lrw.com> wrote:

> 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.

In the context of cryptography the answer is very straightforward: these are the wrong questions.  The right question is: how do you generate N bits of data that your adversary cannot guess with odds better than chance.

> If classical physics described our universe, the answer would be straight-forward:  No!

That is the perceived wisdom, but it is far from clear.  See, e.g.:

https://en.wikipedia.org/wiki/Three-body_problem#Sundman.27s_theorem

"Unfortunately the corresponding convergent series converges very slowly. That is, getting the value to any useful precision requires so many terms, that his solution is of little practical use. Indeed, in 1930 David Beloriszky calculated that if Sundman’s series were going to be used for astronomical observations then the computations would involve at least 
10^8000000 terms.”

(To put this number in perspective, the number of elementary particles in the universe is about 10^80.)

> 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.

True, but again that doesn’t matter.  As long as your adversary can’t carry out the required calculations (and they can’t) then that’s good enough.

> 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.

The free will theorem is a red herring.  It is a technical result in QM that has to do with certain assumptions about entanglement experiments and it has (almost) nothing do with quantum randomness.  That the outcomes of quantum measurements are truly random (i.e. they cannot be predicted even with infinite computing power and complete knowledge of the prior state of the universe) has been well established for decades.  It is completely un-controversial.  (It is also completely irrelevant to cryptography because cryptography does not need quantum randomness.)

> 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.  :-)

I’m pretty sure Conway was being glib.  Not only is it possible to understand QM, it isn’t even particularly difficult if it’s explained properly.  The problem is that QM pedagogy is hopelessly entangled (pun intended) with the Copenhagen interpretation, which is demonstrably wrong.  Copenhagen is a reasonable approximation to the truth in most cases, but it is not the truth.  If you want to go down this rabbit hole, read this:

http://www.flownet.com/ron/QM.pdf

or watch the movie version:

https://www.youtube.com/watch?v=dEaecUuEqfc

(If you want to comment on the content of these links, please don’t do it on this list because this is definitely off topic.)

> 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.

Absolutely.  But more to the point, remember that what really matters is not randomness per se, but generating data that your adversary cannot guess.  Randomness is one way to do that, probably the best way to do it, but it is absolutely *not* worth worrying about whether or not your “random” numbers are “really” random because that doesn’t matter.  All that matters is unguessability.

rg



More information about the cryptography mailing list