Randomness, Quantum Mechanics - and Cryptography

[Jerry Leichter]

The recent discussion of random number generators reminded me of  
something that I've been meaning to write a note about.  A couple of  
years back, John Conway and Simon Kochen proved what they nicknamed  
the Free Will Theorem.  Its informal statement is:  Given three very  
simple axioms (which seem to be fundamentally part of any physical  
theory even remotely consistent with relativity and quantum  
mechanics), "if you have free will, then electrons do, too."  This  
statement of the theorem is deliberately set up to highlight one set  
of philosophical consequences.  A different, more straightforward  
statement is:  The result of a QM measurement cannot be computed by  
any function of the entire pre-measurement state of the universe.   
Informally, the full pre-existing state of the universe does not  
determine the result of a quantum measurement.

Conway gave a series of lectures on these results that are available  
free from iTunes - look at iTunes U listings for Princeton.  *Well*  
worth listening to.  Towards the end, he makes a very interesting and  
subtle point:  We've viewed the unpredictability of QM measurements as  
matters of randomness.  People always quote Einstein's complaint that  
"God doesn't play dice with the universe".  Conway and Kocher's  
theorem, however, show that this view is very fundamentally wrong.  If  
QM results were randomly determined, then we could play the same game  
in our description of the universe that we play with randomizing  
Turing machines:  Rather than add randomness to the machine/universe,  
simply provide a deterministic machine/universe with access to a pre- 
computed "set of random coin tosses" that they call on whenever they  
need to make a "random" choice.  But if you try this approach with QM,  
then Conway and Kocher will argue that the pre-determined tape can now  
be considered part of "the complete pre-existing state of the  
universe" - and their theorem shows that that cannot be sufficient to  
predict the result of a QM measurement!

So QM's indeterminism is subtly different from randomness:  It's an  
unpredictable choice that "isn't made until the exact moment of  
measurement".  It irreducibly cannot be determined in advance.  Conway  
goes on to say that he doesn't *understand* what the distinction  
really means - but then he says he doesn't really understand what  
randomness means anyway.  If John Conway feels this way, what are we  
poor mortals to think?

If you think about the use of randomness in cryptography, what matters  
isn't really randomness - it's exactly unpredictability.  This is a  
very tough to pin down:  What's unpredictable to me may be predictable  
to you, and unpredictability "collapses" as soon as the random value  
is "known" ("measured?").  QM unpredictability as described by Conway  
seems much closer to the kind of thing you really need to get crypto  
results.

                                                         -- Jerry

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com