Randomness, Quantum Mechanics - and Cryptography
Jerry Leichter
leichter at lrw.com
Tue Sep 7 22:22:57 EDT 2010
On Sep 6, 2010, at 10:49 PM, John Denker wrote:
>> If you think about the use of randomness in cryptography, what
>> matters
>> isn't really randomness - it's exactly unpredictability.
>
> Agreed.
>
>> This is a very
>> tough to pin down: What's unpredictable to me may be predictable to
>> you,
>
> It's easy to pin down. If it's unpredictable to the attacker,
> it's unpredictable enough for all practical purposes.
I was talking about mathematical, even philosophical, underpinnings -
not "practical purposes".
In any case, even if you are concerned with practice, the statement
that something is "unpredictable to the attacker" sounds suspect.
After all, most junk cryptographic arguments claim that some algorithm
is "not reversible by the attacker". One should really expect more.
>> 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.
>
> You're working too hard. QM is interesting, but it is overkill
> for cryptography. Plain old classical thermodynamical randomness
> is plenty random enough.
But there isn't actually such a thing as classical thermodynamical
randomness! Classical physics is fully deterministic. Thermodynamics
uses a probabilistic model as a way to deal with situations where the
necessary information is just too difficult to gather. Classically,
you could in principle measure the positions and momenta of all the
atoms in a cubic liter of air, and then produce completely detailed
analyses of the future behavior of the system. There would be no
random component at all. In practice, even classically, you can't
hope to get even a fraction of the necessary information - so you
instead look at aggregate properties and, voila, thermodynamics.
There's no randomness assumption - much less an unpredictability
assumption - for the micro-level quantities. What you need is some
uniformity assumptions. If I had access to the full micro details of
that liter of air, your calculations of the macro quantities would be
completely undisturbed.
> FWIW, quantum noise is just the limiting case of thermal noise in
> the limit of high frequency and/or low temperature. There is no
> dividing line between the two, by which I mean that the full range
> of intermediate cases exists, and the same equation describes both
> asymptotes and everything in between. A graph of noise versus
> temperature for a simple circuit can be found at
> http://www.av8n.com/physics/thermo/partition-function.html#fig-qho
>
> If anybody can think of a practical attack against the randomness
> of a thermal noise source, please let us know. By "practical" I
> mean to exclude attacks that use such stupendous resources that
> it would be far easier to attack other elements of the system.
As a matter of practical engineering, I agree with you. But read what
you said over again, and distinguish it from typical snake-oil
arguments for novel crypto algorithms. The differences that make your
claims believable while those of the snake-oil salesmen are not are
subtle and illuminating. But, as the long argument on this subject
today has shown, that's still not the end of the story. Just as the
snake-oil systems typically fail because their security claims require
constraints on the attacker (which real attackers will get around),
your claims assume constraints as well. Lowering the temperature and
injecting RF. Hmm, hadn't thought of that as an attack technique....
-- Jerry
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com
More information about the cryptography
mailing list