4 ms·

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 17y 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 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 17y 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-cracked http://spectrum.ieee.org/computing/it/quantum-cryptography-c...
    • Panoramix 17y ago
      Actually, there are a number of possible attacks against a quantum cryptosystem; e.g. http://en.wikipedia.org/wiki/Quantum_cryptography#Attacks http://en.wikipedia.org/wiki/Quantum_cryptography#Attacks
• sweis 17y 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 http://www.cc.gatech.edu/fac/cpeikert/pubs/svpcrypto.pdf Oded Regev has also done quite a bit of relevant work.