If you pay much attention to tech news, you've probably been hearing about quantum computing for a while. For those of us without physics degrees, it seems like some kind of sorcery involving qubits and superpositions.
A simplified way of looking at quantum computers is that they are computers that can perform computations that are unfeasible for the classical computers that we currently rely on.
This is a problem when it comes to cybersecurity, because—at least in theory—quantum computers can solve some of the hard problems that are supposed to keep our encryption algorithms safe.
A quick cryptography primer
To back up a little, the encryption algorithms that keep our data safe are basically just a bunch of complicated mathematical operations. When we encrypt data, we process it alongside a secret key according to a large number of specific steps outlined in the algorithm. Once the data has been encrypted with a secure algorithm, it can only be decrypted with the secret key.
These algorithms are designed so that it’s relatively quick and easy to encrypt and decrypt data with the keys, but almost impossible to decrypt it without the keys. If we only share the keys with authorized parties, this gives us a way to easily access the data when we need it, while locking the bad guys out.
There are two main types of encryption:
- Symmetric-key encryption — This is an efficient type of encryption that involves using the same key to encrypt and decrypt data. Today's gold standard is the Advanced Encryption Standard, more commonly known as AES. We use it to encrypt the bulk of our communications.
- Asymmetric encryption — Also known as public-key encryption, it involves two keys, a public key and a private key. The public key is shared openly, while the private key must be kept secret. To encrypt data with an asymmetric algorithm, you must find the public key for your intended recipient, and then run the data through the asymmetric algorithm alongside their public key. When they receive the ciphertext, they can only decrypt it with their private key. Asymmetric encryption is much less efficient, so we only really use it for safely exchanging symmetric keys, and for digital signatures, which allow us to verify the integrity and authenticity of information. Common examples include RSA (Rivest-Shamir-Adleman) and various forms of elliptic-curve cryptography (ECC).
Hard math problems
The encryption algorithms that we currently consider secure aren't impossible to break. Instead, we deem them secure because it's not feasible to break them with current techniques and technology.
The security of an asymmetric algorithm like RSA relies on the difficulty of factoring large prime integers. To give a simplified explanation, if we were to tell you that the number 53,203,463 is produced by the multiplication of two prime numbers, would you be able to tell us what those primes are?
It's not easy, is it? The answer is 6857×7759.
It's relatively simple to multiply them and find the product, but it is much harder to compute it in reverse. The difficulty of performing this type of computation is what keeps RSA secure, but in practice RSA uses much larger prime numbers.
So where do quantum computers come in?
Factoring large prime numbers is really hard on classical computers. But the quirks of quantum computing open up new doors. There are algorithms that can only run on quantum computers.
One of these is called Shor's algorithm, and it can efficiently factor large prime numbers. This means that the hard problem at the heart of RSA can be solved much more efficiently. Shor's algorithm breaks RSA.
Other asymmetric algorithms face similar issues. Both elliptic-curve cryptography and the Diffie-Hellman key exchange rely on the discrete logarithm problem for their security. Unfortunately, Shor's algorithm can also solve this more efficiently, undermining their security.
Symmetric-key algorithms like AES aren't immune either. Grover's algorithm is a different quantum algorithm that can solve AES far more efficiently. However, the situation isn't as dire.
Should we freak out?
Thankfully, quantum computing’s impact on cryptography isn't another thing that you have to add to your long list of existential fears.
The reality is that quantum computers still suck, and are nowhere near being able to break our encryption through either Shor or Grover's algorithms.
Quantum computing's impact on cryptography is still a serious long-term problem, but we aren't asleep at the wheel. The National Institute of Standards and Technology (NIST) is already working to find and standardize post-quantum cryptographic algorithms for key establishment, asymmetric encryption and digital signatures.
For now, we don't have to worry too much about AES, because the 256-bit version should give us a safe enough security margin for the foreseeable future, even with the threat of Grover’s algorithm.
NIST seems to have the situation under control, so feel free to save your existential dread for something else.
