Shor's algorythm

en.wikipedia.org

16 points·bootload··6 comments

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?

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.

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...

Actually, there are a number of possible attacks against a quantum cryptosystem; e.g. http://en.wikipedia.org/wiki/Quantum_cryptography#Attacks

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.

Spelling!

Reply on news.ycombinator.com