What is a Quantum Computer? Will Quantum Computers break encryption?

The security of the internet depends on encryption. It allows your device and a faraway server to send private messages to each other like your emails, your passwords, pictures of your cats, without anyone eavesdropping. Today’s encryption works pretty well, but a sophisticated quantum computer can break it, and a universal quantum computing machine is likely to emerge in the near future. “But quantum computers are already here…” Yeah yeah I know, there are quantum computers on the market, but these are not the scary ones. They use quantum annealing to solve certain optimization problems. They are too highly specialized for that. But when the general-purpose quantum computers come… Are we DOOMED??? Maybe… but we can fight quantum with quantum.

They need to be able to see the information you send them, and you need to be able to see the information they send you. No one else should be able to see any of these messages. But what’s stopping an eavesdropper from taking your messages and making copies for themselves? Not much. So what if you scramble your messages? Write them in a secret code. Okay, then how are you and the server supposed to unscramble each other’s messages? If you tell each other how to unscramble them, then the eavesdropper knows how to unscramble them too, and all of this is pointless. You and the server need to know something that no one else does.

Ok, let’s give that a go. We do this in a way that you need that special number in order to unscramble it afterward. Since this number is used to “lock” and“unlock” the data, let’s call it a “key”. This key is a secret so we can’t pass it through the internet for eavesdroppers to see. Otherwise, they would be able to unscramble our messages. But what about you and the server? Without access to each other’s key, how are you supposed to unscramble each other’s messages? Here’s how we get around this problem today. Say that you want to send the server some private information.

The server has two special keys. The public key can only be used to scramble information, no unscrambling. So it’s safe to send you that key, so you can scramble your secrets before you send them along. Even if the eavesdropper makes their own copy of the public key, it’s useless against a scrambled message. So how does the server unscramble it? It uses the private key. This key is super-secret and no one but the server should ever have it, not even you. One of them can only scramble, and the other can only unscramble messages that were scrambled by the first one. Now, calling both these numbers “keys” might be a bad analogy, since keys can typically both lock and unlock. That’s why I’m illustrating them as a padlock and a padlock key, since padlocks can only lock, and its corresponding key can only unlock that specific padlock.

And even this might be a bad analogy since locking and unlocking messages makes it seem like they’re concealed inside a box or something when it’s really more like blending it into something that looks meaningless, but in such a way that the original message can be reconstructed if you have the right number. Anyway, I’m stealing the padlock analogy from this number video, which goes into a bit more detail on how all of this works. The short version is: Because of math!

So that covers how you can send the server secret information. How does the server send you secret information? You don’t have the server’s private key, so you can’t unscramble messages that were scrambled by its public key. Instead, you generate your own unique, plain old, regular key on the spot and send the server a copy. But, before you send the key through, you use the server’s public key to scramble it. The server can then get your key by unscrambling it. Now you each of you can use this new key to both scramble and unscramble messages. Even better, the eavesdroppers can’t get this new key, since it was scrambled when you sent it to the server. Hooray, it worked! Now here’s the problem. We only share them secretly in the scrambled form if we ever need to.

But we are freely sharing the public key. It turns out that given enough time, an eavesdropper’s computer can analyze it to create an exact copy of the corresponding private key. They can essentially pick the lock. There are some shortcuts, but the math behind these keys is designed so that this would take forever anyway. Luckily, we change our locks faster than the eavesdropper can pick them. The fastest algorithms for doing this key reconstruction are just too slow to be of any practical use.

So the eavesdropper won’t find your private key unless you’re astronomically unlucky. There are theoretically faster algorithms that would do the job though. But luckily they can only run on quantum computers. Wait a minute, those are probably coming soon arent they? So, once again… Are we DOOMED??? Possibly not. Here’s the basic idea. Public-private keys must behave as one-way functions. Given a private key, it’s easy to create its corresponding public key, but given a public key, it’s hard to create its corresponding private key.

It’s a real pain to go backward, hence it is one-way. By design, at least one of these processes should be easy, otherwise, we wouldn’t be able to create these key pairs in the first place. After all, what’s the point of designing the perfect padlock with no way to open it, or the perfect padlock key with nothing for it to open? Making this process easy ensures that we can always make a useful pair. This makes it possible to let everybody encrypt messages but only some people decrypt them. You can’t decrypt messages without the private key, and it’s hard to get it, even when you have the public key.

And that is next to impossible in practice. You might be wondering why we can’t just make it impossible to go backward. It’s because there will always be at least one way to get the private key from the public key: going through every single possibility until a match is found. The best thing that we can do is make the backward process as hard as we can while keeping the forward process easy. This is how one-way functions work, and they’re the best thing we have so far. Unfortunately, the particular one-way functions that most of the internet users can be broken by quantum computers. They make it easy to get the private key, but only because there happens to be an algorithm to do it that performs very well when it’s run on a quantum computer.

To solve this problem with existing technology, new mechanisms could be built on different one-way functions, particularly ones that no one knows how to break even with quantum computers. This is good in the shorter term, but we can do better. Welcome to Quantum Cryptography. Let’s visually represent qubits with this diagram, which I like to call the Bloch circle. It’s a simplified version of something else called the Bloch sphere, but we don’t need it for this video. Now, in the Bloch circle, the direction that this arrow is pointing represents the state the qubit is in.

If we measure it in the vertical orientation, we’ll say that it’s a zero whenever the arrow points this way, and a 1 whenever the arrow points this way. If the qubit was in some non-vertical state, our measurement forces the qubit to choose one of them,…because of quantum mechanics! If it was in a horizontal state, there’s a 50-50 chance of it being measured as 0 or 1.

But if we wanted, we could have measured it horizontally. In this case, this would be a 0, this would be a 1, and these would be 50-50 chances. But what’s the point of leaving it up to chance anyway? Why not just measure vertically when it’s vertical, and horizontally when it’s horizontal? Because we can’t know if a given qubit is vertical or horizontal unless we made it ourselves. ourselves.

The only way for us to learn anything about it is to measure it, but the harsh reality is that measurement might have changed it to something else. Because of quantum mechanics! Now all of this might look really useless at first, but we can actually use these qubits to generate keys and actually detect if someone is trying to eavesdrop. Here’s how it could work. The server generates a random string of 1sand 0s. We’re gonna use these ones and zeros to make a key. The server encodes these bits into qubits by randomly choosing a vertical or horizontal orientation.

These qubits are then sent down a line that supports the transmission of qubits, and you receive them. Now, you don’t know which qubits are vertical and which are horizontal, so you randomly guess, measuring some of them vertically and others horizontally. Each time, you have a 50-50 chance of guessing right since there are only two possible orientations and you have to pick one of them. If you do guess right, that bit will be the same for you as it is for the server.

If you guess wrong, that bit has at the risk of being wrong. Now, you have your own random string of 1sand 0s, but it’s not exactly the same as the server’s string because of your wrong guesses. To throw out the useless bits, you and the server compare the orientations you used for each bit and throw out the mismatches. Even if an eavesdropper drops in to peek at the orientations used to make the measurements, they won’t know what the measurements were.

Now, you and the server each have copies of the same key that you can both use to scramble and unscramble messages. But why did the server make you guess what the orientations were? Why couldn’t the server just give them to you so you wouldn’t need to guess? Because it would have given away too much information for eavesdroppers looking at our qubits.

But adding a little uncertainty trips them up. Let’s see how it plays out. Once again, the server generates a random bit sequence and encodes it in random orientations. Now the server sends you the qubits, but the eavesdropper catches them along the way. The eavesdropper must act quickly. They need to measure the qubits and then send them back down to you so you don’t notice anything wrong. But the eavesdropper doesn’t know whether to measure vertically or horizontally.

If they guess wrong, the qubit changes. Plus, they wouldn’t even know if they guessed right or wrong in the first place, so they can’t fix their mistakes. Maybe, they could make copies of the qubits, send one copy to you so you don’t notice anything wrong, and then try all sorts of different measurements on their own copies to figure out what the qubits were. Too bad they would need to break the laws of physics to do that.

A principle of quantum mechanics known as the no-cloning-theorem tells us that you can’t make copies of qub itself you don’t already know what they are. If the eavesdropper wants to know anything at all, they need to measure the qubits. And unfortunately for them, that means they either need to send you contaminated qubits or dummy qubits of their own. Even if the eavesdropper eventually sees you and the server saying which orientations they should have used, it’s too late for them.

Unless they happened to guess the orientation correctly every single time you guessed correctly, or if by pure chance, the qubits collapsed to the right values anyway, you and the server will end up with different numbers. And taking a guess on all of your qubits is pretty much the worst strategy ever. But how do you and the server know if the eavesdropper was messing with the qubits?

You randomly pick half of your bits to compare. If they’re the same, you and the server know that the other half is the same as well, unless you’re astronomically unlucky. But to better your odds, you use more qubits so small mistakes from the eavesdropper are more likely to be noticed. If you ever notice a problem, you toss everything out and try again.

Hopefully, the eavesdropper will respect your privacy this time. This is known as the BB84 protocol. It’s one of the simpler ways of distributing quantum keys. There’s another one called the E91 protocol that takes advantage of quantum entanglement. This one is a little more complicated. First of all, instead of the server generating a random bit sequence, you both receive half of a bunch of entangled qubits from a trusted third party. You and the server then randomly pick from3 orientations to measure your own half.

You then compare orientations and note the ones that were the same. But instead of throwing the rest of them away, you can use the mismatches to check for an eavesdropper. You know there was an eavesdropper if something called Bell’s inequality was satisfied. If Bell’s inequality was not satisfied, it means that there was no eavesdropping, and the key is safe to use. Of course, these protocols aren’t perfect. They rely on the accurate transmission of qubits, which doesn’t always happen in the real world. And that’s assuming you can even send qubits in the first place.

The existing infrastructure of the internet cannot. But small quantum networks are being built. In addition, these protocols also don’t fix all the problems the classical ones have. For instance, man-in-the-middle attacks are still possible, where the eavesdropper impersonates both you and the server, so neither of you notices anything wrong. Denial of service attacks still is possible by simply “eavesdropping” on purpose. The eavesdropper will be detected every time, but you and the server will never be able to make a key and thus can’t communicate securely.

They break our current system, but they open the door for more advanced ones. But isn’t that pointless? Why the trouble? It’s because they open up new possibilities. Breaking security is just one of the many things they can do. Every new discovery comes with opportunities and costs. We can’t complain when the eavesdroppers are just using superior tech to our own. The threat is real, but people believe in advancing science and technology, because of its potential to improve our lives.

Leave a Comment

Copy link