How secure will our data be in the post-quantum era?

Anastasia Marchenkova
Quantum Bits
Published in
5 min readMay 9, 2015

--

It’s the end of modern cryptography as we know it, and we feel fine.

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…

--

--