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