How secure will our data be in the post-quantum era?
It’s the end of modern cryptography as we know it, and we feel fine.
By Anastasia Marchenkova
May 9 2015
Build your security for the next 50 years. If the speed of processing doubles every two years, make sure your cryptographic systems can’t be brute forced in 50 years. If you use 2048 bit RSA, it will take some quadrillion years to break it. Good enough, right?
Quantum computing is about to throw that all on its head, and soon.
The End of Moore’s Law
Quantum computers are being worked on by academics, the government, large companies including IBM, Microsoft, and Google, and small, but well-funded startups. Every piece required for a quantum computer to exist has been experimentally demonstrated. It’s now an engineering challenge, and that’s scary. It’s a race to put together the pieces (read my quantum computing primer here). Quantum computers increase processing speed on certain quantum algorithms. Then it’s open season, and we are hunting RSA, elliptic curve, and other quantum breakable cryptography.
Who is Screwed?
In public-key cryptography, RSA is one of the most widely known and used for encryption, decryption, and digital signatures, which allows us to know that our information is secure, came from the source we think it came from, and hasn’t been tampered with. RSA is based on the difficulty of factoring very large numbers. If you do not know the factorization, the problem is classically intractable. It just would take too long to go through all the possibilities on a classical processor. However, if you know the factorization, decryption is simple.
Shor’s algorithm, however, can factor an RSA public key superpolynomially faster on a quantum computer than a classical computer, making RSA remarkably useless, given how secure it has been against brute force since it was first published in 1977. A quantum computer can break the discrete log on elliptic curves, so any security protocols based on elliptic curves are vulnerable. This means classical complexity classes do not apply to quantum computers!
Any cryptosystem that is based on factorization or discrete logarithms is quantum breakable by variants of Shor’s algorithm.
You use quantum vulnerable algorithms every day for encryption, decryption, key exchange, and digital signatures as you browse.
Elliptic curve (EC) cryptography is based on discrete logarithm, and, like RSA, is being used for encryption, key exchange, signatures, and more. It’s even used in bitcoin protocols for ensuring that only the owner of the bitcoin can spend the funds.