Quantum Computing Puts Encrypted Messages at Risk

[John S. Denker]

Amir Herzberg wrote:
> 
> 
> Can you generate truly random numbers? Cool! 
> Indeed, this is something which
> in a sense is to be expected, 
> based on the uncertainty principle. 

I don't even need quantum mechanics to generate
industrial-strength random symbols.  By that
I mean the correctness of the generator is not
dependent on the usual-but-unproven cryptologic
assumptions such as the existence of a one-way
function.  (It is somewhat dependent on much
milder assumptions about the mixing properties
of hash functions.)

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.

I consider the traditional "cryptologic" design
and validation of SHA-1 to be the _weakest_ part
of the argument!!!!

There is no reason to believe quantum noise is
"more random" than thermal noise, provided you
can control the temperature of your computer to
any reasonable degree.  And if you don't have
reasonable physical control of your computer,
all bets are off anyway.

> (cost, size, etc.). Can you provide details on this?
  cost = practically free
  size = small, if not already built-in to your computer
  http://www.monmouth.com/~jsd/turbid/

> 
> 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".
 
> I mean, couldn't it just turn out that all
> of the randomization in physics will some day turn out to be
> pseudo-random??? 

It depends on what you mean by "could".
-- It "could" be that the sun won't come up tomorrow.
-- It "could" be that there is an N log N algorithm for
   factoring N-bit numbers on your PC.

> After all, detecting the difference could be fairly
> difficult, even if and when we learn the details of 
> this supposed pseudo-random generator, 

1) The details of my generator are fully disclosed.
[I know that's not the generator that provoked this
thread.]

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.

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