Shor's algorythm

http://en.wikipedia.org/wiki/Shor%27s_algorithm

by bootload • 17 years ago

16 6 17 years ago

en.wikipedia.org

noss• 17 years ago

Spelling!

cabalamat• 17 years ago

So, are there any public key algorithms that're either (1) proven not to be crackable to quantum computers, or (2) believed not to be so?

forax• 17 years ago

I don't know the answer to your question, but if we were able to develop quantum cryptography (http://en.wikipedia.org/wiki/Quantum_cryptography), then we would no longer need to worry about public key algorithms, since Alice and Bob could agree upon a key without fear of eavesdropping, and then use an uncrackable form of encryption, such as a one time pad.

sgk284• 17 years ago

We already have functioning quantum cryptography. In theory it should be unbreakable, but there are practical problems with it (distance... it doesn't work around the world) and still relies on humans to implement the systems.

Current quantum cryptography systems have already been cracked to some extent: http://spectrum.ieee.org/computing/it/quantum-cryptography-c...

sweis• 17 years ago

There are lattice problems that we don't know how to solve efficiently in the quantum model yet. Under some plausible conjectures, certain learning with error problems would be hard in the quantum model. Quantum complexity is an open and ongoing area of research.

Chris Peikert has some recent results on the topic: http://www.cc.gatech.edu/fac/cpeikert/pubs/svpcrypto.pdf

Oded Regev has also done quite a bit of relevant work.

Shor's algorythm

Related Stories