From: tcmay@netcom.com (Timothy C. May)
Date: Wed, 28 Sep 94 10:59:12 PDT
To: scmayo@rschp2.anu.edu.au (Sherry Mayo)
Subject: Re: Anyone seen the 'quantum cryptanalysis' thread on sci.crypt?
In-Reply-To: <9409280734.AA12090@toad.com>
Message-ID: <199409281757.KAA13989@netcom8.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


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