Anyone seen the 'quantum cryptanalysis' thread on sci.crypt?

-----BEGIN PGP SIGNED MESSAGE-----

Hi all,

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.

Detractors of the proposed technique say problems of noise and sensitivity
to mechanical defects are insurmountable and the technique could never work.

I was wondering if anyone here has any comment. After reading the New Scientist
article I immediately checked it out in sci.crypt and saw a few articles there
(but they weren't on the whole any more enlightening that the New Scientist
article). 

I was wondering if anyone here had any views (informed or otherwise :-)

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

ps if anyone is interested I'll try and dig out the references.


-----BEGIN PGP SIGNATURE-----
Version: 2.6

iQCVAgUBLokdq+Fu4n6w1qeBAQEnQgP+Mcu2NV89WuaZ9gJu5tluDzDDj0eZTj41
fWl/Opdw7mY+EqE+RZyWCHKXCx5ibgupZiAoliOfH9VoACd3aoAFJWb+4sMbPwKS
ycb6IhKHKhQQA7Q/wnVUGBb4G4B1ozC/2spCmLM83Nv2mcIzXfo5OlPU6ppg4oRU
pIfJzpcB7hM=
=iG+g
-----END PGP SIGNATURE-----

Sherry Mayo writes
> Detractors of the proposed technique say problems of noise and sensitivity
> to mechanical defects are insurmountable and the technique could never work.
> 
> I was wondering if anyone here has any comment. After reading the New Scientist
> 
> I was wondering if anyone here had any views (informed or otherwise :-)

My ill informed back of the envelope guestimate is that current
art is a factor of one hundred from building a proof of principle
quantum computer,  a factor of one thousand from building a
quantum computer that does something interesting, and a factor
of ten thousand from building a quantum computer that does something
that is actually useful.  Art is improving at (very roughly) a
factor of two every four years.

These estimates may well be rather optimistic, but they are
not totally ridiculous.


-- 
 ---------------------------------------------------------------------
We have the right to defend ourselves and our
property, because of the kind of animals that we              James A. Donald
are.  True law derives from this right, not from
the arbitrary power of the omnipotent state.                jamesd@netcom.com

Sherry Mayo says:
> Detractors of the proposed technique say problems of noise and sensitivity
> to mechanical defects are insurmountable and the technique could never work.

I generally speaking am leery of arguments from how well manufacturing
can be done -- especially since manufacturing might someday be done
perfectly using things like nanotechnology or even primitive
percursors like placing your atoms for your quantum dots one by one
using atomic force microscope tips (our own Tim May once proposed
constructing scanning grids of such tips for such purposes.)

On the other hand, I've still yet to hear any good commentary on what
Shor's result really is and what sort of techniques it depends on.

> ps if anyone is interested I'll try and dig out the references.

Please do

Perry

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

An important question that arises out of this -- do there exist one way
trapdoor functions that are not in BQP, the class of problems solved
in polynomial time by a quantum computer.  In other words, we need
a function where the forward direction and trapdoor inverse are in P, 
but the normal inverse is harder than factorization and discrete 
logarithm, which are in BQP.

If so, then public key cryptography can persist into the era of
the quantym computer; such P/non-BQP trapdoor inverses would be 
the next genration of public key.

Jim Hart
hart@chaos.bsu.edu

Timothy C. May writes:
 > In any case, the Shor work on a quantum factorer is interesting, but
 > is at least several decades away, in my opinion.

Operating from the assumption that this work by Shor is realistically
worthwhile, has there been any research into employing similar
techniques for encryption?  In other words, in the "world" of quantum
algorithmics, are there analogs to the hard problems currently
exploited by cryptographic systems in our current Turing machine
"world"?

| GOOD TIME FOR MOVIE - GOING ||| Mike McNally <m5@tivoli.com>       |
| TAKE TWA TO CAIRO.          ||| Tivoli Systems, Austin, TX:        |
|     (actual fortune cookie) ||| "Like A Little Bit of Semi-Heaven" |