Do you want to get started with Quantum Machine Learning? Have a look at Hands-On Quantum Machine Learning With Python.
We must prepare for it now to protect the confidentiality of data that already exists today and remains sensitive in the future." U.S. Secretary of Homeland Security, Alejandro Mayorkas, March 31, 2021, source: Homeland Security
The quantum computer's ability to crack modern cryptography puts the U.S. government uproar.
Even if today's quantum computers don't have the capacity, tomorrow's devices will inevitably. And that's a problem because what people want to keep secret today is already at risk. For example, an attacker can collect encrypted data today and crack it when the necessary quantum computing capacity becomes available.
For this reason, the Department of Homeland Security (DHS) has published a roadmap to help organizations protect their data and systems and mitigate the risks associated with the advancement of quantum computing technology.
Typically, government agencies are not known for jumping on new technologies promptly. So it should be a wake-up call to recognize the signs of the times and not miss out on understanding this new technology.
Even though I often claim that you don't need to have studied mathematics or physics, quantum computing is unfortunately not a beginner-friendly subject.
Moreover, Shor's proven algorithm for breaking factorization-based encryption that compromises asymmetric cryptography is quite advanced, even for those who know something about the subject.
So let's start with how a quantum computer might conceptually break encryption.
Suppose you have a secret message that you want to convey to your friend.
Of course, you don't want anyone else to read the message. Therefore, you need to encrypt this message before you send it. The challenge is to disguise the real message so that no one but your friend can decipher it.
The safest way would be for your friend and you to have a secret language that only the two of you understand. Think of the Egyptian hieroglyphics that no one could understand for centuries.
However, secret languages are inefficient, costly, and difficult to maintain. I already have trouble getting my English right.
So we use some standard "languages" (the cryptography algorithms) and customize them with a secret key that you must have to encrypt or decrypt the message.
While such symmetric algorithms provide a fairly high level of security, they have a logistical disadvantage. The inherent problem is the initial exchange of the keys used to encrypt and decrypt data. When these keys are passed over an unsecured connection, they are vulnerable to being intercepted by adversarial third parties. Once an unauthorized attacker gains access to a particular symmetric key, the security of all data encrypted with that key is compromised.
Public-key encryption aims to solve this problem using asymmetric algorithms. We encrypt data with a different key than we use to decrypt it in this method.
Here, one of the keys, the public key that we use to encrypt the data, is accessible to everyone. The other key, which you can use to decrypt the data, is private.
So if you encrypt your message with your friend's public key, she is the only one who can read it because she has the private key.
Public key encryption effectively circumvents the problem of key exchange. But it makes you pay dearly for this advantage. It is a deal with the devil.
These asymmetric algorithms assume that the private key cannot be derived even if one possesses the public key, although both keys are related.
It is prevalent to use huge semi-primes as the public key, which are the product of multiplying two primes. The two prime numbers then serve as the private key.
Practically, it is impossible to find the prime factors of huge numbers. Therefore, it is unproblematic if the public key is publicly known.
For example, while your smartphone can multiply two 800-digit numbers in a few seconds, it would take a supercomputer more than 2,000 years to determine the prime factors of the result.
Let's get a taste of it. First, try to find the prime factors of 22523. Of course, this is a tiny number. But there are thousands of combinations of prime numbers that might be its factors.
For comparison: Multiply 101 by 223. You will quickly be done.
Now we can understand the uproar caused by quantum computing and, in particular, Shor's algorithm. Making factorization an efficiently solvable problem shakes the cornerstones of securing our secrets.
Do you want to get started with Quantum Machine Learning? Have a look at Hands-On Quantum Machine Learning With Python.
Get the first three chapters for free here.