Will Quantum Computers break encryption?

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
optimisation problems. They are not the full-blown quantum computers
that threaten our security. 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. For the moment, forget about encryption and
just think about what it’s trying to achieve. You and a server need to communicate with
each other. (And by “you”, I mean “your computer”.) 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. Let’s say that we scramble our data and
incorporate a special number into the exact way that we scramble it. 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. This private key was custom-made to unscramble
messages which this particular public key scrambled. These keys always come it pairs. 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 numberphile video, which goes into a bit more detail on how all
of this works. The short version is: Because 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 theserver 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. Everything here rests on the fact that keys
that can unlock messages are kept secret. We only share them secretly in 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 analyse it to create an exact copy of the corresponding
private key. They can essentially pick the lock. This is done by guessing tons of potential
private keys until a match is found. 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 the 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
aren’t they? So, once again… Are we DOOMED??? Possibly not. There is an initiative to create new encryption
standards in a world after quantum computers become
a thing: Post-Quantum Cryptography. 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 backwards, 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. The hard part here is the critical point of
this mechanism. 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 backwards. 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
backwards 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 function
that most of the internet uses can be broken by quantum computers. They make it easy to get the private key,
but only because there happens to be 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. That would keep this process easy, this process
hard. This is good in the shorter term, but we can
do better. Surprisingly, quantum computers themselves
come to save the day. They can let us do things with security that
not even public-private keys can do. Welcome to Quantum Cryptography. Conventional computers use bits which can
each be either 1 or 0. Quantum computers use qubits, which can be
1 or 0 or some combination of the two. 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. When we try to read a qubit, we need to choose
a direction to measure it 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 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 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 1s
and 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 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 risk of
being wrong. Now, you have your own random string of 1s
and 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. If you can perfectly guess the server’s bits,
so can an eavesdropper. 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 qubits
if 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? How do you know if these bits are safe to use? 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. And if they don’t, try a different communication channel. 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 from
3 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 accurate transmission of qubits,
which doesn’t always happen in the real world. So in reality, you need to sacrifice a bit
more information to do error correction. 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. They have all even successfully performed
the BB84 protocol. 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
notice anything wrong. Denial of service attacks still are 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. The solutions to these problems may involve
broader fields, such as authentication and networking. In the end, quantum computers are a double
edged sword, at least in the world of security. They break our current system, but they open
the door for more advanced ones. But isn’t that pointless? Why develop quantum computers in the first place if they break and then re-solve the same problem? Why the trouble? It’s because they open up new possibilities. Breaking security is just one of many things they can do. They can also improve database performance, and give us more accurate simulations of quantum mechanics, which could accelerate research in medicine or other technologies. Every new discovery comes with opportunity 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. Sometimes… we just need to keep up with it. Oh no… The video intro’s out of date!

Author:

100 thoughts on “Will Quantum Computers break encryption?”

  • Smells like total BS. If no one can read the message and then forward again, then it means you can't have routers and switches between you and the server.
    Then it also means you have a dedicated link to the server.
    If you have a dedicated link to the server, then your connection will only be insecure if someone physically tampers the connection.

  • So why can’t we just use randomly generated numbers and not bother with quantum mechanics? Also I still don’t fully understand how random numbers are supposed to be secure but eh.

  • I love the animation, direction, and even the narration for preferential reasons, but I'd be crushed if I found out later that the only reason I love the content is because I'm not more knowledgeable. How can the viewers decide the validity of the information? Would you highlight user comments that attempts to make an alternative or a modified explanation if they have some educational merit? I don't know if that's already a thing that youtube culture is trying to generate, but really: This work is so beautiful, that I can't exactly stop watching, so just asking….

  • Quantum computing is humankinds asteroid, It's the beginning of the end, our extinction point begins. Once we develop high power computing, we unlock AI, and make ourselves no longer useful. We will become pets.

  • I think you should have mentioned the holy grail of cryptography, which also plays an integral part of why Quantum Cryptography is so powerful: The so called one time pad. A key, which is only used exactly once and is exactly as long as the plaintext you want to encrypt. Even without quantum cryptography this method of encryption is, if applied correctly, unbreachable. Quantum Cryptography only…well…"only" solves the issue of secure key transmission

  • Update May 2019

    The Quantum Encryption presented can be exploited by spoofing.

    We still don't have a Quantum resistant public encryption. There are many efforts but none is a proven success. This means data that has been recorded today by an attacker can be cracked in the future.

    Yes we have many quantum computers around the world but not yet enough to doom us. More needs to be done.

    Historically, from Babbage to the present, computers were invented and developed to break encryption.

  • Wait so there will be multiple decades no internet access will be secure? This system requires each computer to have a quantum processor. They will have quantum computer soon, but they are not small…. it will be years before we will get this small enough for a laptop to have or even phones.

  • Hou did u get a mismatch information in a entenglad bit??

    If a bit are entenglad (and you mesure one of the entenglad bit) u know instantly the state pf the other bit.

  • Bryan Cooper says:

    My reason for watching this is due to Sean Worthington, inventor of @t – he invented the second technology fixing the "physical Integrity issue" with digital currencies. Quantum Computers are the biggest threat to Cryptocurrencies because the Blockchain is based on cryptography and one of the biggest functions of a Quantum Computer is cracking cryptographic codes. Theoretically a fully developed Q. C. can hack any blockchain based currency in under two minutes. The only "digital" not cryptocurrency is Cloudcoin and is NOT cryptographic and is 100% Q.C. SAFE. This is the anti-blockchain technology – called RAIDA. @t

  • R U mad!!?? Proper quantum computers use all 32 types of quantum **************(CLASSIFIED INFO) to compute!!!!!?!!!

  • Do you even know anything or you just ripped off this info from a fake site on the net? Your channel is good but…this video is total gross.

  • And by the way, there is one more top-secret protocol named KIAROX95. I'm sorry I can't share any info about that. And you will not find any info on it on the net. Only 'We' know about it.

  • Nice video. How do the server and client compare the orientations without the server giving up what orientation it used?

  • Ashley Haadt says:

    I always thought Schrodinger was being kinda mean but it looks like your clever kitty is getting even by leaving a big greasy surprise in the box for him. Your videos tend to clarify complex ideas better than most; they've been very helpful, thank you for posting them.

  • Im doing reasearch on quantum mechanics and cryptography for fun, and people like you make it possible
    Thank you for this video!

  • Charlie Parlie says:

    Wow…i didn't understand one thing. Anybody has any suggestion to improve mathematical reasoning or logic…😕

  • So Chrome creates a client key pair with every https session? Use the server public key to encrypt client session public key and send to server?

  • Redwan Hossain says:

    You think code breakers are DOOMED……? The more powerful the encryption is it will always be an open challenge with the hackers. Soon or late they will find another way to steal data

  • Thorwald von Drakasul says:

    Weapons of humans

    Hands
    Stones
    Spears and bows
    Swords
    Guns
    Atomic bombs…

    And at the end of the day your enemy has the same guns and atomic bombs and you fkd your self…

    But people or to dumb to understand…. so yeah.. lets break encryption with quantum computers!! Yeah!.. oh….

  • its too bad that cubits are only cubits while inside the processes, otherwise if in transmission it will already be in a binary state.. you cant send cubits through a line. not now, not ever, since our current rendition of quantum processes require low sub thermal temperatures.

  • I mean that when quantum computers work better, computer security technicians and pentesters or hackers will be obsolete?

  • George Andrews says:

    It would be easy to stump a quantum computer decoding a message. Simply don't tell it exactly where the message starts and stops and use key less encryption like enigmato…

  • The bad thing is, that a NSA will have quantum computers rather fast while it will take ages until I've got a quantum computer in my cellphone or at least at home. And during this time where a large organization can afford a quantum computer but I don't all communication is insecure and has to be treated as such. So yes, we are doomed.

    Also, how long will it take until we can transmit qubits? On the other hand a quantum computer doesn't need a qubit-transmission line to find out your private key. They just listen in on the conversation and then reverse calculate your private key. So yes, we are doomed.

    I really, really don't look forward to that time.

  • Faustin Gashakamba says:

    You can cut that part of the video that talks about current encryption technique and it would be the best video on YouTube about Public Key encryption.

  • yeah i'm still having trouble with the analogy. maybe talking about parts of a mathematical equation will make the idea concrete

  • Sleepy Ancient says:

    I'm don't think general quantum computing will be attainable for anyone who isn't a billion dollar entity. At least not for another 40 years. Why? Performance per dollar, upkeep, a developing world, and inconvenience.

    The technology is currently specialized because generalizing it would lose enough meaningful performance that a regular binary system would make more sense.

    TSMC barely has 7nm (same size as Intel's 10nm, because we don't have a universal standard for a nanometer), and Intel, despite making qubit processors for quantum computers, still struggles with 10nm on a mass production level.

    Besides the processing, there's the issue of outside interference and shielding (we need to drop below around -230 C to process the information in a way that's meaningful). And if Google failed to compete as an ISP with 1Gb/s internet, the infrastructure itself isn't feasible on a large scale, and won't be for a long time.

    Then, by the time the technology is ready, the largest developing countries in the world (China and India) will have populations moving away from menial jobs (Chinese factories are starting to show the signs of this, some not being able to find workers for the cheap pay). This means cost of living everywhere goes up.

    That means it's going to cost more for everything. We're enjoying a period of cheap technology because it's mostly outsourced. Once those countries cost of living goes up, then prices will be similar to domestic labor and we'll be paying for….

    Accounting for inflation and socialist economic policy (raising the minimum wage beyond inflation, to keep people happy on election day, which instead of combating inflation, artificially inflates it further… also, taxes will spike once we stop letting each other have more debt… dystopia here we come), we'll be paying at least 3 times, up to 10 times more for everything.

    TL;DR: We'll be using binary computers for a long, long time.

  • My Cat's Breath Smells Like Cat Food says:

    Thank you. I was learning a bit about encryption and couldn't figure out how the keys were supposed to be shared. This is so simple, but I didn't even consider it.

    I have a question about how hard it is to reverse that key, though… How long are we talking, and how often do those keys change? Someone could still just keep all the information they've stolen and work on cracking it, right? Once you've gotten the messages and the public key, the key to unlock those is set – nothing can change them. So someone could still be hoarding information with the keys associated with them until they can crack it, right? Or are the keys changing so often, you'd only get a bit of data before they key is suddenly changed?

  • I wrote an encryption method for messages that quantum computers can’t break.
    It doesn’t use keys and doesn’t allow you to know exactly when a encoded message stops or starts in the output.
    It is simple to use as you don't even need a computer to encode or decode it.

Leave a Reply

Your email address will not be published. Required fields are marked *