Re: Crypto and new computing strategies

[tcmay@netcom.com (Timothy C. May)]

Jim Choate writes:

> In the latest issue of Scientific American there is an article on quantum 
> computing and how the first working machine is to be built in the 
> immediate future. This raises dark portents in my mind when one considers
> the rate and the size constraints on such devices. We may be looking at a 
> technology birth which will allow brute force computation of RSA style
> algorithms and their cracking. 

No need to worry just yet.

There is no convincing evidence that "quantum computers" can calculate
in any way differently from "ordinary" computers. I'm not sure if Jim
is referring to the Bennett-Brassard talk of computers exploiting QM
principles in a new way, or the stuff on quantum-well sorts of devices
(single-electron wells). My issue of Sci Am is buried somewhere.

Devices that are built on a size scale where quantum effects are
important, such as quantum-well devices, don't use QM as a
computational mechanism per se. The devices are just real small. But
not small enough to matter for large RSA moduli--the computations
required to factor a 1000-decimal-digit number swamp even a universe
_made_ of computers!

The issue of "rate and size constraints" is a different issue for
several reasons:

1. Quantum computers (of the Bennett-Brassard sort), in their nascent
stage, are very large and cumbersome affairs....lots of light tables,
lasers, beam splitters, and interferometers. This will shrink, but not
for a while.

2. Nanotechnology and other "small" technologies may someday make
computers much more capable than the silicon-based technologies of
today. I'm not holding my breath, for lots of reasons.

And, like I said, a long-enough modulus defeats even a universe filled
with computers. It's in the math.

Can NP-hard problems be skirted with "nondeterministic" computers
(whatever _they_ are)? Not that we know of. Just speculation at this
point.

(And it hasn't been proved that factoring, let alone RSA, is NP-hard
or NP-complete or anything else.)

So I'm not worried.

--Tim May


-- 
..........................................................................
Timothy C. May         | Crypto Anarchy: encryption, digital money,  
tcmay@netcom.com       | anonymous networks, digital pseudonyms, zero
408-688-5409           | knowledge, reputations, information markets, 
W.A.S.T.E.: Aptos, CA  | black markets, collapse of governments.
Higher Power: 2^859433 | Public Key: PGP and MailSafe available.
"National borders are just speed bumps on the information superhighway."