[Cryptography] The ultimate random source
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
> 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*
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
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
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).
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
Persi Diaconis, Susan Holmes, and Richard Montgomery
"Dynamical Bias in the Coin Toss"
SIAM Review, 49(2):211-235 (2007)
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
More information about the cryptography