[Cryptography] The ultimate random source

John Denker jsd at av8n.com
Fri Feb 14 20:33:44 EST 2014


On 02/14/2014 03:22 PM, Sampo Syreeni wrote:
> 
> I wonder... Might there be a random process which actually *can* be
> verified? 

Answer: Yes.

> Say, something relying on quantum entanglement and the
> uncertainty principle?

Entanglement has got nothing to do with it.

Quantum mechanics is relevant only in the smart-aleck sense 
that quantum mechanics explains and /includes/ all of 
classical physics as a special case.

   BTW FWIW the reverse is not true:  Classical physics
   cannot explain QM.

OTOH if you meant to exclude classical physics, that's a
mistake.  The second law of thermodynamics is just as well
"verified" as the "uncertainty principle" ... and in fact,
if you look at them closely enough, you find that the are
essentially synonymous.  There is no such thing as purely
zero-point fluctuations as distinct from purely thermal
fluctuations;  those are just two asymptotes on the *same*
graph:
  http://www.av8n.com/physics/oscillator.htm

Bottom line:  Thermal noise is a random process.  The
principle of the thing is verrrry well verified.  Everything
after that is implementation details.  The details are
important, but they don't change the principle of the thing.

Quantum noise is no better than thermal noise.  It is no 
worse except insofar as the details are harder to manage, 
which they generally are.

==========================

Regarding the M&M RNG specifically:

Firstly:  I assume everybody knows that the Subject: line
is a joke.  This is not the ultimate random source.  It's 
a facetious random source.  There exist other sources that 
are cheaper, faster, and in every way better.

Secondly: The analyses that have been offered so far are in
the facetious and/or amateur category.  They are the sort of
analysis that even if done carefully would only result in
an estimated /upper bound/ on the entropy.

  Security depends on a reliable lower bound, and I haven't
  seen anybody even try to calculate that for this system.

Thirdly:  Fussing over "sensor noise" misses the point of
this example.  The M&M source is designed so that it does 
not depend on sensor noise.  In this sense, it belongs in 
the same general category as pointing a camera at a powerball 
machine, or pointing a camera at a coin toss.  For better 
or worse, the fundamental random source process is several 
stages upstream of the camera.

The problem with sensor noise is that a lot of people seem
unwilling to do the work required to calibrate (i.e. "validate")
the sensor in enough detail to obtain a reliable lower bound
on the entropy.

The M&M process gets around that problem, but AFAICT it
throws the baby out with the bathwater, insofar as it 
would be /at least/ as hard to validate this source,
i.e. to calculate a reliable lower bound on the entropy.
I'm not saying it couldn't be done ... but I am saying it 
would be a lot of work.

Fourthly:  It is a mistake to think that the fundamental
process here has anything to do with capturing the randomness
provided by the human being who shakes the beaker of M&Ms.
If this source works at all, it works on another principle.
You could use a non-human robot to stir the M&Ms.

There is such a thing as /chaotic dynamics/.  In a chaotic
system, the state at some large time T is exponentially
sensitive to initial conditions.  In other words, it is a
noise amplifier.  The so-called "butterfly effect" is a
familiar metonym.

If the M&M source works at all, to validate it you would
need to demonstrate that there is chaotic dynamics at work.
I reckon it is, but you would need to demonstrate it and
quantify it, not just assume it.  You would need to show 
that it outruns various segregation processes.  There is 
serous, non-facetious research that is relevant, in the 
materials literature:
   Williams, J. C. 
   "The Segregation of Particulate Materials. A Review"
   Powder Technology 15, 245-251 (1976).
and in the physics literature:
   Rosato, A., Strandburg, K. J., Prinz, F. & Swendsen, R. H.
   "Why the Brazil Nuts are On Top: Size Segregation of Particulate Matter by Shaking"
   Physical Review Letters 58, 1038-1040 (1987).
   http://prl.aps.org/abstract/PRL/v58/i10/p1038_1

By way of cautionary tale, pointing a camera at an ordinary
coin toss would be a terrible idea.  If you were to assume
the coin exhibits chaotic dynamics, you would be in for a
nasty surprise.
   Persi Diaconis, Susan Holmes, and Richard Montgomery
   "Dynamical Bias in the Coin Toss"
   SIAM Review, 49(2):211-235 (2007)
   http://statweb.stanford.edu/~cgates/PERSI/papers/dyn_coin_07.pdf

I suspect M&Ms are better, but you would need to demonstrate
that, not just assume it.

An ounce of calibration is worth more than a ton of wishful
thinking.


More information about the cryptography mailing list