Do you think that RSA is safe in the next 30 years? Think again.

  • Article

There is an inherent assumption that cryptography works, and it will be 100% safe at least for near term. The longer the RSA key, for example, the safer is the algorithm. The assumption goes beyond that - the time complexity of the code-breaking algorithm increases exponentially with the length of the key. So, breaking a message encrypted with a 1024-bit RSA key in our lifetime was believed to be impossible.

Well, that's certainly not true. Ten years ago, Peter Shor published a ground-breaking article that proofs that all you need is a polynomial-time algorithm to decompose a number in prime factors, or to calculate discrete logarithms, using a relatively modest-sized quantum computer. This means that our beloved RSA encryption/decryption algorithm will not be secure anymore if someone builds such a quantum computer!

Quantum computing is a fascinating domain. And what I like about this research area is that things are happening right now. I will give two examples:
1) A new article in Science shows that you can use now a quantum computer based on ion-trap quantum computers (which are considered by many the most promising type of quantum computers). The article is based on an earlier work presented here.
2) There was a very exciting article in Nature in December 2004 demonstrating for the first time a practical implementation of quantum error correction. The experiment also used three beryllium atoms in an ion-trapped quantum computer. I can't seem to find the nature.com link since the server is down, but I found another one at NIST.

Yes, the moment we will build a large-scale quantum computer, the cryptography as we know it will go away. I'm not sure what would be the ripple effects on software industry but for sure the implications will be huge. Fortunately, quantum computing brings also several solutions to the problems that they create. There is a new type of quantum cryptography which is guaranteed to be safe. Some these devices are already being built practically, however they are very complex and expensive. Not your usual network PCI card.

So I am not sure I will feel safe when typing https:// thirty years from now...