Quantum computers inch closer?

[Ed Gerck]

David Wagner wrote:

> Ed Gerck  wrote:
> >The original poster is correct, however, in that a metric function can
> >be defined
> >and used by a QC to calculate the distance between a random state and an
> >eigenstate with some desired properties, and thereby allow the QC to define
> >when that distance is zero -- which provides the needle-in-the-haystack
> >solution,
> >even though each random state vector can be seen as a mixed state and will, with
> >higher probability, be representable by a linear combination of eigenvectors
> >with random coefficients, rather than by a single eigenvector.
>
> I must admit I can't for the life of me figure out what this paragraph
> was supposed to mean.  Maybe that's quantum for you.

In other words, even though most of the time a QC will be dealing with
mixed states (ie, states that cannot be represented by a single eigenvector),
a QC can nonetheless use a metric function (such as loosely described
by the original poster) in order to arrive at the desired needle-in-the-haystack
solution -- that might be a single eigenvector.

> But I take it we agree: The original poster's suggested "scheme" for
> cracking Feistel ciphers doesn't work, because quantum computers don't
> work like that.  Agreed?

As I commented at the time, and where I think we agree, the scheme does not
make Feistel ciphers easier to break by quantum computing.  It's not what a
"quantum algorithm". However, we need to recognize that the scheme suggested
is sound for any computer and a QC *is* a computer -- but it would be no better
for a QC than  an exhaustive search. In short, his  method had nothing "quantum"
about it.

Here, the essential point for an effective QC solution is not whether the
calculation is possible (which it is if it can be computed), but that it should
be capable of being efficiently transposed to a quantum system.  Breaking a
Feistel cipher cannot, breaking RSA PK can.

Cheers,
Ed Gerck



---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com