Tim,
I'll try to address some of the issues you raise. Quantum computing and quantum
cryptography are different but related in that they both exploit certain types of
particle behavior at the quantum level. Various atomic and subatomic paricles have
characteristics such as spin and polarization which can be measured. These spin or
polarization states are especially interesting because under the right circumstances
more than one state may be represented by the same particle, this is known as
superposition and is the crux of the Schrondinger's cat thought experiment. This
means that a quantum bit or qubit may encode more than bit of information by
exploiting the quantum superposition. Furthermore if more than one particle enter
this state together they become entangled, or linked in a way, this is the crux of the
EPR thought experiment and the idea of "spooky action at a distance" that Tim May
slyly alluded to. If you set the spin or polarization of the particles in the right !
!
!
way then when you set up an interferometer the pattern that comes out has to be the
answer to a question. Assuming you have set everything up correctly and there has
been no interference with the particles. Various types of "gates" have been designed
to do this, and since they are reversible a quantum computer in theory avoids the
thermodynamic issues of other computers. As a pratical matter one of the main
difficulties of doing this on a useful scale is the how to do error correction without
measuring because measuring will destroy the superposition and entanglement, but even
on this progress has been made. Because of the nature of qubits in theory these
computers are potentially very powerful. The application isn't really cryptoanalysis
as such, it is factoring. The Shor algorithm will allow a quantum computer of
sufficient size to factor numbers much faster than has previously be possible.
Quantum cryptography would use intangled particles to send messages which cann!
!
!
ot be read by anyone but the intended recipient, the issue here is that to eavesdrop
someone has to measure the quantum state which will destroy the superposition and the
entanglement and it will be obvious to the recipient that this has happened.
Furthermore without information from the sender about quantum states it cannot be
deciphered. All this is very interesting, the only issue is actually building one
which is easier said than done. Currently only a few particles can be set up and
control in the needed manner and many times more would be needed to perform real
calculations. So far these efforts have involved things like ion traps and magnetic
resonance equipment to set particles spinning and them measure them. The IBM
experiment used MNR equipment to control 5 flourine atoms which perform what on a
normal computer would be a multiple set calculation in one step. This is less
impressive than it sounds as a kid with a crayon could do the calculation and without
the !
!
!
room full of equipment needed to do on a quantum basis.
The one more recent development that might lead to a quantum computer that could do
something useful is Bruce Kane proposal for a silicon based spin computer which would
embed phosporous nuclei in a repetitive array and use their spin states as the qubits.
All this is discussed at www.qubit.org you might also try www.quantum.at One last
thing Deutsch's interest is not so much the actual quantum computer and what it would
calculate but that it might provide evidence for his "many worlds" outlook. He
beleives we live in one universe among an infinitude of universes and that each of the
states in a superpositon represents a different universe which are at that point
interacting.
Jim
--
On Tue, 15 Aug 2000 16:41:12
Timothy Brown wrote:
>
>> There's some confusion or disconnect between the _title_ of the
>> thread and the _content_ of the thread. "Quantum cryptography" of the
>> Brassard/et. al. sort, which reveals that intercepts have occurred,
>> is not the same thing as a "quantum computer," of the
>> Grover/Deutsch/et. al. sort.
>
>My reason for bringing up the thread was the Altavista article. Chuang
>reportedly states in an interview [ref. to in the article] that he found the
>period of a function in one step. I'm not well-versed in cryptography, but
>this highlights the fact that cryptanalysis will become sufficiently easier
>with the advent of quantum computers. The fact that IBM has developed a
>working model leads me to believe the technology may be available much more
>recently than previously thought. Since cryptanalysis will become easier,
>my question was simply put - will cryptography become sufficiently more
>secure using principles inherent in quantum computing? I'm aware of most of
>the basics of what makes a cryptosystem secure, but how do the principles in
>quantum computing make cryptosystems more secure, and are there any
>references to secure cryptosystems theorized with the advent of quantum
>computing blah blah blah, you get the idea.
>
>Honig states:
>
>> Simple. Use bigger keys. Bigger by the work-factor that quantum
>> computation gives you (see Grover's algorithm). E.g., a 512-bit symmetric
>> block cipher should be good for a few more years, quantum computers
>> or not. 3-AES anyone?
>
>dmolnar says:
>
>> public-key crypto : factoring and discrete log become "easy."
>> Thus RSA and Diffie-Hellman and all their cousins become broken.
>> Search begins in earnest for alternative one-way functions and public-key
>> cryptosystems. As far as I know, NTRU doesn't have a quantum algorithm
>> for breaking it; there may be others.
>>
>> Actually, this brings up a point - what weird public-key cryptosystems
>> not based on factoring or discrete log are there? I can think of
>> Arithmetica's system and NTRU off the top of my head, but not much more.
>
>This is essentially the crux of my question. Does quantum computing not
>make factoring very easy, at least in terms of available power? If I create
>a cryptosystem using quantum computing and you cryptanalyze it using quantum
>computing, is the make/break ratio equal? I assume so, so my question
>becomes, are there different ways to make a cryptosystem using quantum
>computing theory... and are there any good books or research material or web
>pointers available on the subject (outside of the brief discussion at
>www.qubit.org)?
>
>Thanks, folks -
>
>T
>
>
Send your favorite photo with any online greeting!
http://www.whowhere.lycos.com/redirects/americangreetings.rdct
