The story broke around September 20th that Google was claiming quantum supremacy. It merited not much more than small footnotes in the popular press. It was enthusiastically received in the technology press which makes me think that it is time to start thinking about a world after RSA is dead.
In 1994 Peter Shor published his paper “Algorithms for quantum computation: discrete logarithms and factoring”. At the time quantum computers were nothing but a theoretical figment of many fertile imaginations. Fast forward to 2019, with Google claiming quantum supremacy, and we should be taking them very seriously indeed.
“Quantum supremacy” means (if verified) that Google has a real quantum computer that can solve a real world problem more efficiently than any classical (digital) computer. If their claim turns out to be true, the chances are that the cost of using this computer is astronomical and certainly beyond the means any individual or probably any corporation. But so were IMB’s machines in their early days.
What we experienced back in the early digital age was what we should expect to happen now. As soon as practical uses exist, money will pour in and improvements in the technology will be rapid, probably exponential. Given that most research (outside of secret government research) has been funded by financial institutions, it is a fairly safe bet that those same institutions will be racing one another to translate quantum supremacy into financial market supremacy.
So why should we be concerned about this and what does it have to do with encryption? Well, Shor’s algorithm factorises numbers. If you can factorise a product of two large prime numbers in reasonable time, you break RSA and related cyphers, which account for pretty much all of the messages in the world now. And that is exactly what Shor’s algorithm promises.
We are a few years away from a time with a powerful enough quantum computer to break current RSA keys but if quantum supremacy is proved, you can be sure that time is closer than you think. And don’t forget, your messages are probably being stored by several government agencies the world over right now. Your messages are definitely secure now, but if you care about your messages being secure 5 or 10 years from now you should be asking why we aren’t using quantum safe cryptography now.