Quantum Computing Puts Encrypted Messages at Risk

[David Honig]

At 02:40 PM 7/19/02 -0400, John S. Denker wrote:
>Amir Herzberg wrote:
>> 
>I don't even need quantum mechanics to generate
>industrial-strength random symbols.  

No one is saying you do.

>Specifically:  The "executive summary" of the 
>principles of operation of my generator is:
> -- use SHA-1, which is believed to be resistant
>    to collisions, even under chosen-input attack.
> -- use it under conditions where the adversary
>    cannot choose the input.
> -- the rest is just physics and statistics.

Sure.  There are many examples of this kind of generator,
using physical sources from video'd lava lamps to radioactive decay
(incl. semiconductor junctions, resistors, microphone, 
detuned FM radio cards).  And there are many examples of 
output-whitening hash functions; SHA-1 is reasonable in this case.


>> As an aside note, the uncertainty principle 
>> may be an example of physical
>> theory which have withstood many years, 
>> but I doubt that it was really
>> tested using crypto principles. 
>
>Where is that coming from?  I consider the uncertainty
>principle incomparably more well-established than the
>usual "crypto principles".

The thread here has split into "QM & True Randomness" and 
"what do you need to build a true RNG"...


>2) Vetting a generator by trying to "detect" patterns
>in the output is like kicking the tires on a used car
>... go ahead and do it if you want, but it is far from
>sufficient for establishing any reasonable standard of
>correctness.

You can't vet a RNG by looking at its output, which is likely
whitened anyway, but you can gain confidence by looking at its design and 
measuring the entropy in the raw-physical-source derived bitstream.
If the raw source has < 1 bits/symbol (and it will), it'd be nice if a
later stage
distilled this to near 1 bit/symbol, before whitening.  Of course, no one
outside the box will know, since you're whitening, but it yields resistance
to (albeit difficult) attacks (e.g., your hash turns out to be attackable). 
I also fail to see harm in measuring/monitoring entropy as the RNG operates.

dh




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