[4117] in cryptography@c2.net mail archive
Re: quantum cryptanalysis
daemon@ATHENA.MIT.EDU (staym@accessdata.com)
Tue Feb 2 14:30:40 1999
From: staym@accessdata.com
Date: Tue, 02 Feb 1999 11:55:48 -0700
To: cryptography@c2.net
Ulrich:
>Can you explain the halfing effect on the key length? Or may be you
>have some pointers to the literature on that?
Look up "Grover" on the Los Alamos National Labs pre-print site
http://xxx.lanl.gov/find/quant-ph
Searching a space with half the keylength is searching a space with the
sqare root of the number of keys.
Classical computers with k bits can be in 2^k different states. In a
quantum computer, each of those states is an axis in an orthogonal basis
that spans a 2^k dimensional space. The state of the quantum computer
is any unit vector in that space.
Take a classical computer and a quantum computer, each with one bit.
The classical one has to be either in the state 0 or 1. In a quantum
computer, these two states form an orthogonal basis: 0 corresponds to x,
1 to y. A quantum computer's state is represented by an angle theta in
the x-y plane. When you measure a quantum computer's bit, there is a
probability (cos theta)^2 that it will be measured in the 0 state and a
(sin theta)^2 probability it will be in the 1 state. (Think polarized
light: does the photon pass thru the polarizer or get absorbed? Depends
on the angle.)
Grover's algorithm negates one component of the vector corresponding to
the item you're trying to find (the right key, for instance). It then
does a "rotation about the average:" it averages all the components,
sets the positive ones to the average and adds the difference to the
negative one, increasing the probability that the negative one will be
measured. In order to increase that probability to 50% or better, you
have to repeat the negation-rotation process about 2^(k/2) times.
--
Mike Stay
Cryptographer / Programmer
AccessData Corp.
mailto:staym@accessdata.com
