How Will Cryptography Survive The Rise Of Quantum Computing?

[Music] good morning when i started preparing this i didn't realize it's going to be at 8 30 a.m so brace yourselves this is going to be tight okay quickly my name is rakim i teach computer programming i live in finland that's my blog and twitter this is the company i work now at the moment it just started not much there codexpands.com the plan we want to talk about quantum computing and how it applies to cryptography but to do it we have to build the base a bit so we're going to start with the computer and how to build a computer and then move to cryptography using regular modern computers and then learn a bit about quantum mechanics so that we are

able to understand something about quantum cryptography and the ways quantum computers break modern cryptography so computer maze of bits in all that could be zero one uh it's not a physical thing it's just an idea uh i can be a bit so i can say this is me zero this is me one and now i can encode something as long as we all accept this language a light bulb can be a bit a electricity could be a bit like low voltage high voltage that's how your processors actually use bits it could be physical like in a laser compact disc you see these nice colorful things they are uh there because the surface of the disc is not actually flat it's flat and

has so little pits and they don't directly correspond correspond to zeros and ones but they are technically like bits so you can use something to uh encode something into bits as long as you all accept the rules now when you have bits and then you combine them into logic gates any programmer knows logic operators like and or again this is just an idea um and if you have again i can be an and gate like give me two bits i'll give you the answer uh you can implement them on or gate you can implement them using something physical you can probably train a dog to be a logic operator because well it's not not much

there to learn here's an and bid implemented with dominoes so this guy pushes two things which means one one and the answer is also one falling down means one but if he pushed only one left one or the right one the answer would be zero because zero and one is zero the way logic gates are implemented in modern computing is with transistors those on the left they're built about coin size big from about 50 years ago and then you see they go smaller and smaller and that's basically an electric switch and your modern cpu has like billions of those why well if you combine them in somewhat complex ways like here you can make math

because if you combine gates like this and you put some input bits you get the sum of those bits and that's the full adder that's how it works in action as long as you keep adding stuff you can get more and more complex math because if you have addition you have multiplication and if you have multiplication then um you can have everything because multiplication is the key to everything and here's by the way a nice sci-fi book i read recently highly recommended there are multiple cool ideas in this book but one of the ideas is there's this civilization they don't have computers or electronics but they do have a notion of computing so they use soldiers

to implement logic gates thousands and thousands of soldiers and they have this rule that flag down means zero flag up means one and then they arrange soldiers and they try to compute some hard mathematical problems so if you have bits and you have logic gates you have a computer now this part is of course the most difficult and i'm skipping it because we only have so much time and this is similar to this it's like you do something and then magically you have the answer but if you're interested in those heartbeats if how do you go from beats to modern computers then i also highly recommend those two books by the same author one of them on the left goes from light

bulbs to modern computers and the second one talks about the scientific paper by alan turing that started this whole thing all right so we assume we know how computers work that's how they basically work you are here we are now ready to talk about cryptography as you know cryptography is a way to make information secret to hide something so that only specific people can read your messages so one of the simplest and most obvious ways to encrypt a message is to just shift it within the alphabet we done it as kids probably and romans did it thousands of years ago and if you just take some say english text and shift it by some number

like three you get this and if you're not from hungary this is not hungarian although sorry i had to do it so romans used it about 2 000 years ago and i guess it worked for them because they looked like that and their enemies looked like that so not much to hide there but today that won't work it's so easy to crack it you can just guess you can look at and the worst case scenario you just try all the combinations and in english there are 25 different options so this is the idea behind the simplest symmetric encryption and up to about the 70s that's all we had this is the top of the symmetric

encryption machines the nazi used in the world war ii it's much more complex than the simpler simple shift because for a single letter they used different combinations every time and they changed every day and then every month but it's still something that first year computer science student can crack in about 50 lines of code today that's symmetric encryption where you use the same key to encrypt and decrypt and now your problem lays in this communication of the key because as long as someone has the key they can encrypt your message so this is not perfect this is why from about 70s we have a much better idea of asymmetric encryption and the idea there is let's say this on the left

is me on the right is that's my sister as you can see we are related i don't have a key she has both the key and the lock and the lock is public she gives it to everybody when i want to send her a private message i take her lock and i encrypt my message with her lock and give it to her only she can unlock it because only she has the key she never shares the key that's the basic idea so it could be done with locks but we only have computers that can only do math nothing else so how do we do it with math well we need something that is mathematically easy to

kind of lock one way but hard to unlock if you don't have the key and one of the things that works in math like that and it's called the one-way function in math is multiplying large prime numbers if you just pick two prime numbers you multiply them it's easy you can do it on your computer even if the numbers are really really big but if you have that number n it's really hard to find what prime numbers were used to produce it so how to apply this idea to encrypt messages over simplification again but this is how the rsa works basically you pick two prime numbers let's pick really small ones two and seven you

multiply them you then find a special value called phi of n there's a whole bunch of number theory in it we won't cover it but trust the system this is the formula you use and you get six and now the fun part you pick a number e which is your encryption key and again you have some constraints you don't see it but uh there's math uh number theory and math there but you have a few choices when you have uh large prime numbers so i pick five within those constraints and then i also pick d which will be my decryption key the secret key again i have some rules to pick it but i have some choices and i

choose 11. now we have the kit we have the public keys and we have the private key so my sister generated all that i want to send her a private message so i take her public stuff the 5 and 14 and now let's say i want to send her a simple message c letter c i convert it to a number any way i want maybe utf like a unicode or whatever i convert it to number three because c is the third letter of the alphabet and then i take three raise it to the power of that e 5 and see the result mod 14 and mod 14 is the remainder after integer division so we

have 243 we divided by 14 we get the remainder three oh sorry five five is the secret message this is the thing that i'm gonna send her and she can see now she has the private key and she has the encrypted message she does the same thing but with the private key so she raises it to 11 she does mod 14 she gets three and that's how it works basically there are more layers to this but that's the idea behind much of modern cryptography so you see the problem here is it is hard to guess those numbers and it is hard to find them with large enough prime numbers it will take billions of billions of years on a

regular computer to just find those prime factors because the basically the only way you have is to try all of them all right we have the idea behind computers and we have some ideas about cryptography now to talk about quantum computers and quantum cryptography we need to dive just a bit into quantum mechanics so remember in chemistry classes in in high school we talked about those covalent bonds like you have h2 which is two hydrogen nucleus connected like sharing an electron and i could never understand like sharing an electron is it like going around two nucleus at the same time is it like running around because i have this idea and many of us do this is the atom right

it has the nucleus and it has electrons like planets running around them and that picture is nice it's easy to understand but it's wrong because electrons actually are not those balls that could be anywhere the idea of asking where is this electron at the moment does not make sense because if you don't ask that question if you don't look at the atom it's not anywhere it's not in any particular place so it's not like that electron is running around the nucleus it's a probability around that nucleus and it has some probability of being here being here so it's a cloud of somethingness and when they say two hydrogen nucleus nuclei sharing an electron that means the

electron is at both places at the same time it's with that nuclei nucleus and with that at the same time it does make sense it shouldn't because quantum physics is like that it's counter-intuitive we hate it because it it doesn't fit the way we think about the world naturally so for the longest time scientists scientists were asking a question what is light you you know this probably from from physics in high school is it a wave is it a particle and the problem with that question is if you are into waves you can produce experiments that will prove it's a wave if you are into particles you can produce experiments to prove it's a particle so

it's hard to guess it's hard to find out and one of the ways to think about it is well if it's a wave then it should behave like a wave so if you have like a wave of water and you put two slits in front of the waves then on the other side you should see this interference pattern like here's the screenshot from a video on youtube where a guy pushes two balls onto the flat pond of water and produces two sources of waves and those waves collide into one another and they produce these flat pieces where uh waves like high point of wave goes with a low point and they cancel each other and at some points they

amplify each other this way you have the interference pattern but if particles are shot through the same double slits then you should see just two lines right they go through left one or through the right one like

i'll switch to this one okay so the problem with this is if you look at particles like photons or electrons like that then you do an experiment and you should you shoot electrons or photons through double slits you still get an interference pattern as if it's a wave and okay well that proves it it's a wave then but they think okay maybe it's not a wave but there's still like little balls of things that collide with each other and produce this interference pattern so let's shoot them one by one just one at a time and if you do it you still get the interference pattern like one thing it goes through something like the left foot or the

right slit and then it lands on that side as if it was part of a wave it doesn't make sense and the only good explanation to that is it's doing it's going through both leads at the same time you should one electron it goes through both things at the same time with some probability and then collides with each other on the other side and produces the interference pattern but if you put detectors on the slit and you want to see is it going through the left one or is it going through the right one you'll see the answer like this one went through the left one but you won't see the interference pattern anymore on the other side you'll

see two lines as if those those were particles so the fact of observing the answer collapses the answer to one thing and it's not like our minds controlling the universe by observing it it's because at this point observing means interacting you cannot observe a photon without touching it like kicking it and by doing it you collapse it to one possible scenario which is left or right so things on this scale like photons electrons even small atoms behave like that and they could be in for example two states at the same time they could be at two states at separate times so with things like photons on the right side there is a property called spin which is a bit

harder to get at this point but we can just think of it as a photon looking up or looking down so it could be in one of those states and you can apply some energy and move it from one state to another state which means you can use them to create bits just like you use light bulbs or electricity and at this point this is no better than any regular computer you still have bits you still have two states distinct discrete states but those quantum objects as i said they can also be in both states at the same time with some probability so we could have an electron that looks right uh sorry left so it's kind of somewhere between zero

and one with fifty percent probability and that's what they call a qubit uh it could also be like this way and technically you can have many many more possibilities and technically infinite number of different states between zero and one so if you have computers with bits and logic gates then quantum computers are quantum bits with quantum gates the gates that operate on those qubits and again this is the long part which is the most difficult now if you google about quantum computing and look at popular articles or lectures or stuff like that there are a few levels of the way they describe it and one of the first levels is some journalists might say well quantum

computers have more than once and zeros our regular boring computers only have two bits zero and one and these powerful quantum computers have more than zero and one that makes them really really fast which is again not really true we could have more bits than zero and one is there's not like a physical limitation to that and there are actual computers with uh trinary systems where they have zero one and three or zero one and two and it's not that that gives us power uh two bits is enough for all the power we need another level they might describe it is well the bits can be zero and one at the same time this means this computer is infinitely

parallel like this quantum computer does something that a classical computer does but it does it in infinite many uh states at the same time so it's like a super parallel computer which is technically true but effectively isn't because if you look at this and you think a quantum computer is just a bunch of classical computers working at the same time it sounds really good but the problem is they do but at some point you want to get the answer out of those you only get one one at random so it's not really it's it's not helpful to think about quantum computers as computers classical computers that work in parallel it's like a superposition of multiple

classical computers just like a photon on an electron could be in superposition of different states so if you are looking for factors of n like those prime numbers then your machine is in different states of looking at different numbers at the same time but then you want to see the answer and it gives you the answer like it says this number is not a factor well that's not helpful i could have done that with a classical computer at random just pick random numbers and see if there are factors or not so it's kind of similar to this to a gaming die when it's in the air it's in like superposition of different states but it's not helpful because you

want to see the answer and you put it on the table and you only have one answer it collapses to that one answer so you keep going and you say okay this is also not a factor and if you're lucky then at some point you get okay this is a factor again you could have done that with a classical computer at the same speed so this particular property of quantum computers that's not enough to solve that particular problem of finding prime factors but they do find prime factors by changing the problem by taking advantage of these weird quantum properties because if you switch from the idea of finding prime factors to a problem of finding a period of a

function which is again provable by means of number theory that you can kind of rearrange the problem into finding a period of some function and then at some point get the prime factors then your answers are still random but then less random than that they are less random than a perfect die they are more likely to land on a particular value which is the correct answer so you might repeat the same thing multiple times and then you see the answer is x is more likely to be there it's statistically more likely and it's like a gaming day which is crooked like it's it's uh not fair maybe it's heavier on one point if you do

if you throw it multiple times it's more likely to land on one side and this is the idea behind many algorithms in quantum computer uh quantum computing this particular one is called schwarz algorithm and the idea with other algorithms as well is that you make the problems so that you you play with it so that it's more likely to not give you a completely random answer but more likely to give you a correct answer and with with repetition with enough tries you just look at the statistics and this top answer is probably the correct one this lower one is probably the wrong one so this is how roughly you get about solving problems in cryptography with a

quantum computer now the idea there is you have a problem designed for a classical computer and the problem of finding prime factors is really really hard on a classical computer it could be somewhat easy on a quantum computer we're not there yet well the problem with quantum computers is you need something to have those bits you need those atoms or electrons or photons and it's really hard to control them because if you put them in some state then basically any fart can change them anything like a smallest smallest interaction with a particle flight or temperature can change them so it's really hard to make this computer a stable computer this is why those fancy quantum computers are so big most of

that space is um it's basically a fridge that you want your quantum computer to be at about absolute zero so that no jiggling no temperature affects it but at some point we will get there probably uh the shores algorithm was implemented um before was like written before quantum computers existed and then it was implemented with one of the first quantum computers and uh it produces the answer that seven is a factor of 21 which which is good we're getting there but we need now to scale it to like billions and billions but this could be a race um with no end like we could create new algorithms that are harder and harder to solve and then

maybe come up with more quantum algorithms to actually solve them so what can we do to guarantee that we can create some cryptography that is unbreakable by even a quantum computer and this is the area of quantum cryptography actually using these weird quantum properties to create new algorithms based on quantum properties to encode messages and we're going to jump right into it again this is an algorithm's algorithm called bb24 and we are back to the land of symmetric keys so the idea is we want to share the same key and use it for encryption and decryption but now we're going to use it quantum way so those balls again are let's say photons and it can look up it can look down it

can be in one of those positions and then left and right and you have detectors to detect what position is it in if you use the correct detector like if you have up or down photon and you use the vertical detector you get the correct answer you get zero up one down but you also have a horizontal detector and if you use the horizontal detector on the vertical photon you get a random answer zero or one so you basically have like the correct detectors for a photon and the incorrect detector for photo so my sister generates a series of random bits should be big enough but in this example it's it's small just at random

she then picks random detectors for each bit again completely random and based on those she produces qubits she produces photons of the correct orientation so that if i were to know the detectors and she gave me the photons i could produce the same bits but she doesn't tell me the configuration of the detectors she only gives me the qubits so i get those photons in some configuration and that's it this is our first point of communication and this communication is done on a quantum channel on a channel that is capable of sending qubits in this example we are using photons so we could use something like a fiber optic cable that is capable of basically

moving a photon from one point to another without changing its orientation its state so this is still communication and this is still like some cable lying around someone could listen to it right so let's say some evil person listens to the to the communication that's my go-to evil person all the presentations i use the problem there is it's a quantum communication with quantum bits and if hitler listens and tries to see what qubits are there he needs to use detectors but he doesn't know what detector to use if he uses the wrong detector for qubit it will flip to either zero or one at random by doing it he might change the the qubit so when i receive the message

after listening after hitler listens to it i might get a different message and with the long big long enough messages i got i am guaranteed to get the incorrect message and you'll see how this works in our favor so let's say i get the message i then also pick detectors at random because i don't know the correct configuration of detectors so i just pick them at random and i produce some bits by applying them to the photons if you think about it you can see that statistically i will get 75 percent right because 50 of the detectors i will choose correctly and out of those 50 incorrect chooses i will get 50 at random correctly so

i'll get 75 of bits correctly then i just call my sister on a regular unsecured line like a phone and we just compare detectors we don't talk about bits we don't talk about photons i say for the first position i chose that detector and she says me too so i see okay then my beat should be correct on the second i chose this detector and she says no i chose that detector and i say okay this bit is incorrect then i chose the wrong detector so i just discard the wrong bits comparing them and again at this point hitler might be listening too because it's now just a regular phone line so he listens and he says okay he now

knows the configuration of detectors that we used but he doesn't have the photons in the same state because if he had then i would have gotten the wrong message so after doing this we just discard the wrong bits and now we have the shared key and it's all about statistics because with message small enough like this hitler could be lucky but we need to produce big messages and then we are guaranteed statistically to be safe and there are also ways to detect if the the message was listened to because we can also detect changes in the state of the qubits this was really fast i'm not sure if this is enough it's a really quick overview there are

resources that you can get into to learn about this is fascinating and this was a theory for a few years and then they actually implement it and all over the world in multiple places they could create a secure channel by doing this quantum encryption and actually if you drive from here for about two and a half hours to the east uh they did one of the first demos in vienna where they created a secure channel multiple links and it works it's amazing so even though quantum physics is this weird unpredictable randomness which doesn't make sense to us because we want things to be not random we want things to make perfect sense we want to predict

outcomes it turns out we can use this in our advantage so this fundamental property of the universe of not being sure about itself can be used for example in secure communication so if you want to learn more about this there are a few resources that i recommend there's an interactive essay and there is this blog by a quantum scientist and he also wrote a book called quantum computing since democritus and there are a few channels on youtube i particularly recommend this frame of essence channel which describes both quantum computers qubits and quantum cryptography using this algorithm that i described and some other algorithms those links will be on my website at this address feel free to ask me questions or

anything i'm not a specialist in this area at all i'm just really curious about it i think it's it's quite amazing and thank you [Applause] [Music] you