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" |
participants (6)
-
jamesd@netcom.com -
Jim Hart -
m5@vail.tivoli.com -
Perry E. Metzger -
Sherry Mayo -
tcmay@netcom.com