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 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.For example, let’s check on the security of Medium, where this post was originally published.
Medium uses ECDHE (Elliptic curve Diffie–Hellman) signed using RSA keys. Both quantum breakable. Other quantum breakable algorithms include DSA (Digital Signature Algorithm) schemes and the Diffie-Hellman key-exchange protocol.What about AES? As it turns out, symmetric cryptography, like AES, is only weakened by a quantum computer. You would need to double the bit size to have the same protection against a quantum computer. As you see, Medium used AES-128 to encrypt. Great! Except a quantum computer would make AES-128 actually only have the protection of AES-64, which would take a couple weeks to crack, instead of a few billion years.
Now, it may not matter to you if someone breaks into your Medium account. But a bank should probably care if someone got access to their system and started siphoning funds.Do you bank online? Do you use a username and password on any site? Both symmetric and asymmetric algorithms are at the core of modern systems like SSL, VPN, HTTPS to communicate securely over the internet. The information you send when you log in to your account or buy something online is most likely protected and authenticated by a quantum breakable or quantum weakened algorithm.
It is not enough to double bit size for asymmetric cryptography, and the symmetric cryptography is seriously threatened — with just brute force.
Quantum Computing is Non-Turing
A good portion of current cryptosystems is definitely vulnerable at some level to quantum computers. For data that is sensitive, does this mean that it is already too late? Credit card numbers encrypted with RSA will expire, but what about your medical history, or your social security number?Snowden’s files show that as of 2013, the NSA has not succeeded in building a quantum computer. Do you think they will announce if they succeed first? What if another country, like China, succeeds? By the way, breaking elliptic curve cryptography requires less qubits than to break RSA.
We need to establish quantum-safe protocols, move to safer algorithms for more sensitive and longer lasting information, and bring together the physics and security community for talks about the future of computing in a post-quantum era.
The move to post-quantum cryptography, which is already technologically feasible, and even better, practical, provides the first layer of defense. Lattice-based cryptography, and Supersingular Isogeny Diffie–Hellman Key Exchange are natural candidates to replace current quantum breakable cryptographic methods, due to their efficiency and basis in methods currently used today, but there are many algorithms with promise, as well as growing interest, support, and funding from government and academia on post-quantum cryptography.
It would be a shame if quantum computing wouldn’t be allowed to flourish; the positives of quantum algorithms applied to core physics, medicine, machine learning, and more outweigh the negatives of breaking current modern cryptography. We don’t and can’t know the technological leaps that will happen once large-scale qubit systems exist and can be properly tested, but we can guard against the current knowledge and look into the future, knowing that quantum computing is coming fast. Our data and our lives exist on the internet, and there’s no going back.
-p-1600.png)
