Sherry Mayo wrote:
Sorry if this has already been brought up (I've been skimming through c'punx lately and may have missed it) but does anyone have any comment on this thread (see title).
I first read about this in New Scientist (Sept 24th, No 1944). To summarize: Shor came up with an algorithm that could use quantum effects to rapidly factorise large primes. To build such a quantum computer requires manufacturing techniques not yet available, although two other researchers (one is called Eckart) streamlined Shor's algorithm and proposed a design for a "factorization engine" using quantum dot technology. You'd need to put a lot more quantum dots on a chip than is currently possible to build such a device, but the suggestion could be possible in a few years time. the article hinted that Hitachi were already hard at work on the problem.
Several companies are pursuing advanced lithography techniques and alternatives to conventional CMOS; the work on "quantum wells" and "quantum dots" is along these lines. I'm not holding my breath. (Rather, I *am* holding my Intel stock, as I see no significant chance that anything will displaced fairly conventional circuitry and lithography anytime soon.) In any case, the Shor work on a quantum factorer is interesting, but is at least several decades away, in my opinion. And even then it is likely to be "workable" out to some number of digits (roughly, number of digits = precision needed), by which time the conventional advances in computer power will mean we're all using 10,000-bit moduli (especially if we have just heard that NSA has just spend $32 billion to build a Shor machine able to factor 3000-bit moduli :-} ). Our own James Donald has written several long essays on Shor's results, taking a more optimistic (or pessimistic, depending on one's goals) view. Also, as Sherry noted, extensive discussion pops up in sci.crypt and the new group, sci.crypt.research. Bennett and Brassard's quantum cryptography, also discussed extensively, is closer to be realized practically. (It uses the Uncertainty Principle for polarized photons in a fiber optic cable to determine if a channle has been tapped.) A plug for the Cyphernomicon FAQ: My FAQ has several entries on quantum methods for crypto. Grep it for quantum, Shor, Brassard, Bennett, etc.
I suppose cypherpunks should keep up with the latest developments (or even possibilities), and where there's quantum cryptanalysis presumably there's also quantum cryptography :-)
Sherry
There is indeed interest in this. But bear in mind that even the most optimistic proponents admit this stuff is many years, probably many decades, away. Sort of like where the crypto that now interests us was in 1925. (And I think conventional number-theoretic crypto will stay way ahead of any machines that can ever be built. A gut feel, but based loosely on the exponential increase in complexity vs. the linear growth in technology.) --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. Cypherpunks list: majordomo@toad.com with body message of only: subscribe cypherpunks. FAQ available at ftp.netcom.com in pub/tcmay