The rise of quantum computing and its implications for current encryption standards are well known. But why exactly should quantum computers be especially adept at breaking encryption? The answer is a nifty bit of mathematical juggling called Shor’s algorithm. The question that still leaves is: What is it that this algorithm does that causes quantum computers to be so much better at cracking encryption? In this video, YouTuber minutephysics explains it in his traditional whiteboard cartoon style.
“Quantum computation has the potential to make it super, super easy to access encrypted data — like having a lightsaber you can use to cut through any lock or barrier, no matter how strong,” minutephysics says. “Shor’s algorithm is that lightsaber.”
According to the video, Shor’s algorithm works off the understanding that for any pair of numbers, eventually multiplying one of them by itself will reach a factor of the other number plus or minus 1. Thus you take a guess at the first number and factor it out, adding and subtracting 1, until you arrive at the second number. That would unlock the encryption (specifically RSA here, but it works on some other types) because we would then have both factors.
One reason why this seemingly simple process relies on the development of powerful quantum computers is that finding the correct power to multiply the first number by in order to find a factor of the second number (N) ± 1 takes an enormous amount of tries. The encryption key is quite a long number and thus the power could be anything from 1 to millions. But brute force is not why quantum computers work so well here.
The Superpowers of Superpositions
Briefly, thanks to quantum superpositioning, a quantum computer can calculate many answers for a single input. However, the video says that you only get one answer output at a time, with probabilities attached. To solve that issue, the calculation is set up so that wrong answers interfere with each other so that only the correct answer (or at least a good guess) is likely to be output. That calculation, which focuses on finding the right power p, is Shor’s algorithm.
It’s all extremely mathemagical, involving an assist from Euclid’s algorithm, as well as a quantum Fourier transform that turns a series of superpositions of superpositions into sine waves that either constructively (add to each other) or destructively interfere — i.e., cancel each other out. The video says that, essentially, you can rig it so that only 1/p is saved, with all the other answers destructively interfered out of contention. Once you’re there, it’s a walk in the park to find p, which makes finding the two encryption factors a whole lot easier. Watch the whole video for more details, and to maybe feel a little smarter.
By the way, Peter Shor is still thriving, and if you’re interested in a deep dive on how he broke the Internet, here’s another video where the man himself explains how he figured out his eponymous masterpiece.
Source: www.darkreading.com