How Quantum Computers will Break Encryption
Exploring The Quantum Realm…
Having started the journey of learning about quantum computing, I decided that the next step is to try and gain an understanding of something practical. There has been a lot of discussion and debate about quantum computers having the potential to break encryption, thus rendering all internet encrypted traffic open to prying eyes, I decided to investigate.
Fair warning, this is going to get a little complicated and I will try and explain it in layman’s terms, although there will be some cryptographic analogies involved — but nothing more complicated than middle school computing physics… I hope.
Encryption
The goal of encryption is to garble data in such a way so that no one who has the data can read it unless they’re the intended recipient.
And the encryption of pretty much all private information sent over the internet relies immensely on one numerical phenomenon — as far as we can tell, it’s really really hard to take a really big number and find its factors using a normal, non-quantum computer.
All encryption over the internet is based on finding the factors of a really large non-prime number.
Unlike multiplication, which is very fast (just multiply the digits together and add them up ), finding the prime numbers that multiply together to give you an arbitrary, big, non-prime number appears to be slow — at least, the best approach we currently have that runs on a normal computer — even a very powerful one — is very slow.
FUN FACT : The largest factored RSA number was 768 bits long and it took 15,000 CPU years to decrypt (two years of real time, on many hundreds of computers).
Now, it’s not yet proven that we won’t eventually find a fast way to break encryption just with normal computers, but it’s certain that anybody with a large working quantum computer today would pose an immediate privacy and security threat to the whole internet. And that’s due to something called “Shor’s Algorithm.”
Shor’s Algorithm
Enter Shor’s algorithm, quantum computers, and the threat these pose to effectively breaking encryption. The algorithm is based on two aspects of quantum theory, ‘quantum superposition’ and ‘interference’. Peter Shor is an American professor of applied mathematics at MIT and is the inventor of this quantum algorithm from his work in the 90s in the field of quantum computation.
The kind of encryption we’re talking about garbles or “locks” messages using a large number in such a way that decrypting or “unlocking” the data requires knowing the factors of that number.
If somebody doesn’t have the factors, either they can’t decrypt the data, or they have to spend a really really long time and a huge amount of investment in computing resources finding the factors.
Shor’s algorithm is based on making a bad guess of a factor and then using the algorithm to turn that bad guess into a much better guess. Unlike quantum computers that take an astonishingly small amount of time, classical computers can also run Shor’s algorithm but take a very long time to complete.
Research Papers and Scholarly Articles :
Next Steps
We have quantum computers today, so what’s stopping us from breaking encryption right now? In a nutshell, the size of quantum memory in these computers. This is still an emerging field of research and although some quantum computers exist, they have nowhere near enough quantum memory yet to be able to make the calculations necessary to break encryption. Some estimates say that around 5096 qubits are required to break the 768-bit RSA encryption in the example given above. Currently, we’re in the 10s of qubits — a long way off.
Saying that, a lot of time and money are being poured into this field and developments are gathering pace. What is certain however, is that quantum computers WILL eventually break encryption so the role of better encryption techniques is essential in combating this and keeping our private information truly private.
Looking forward to explore more of this realm of quantum supremacy so just stay tuned …
“A classical computation is like a solo voice — one line of pure tones succeeding each other. A quantum computation is like a symphony — many lines of tones interfering with one another.”― Seth Lloyd (Programming The Universe)
