Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:10:57
Anonymous (nobody@replay.com)
Tue, 11 Aug 1998 06:40:27 +0200
> I'm looking for a problem in cryptogrpahy that might be solvable (or at
> least, done faster) on a quantum computer that hasn't been treated yet.
> Any suggestions?
Grover's algorithm lets you do a database search for a match to one
of n items in sqrt(n) steps rather than the n steps it would take with
a regular computer. I've read that this can theoretically be used to
do things like exhaustive DES search in 2^28 steps rather than 2^56.
According to a posting earlier today, Grover has an article in the August
7 issue of Science, but I haven't seen it yet.
It might be interesting to see how this would apply to hash collisions,
if Grover doesn't discuss it. Hash collisions are already a square root
problem. They wouldn't seem to fit into the Grover algorithm model where
you are searching a database for a match to a given value. Instead, you
want to find two matching values in a large database. Can you do better
than the square root?
Factoring and discrete logs can be broken in sub-exponential time
using Shor's algorithm. Maybe ye olde knapsacks could be looked at.
There must be a few variants around which haven't been broken yet.
What would quantum computers do to them?
There are some other public key algorithms around which nobody uses because
they tend to have large keys or are slow. Schneier has a good overview
of these, which are based on coding theory, cellular automata, and other
mathematical structures.
H
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:10:57