- Right now some nation statesand individual actors areintercepting and storing lotsof encrypted data likepasswords, bank details,and social security numbers.But they can't open these files.So why are they doing it?Well, because they believe that withinthe next 10 to 20 years,they will have accessto a quantum computerthat can break the encryption in minutes.This procedure is knownas Store Now, Decrypt Later or SNDL.And it works because thereis information around todaythat will still be valuable in a decade.Things like industrial andpharmaceutical researchand top secret government intelligence,and everyone is aware of this threat.The National Security Administrationsays that a sufficientlylarge quantum computer,if built would be capable of underminingall widely deployed public key algorithms.- You know in a five to 10 year timeframe,quantum computing will breakencryption as we know it today.- Even though sufficientlypowerful quantum computersare still years away,they're already a threat becauseof Store Now Decrypt Later,which is why the US Congressjust passed legislationmandating all agencies start transitioningright now to new methods of cryptographythat can't be broken by quantum computers.You know, our current encryption schemeshave been remarkably successfulworking effectively for over 40 years.Up until the 1970s, ifyou wanted to exchangeprivate information with someone,you would first have to meet up in personand share a secret key.This same key would be used toencrypt and decrypt messages.So it's known as asymmetric key algorithm.As long as no one else getstheir hands on the key,your messages are safe.But now what if you wanna send informationto someone you've never met,and it's too hard to arrangean in-person meeting.You can't share a keyover an unsecured channellike a phone line or the mail,because it could be intercepted.And this is what in 1977,led three scientists,Riverst, Shamir, and Adelmanto come up with anencryption breakthrough.Today it's known by their initials RSA,and it works something like this.Every person has tworeally big prime numbers,all their own which they keep secret.They multiply these numbers togetherto get an even bigger number,which they make publicfor everyone to see.Now, if I wanna sendsomeone a private message,I use their big publicnumber to garble my message.And I garble it in such away that it is impossibleto ungarble without knowingthe two prime factorsthat made that number.This is an asymmetric key system,since different keys are used to encryptand decrypt the message.So it's easy for my intendedrecipient to decode,but impossible for everyone else,unless they can factorthat large public number.Now, someone could try to factorit, using a supercomputer,in the best known factoring algorithmthe General Number FieldSieve, but modern cryptographyuses prime numbers thatare around 313 digits long.Factoring a product oftwo primes this big,even with a supercomputer,would take around 16 million years,but not on a quantum computer.See, in normal computers, a bit can onlybe in one state at a time,either a zero or a one.So if you had two bits, they could bein one of four possiblestates, 00, 01, 10 or 11.Let's say each of thesestates represents a number,0, 1, 2, or 3.If we want to do a calculation,for example, raising sevento the power of one of these numbers,we can only do it for one state at a time,in this case seven squaredand so we get the answer 49.Quantum computers consist of qubitswhich also have two states, zero or one.But unlike a classical bit, a qubit,doesn't have to be injust one state at a time.It can be in an arbitrarycombination of those states,a superposition if youwill, of zero and one.So if you have two qubits,they can exist simultaneouslyin a superposition of 0, 1, 2, and 3.Now, when we repeat the same calculation,it will actually perform the calculationfor all of those numbers at the same time.And what we're leftwith is a super positionof the different answers.1, 7, 49 and 343.If we add another qubit,we double the number of possible states.So with three qubits, wecan represent eight states,and thus perform eightcalculations all at once.Increase that number to just 20 qubits,and you can already representover a million different states,meaning you can simultaneously computeover a million different answers.With 300 qubits, you canrepresent more statesthan there are particlesin the observable universe.This sounds incredibly powerful and it is,but there is one very big catch.All of the answers to thecomputation are embeddedin a superposition of states,but you can't simply readout this superposition.When you make a measurement,you only get a single valuefrom the superpositionbasically at random,and all the other information is lost.So in order to harness thepower of a quantum computer,you need a smart way to converta superposition of statesinto one that contains onlythe information you want.This is an incredibly difficult task,which is why for most applications,quantum computers are useless.So far, we've onlyidentified a few problems,where we can actually do this,but as luck would have it,these are precisely the problemsthat form the foundationof nearly all the public keycryptography we use today.In 1994, Peter Shor andDon Coppersmith figured outhow to take a quantum Fourier transform.It works just like anormal Fourier transform,apply it to some periodic signal,and it returns the frequenciesthat are in that signal.Now this may not seemparticularly interestingbut consider this.If we have a superpositionof states that is periodic,that is the terms in thesuperposition are separated,by some regular amount,well we can apply thequantum Fourier transformand will be left with statesthat contain the frequency of the signal.So this we can measure.The quantum Fourier transform,allows us to extract frequency informationfrom a periodic superposition,and that is gonna come in handy.So how does a quantumcomputer factor the productof two primes much fasterthan a conventional computer?I want to explain this by first walkingthrough a simple example withno quantum computer required,and then I'll show how a quantum computercould execute this methodeven for a very large numberin a short period of time.So let's say we have a number N,which is the productof two primes, p and q.For the sake of this example,let's set N equal to 77.Now I bet you can guess the prime factors,but let's pretend for themoment that we don't know them,because with a product ofreally big primes, we wouldn't.Now I want to use a fact about numbersthat feels like magic.Pick a number g that doesn'tshare any factors with N.If you multiply g by itselfover and over and over,you will always eventually,reach a multiple of N plus one.In other words, you canalways find some exponent r,such that g to the power of r,is a multiple of N plus one.Let's see how this works.Pick any number that is smaller than 77.I'll pick the number eight.This number doesn't share factors with 77.And if you were doingthis with big primes,it would also be extremely unlikelythat you just happen to pick a numberthat shares factors with N.Now multiply eight by itselfonce, twice, three timesfour times, and so on, raisingeight to ever higher powersand then divide eachof these numbers by 77.We're not really interestedin how many times77 goes into the number,just the remainder,what's left over, because at some point,77 should divide one of these numberswith a remainder of exactly one.So eight divided by 77 iszero with a remainder of 8,64 divided by 77 is zero remainder 64.512 divided by 77 is six remainder 50.And as we keep going, we get remaindersof 15, 43, 36, 57, 71,29, and finally one.So there we have it,eight to the power of 10is one more than a multiple of 77.So we've found the exponent Rthat satisfies this equation.But how does this helpfind the factors of N?Well, we rearrange the equationto bring one over to the left hand side,and then we can split itinto two terms like so.And now as long as r iseven, we have one integertimes another integer isequal to a multiple of N.This looks remarkably similarto p times q equals N.I mean since we know that p and qare on the right handside of this equation,they must also be on the left hand sidejust multiplied by someadditional factors.So one way to thinkabout what we've done iswe've taken a bad guessfor one of the factors G,and by finding the exponent r,we've turned it intotwo much better guessesthat probably do share factors with N.Since r was 10, the two termson the left hand side are eightto the power of five plus one, 32,769and eight to the power offive minus one, 32,767.These two numbers probablyshare factors with N.So how do we find them?We use Euclid's algorithm.If you wanna find thegreatest common divisorof two numbers, say 32,769 and 77,divide the bigger numberby the smaller oneand record the remainder.In this case, 32,769 dividedby 77 gives a remainder of 44.Then shift the numbers oneposition left and repeat.So now we divide 77 by 44and we get a remainder of 33.Repeat the process again.44 divided by 33 gives a remainder of 11and again 33 divided by 11equals three remainder zero.When the remainder is zero,the divisor is the greatest common factorbetween the two numbers you started with.In this case, it's 11,which is indeed a factor of 77 and 32,769.You could do the same procedurewith the other number or justdivide 77 by 11 to get seven,its other prime factor.So to recap, if you wannafind the prime factors p and qof a number N, first, make a bad guess, g,second, find out how manytimes r you have to multiply gby itself to reach onemore than a multiple of N.Third, use that exponent to calculatetwo new numbers that probablydo share factors with N.And finally use Euclid's algorithmto find the shared factorsbetween those numbers and N,which should give you p and q.Now, you don't need a quantum computerto run any of these steps,but on a classical computer,this method wouldn't be anyfaster than other methods.The key process that aquantum computer speeds upis step two, finding theexponent you raise G2to equal one more than a multiple of N.To see why, let's go back to our example,where eight to the power of 10 isone more than a multiple of 77.Watch what happens to the remaindersif we keep going pasteight to the power of 10,to 8 to the 11, eightto the 12, and so on.Well, we get remaindersof 8, 64, 50, 15, 43, 36,57, 71, 29, and again one.The remainders cycle andthey will just keep cycling.Notice how the exponentthat yields a remainderof one is 20, which is 10more than the first exponentthat yielded a remainder of one.So we know that eight to the 30and eight to the 40, 8raised to any power divisibleby 10 will also be onemore than a multiple of 77.It's also worth noting thatif you pick any remaindersay 15, the next time youfind that same remainder,the exponent will have increased by 10.So you can find theexponent R that gets usto one more than a multiple of n,by looking at the spacing ofany remainder, not just one.Remember that.Here I'm plotting out theremainders on a log scaleso you can see they areperiodic with a period of 10.If I had made a different guess,say I had picked G equals15 instead of eight,well then the period would be differentand the remainders would be differentbut there would alwaysbe a remainder of one.Why is this?Well, now that you can seethis is a repeating pattern,we can go back to the beginningand any number raised tothe power of zero is one.So that is actually the first remainder.So it must also appear whenthe cycle starts again.Now we are ready to use a quantum computerto factor any large product of two primes.First we split up thequbits into two sets.The first set we preparein a superposition of zeroand one and two and threeand four and five and sixand seven and eight and nine,all the way up to 10to the power of 1,234.Yeah, this is a huge superposition,but if we had perfect qubits,it would require only around 4,100.The other set contains asimilar number of qubitsall left in the zero state for now.Now we make our guess G,which most likely doesn'tshare factors with N.We raise G to the powerof the first set of qubitsand then we divide by Nand store the remainder inthe second set of qubitsleaving the first set of qubits as it was.Now we have a superpositionof all the numberswe started with and theremainder of raising Gto the power of thosenumbers divided by N.And through this operation,we have entangled our two sets of qubits,but we can't just measurethis superposition.If we did, we would get arandom value and learn nothing.But there is a trick we can use.If we don't measure theentire superposition,but only the remainder part,we will obtain some random remainder.But this remainder won't occur just once.It will occur multiple timesevery time it comes up in the cycle.Imagine we were doingthis with the examplefrom before with N equals77 and G equals eight.If the remainder we measured was say 15,then there would be multipleterms in our superposition.Because there are multiple exponentsyou can raise G2 thatgive this same remainder,exponents 4, 14, 24, 34, and so on.They are each separated by 10,and that value is the exponentthat satisfies our equation.So more generally aftermeasuring the remainder,we will be left with asuperposition of statesthat all share the same remainderand the exponents will all be separatedby the same amount r.This is the number we are looking for.Since the remainder is nowthe same for all states,we can put it to the sideand we now have asuperposition that is periodic.Each term is separated fromits neighbors by an amount R.If we now apply thequantum Fourier transformto this superposition of statesand I'm simplifying a little here,we will be left with statescontaining one over R.So all that's left to do nowis perform a measurementand find R by inverting it,and that's it for the quantum part.Now, as long as r turns out to be evenwe can use r to turn our bad guess ginto two numbers thatlikely share factors with N.And as long as these terms themselvesare not a multiple of N,we can use Euclid's algorithmto find the factors of Nand break the encryption.This would only take severalthousand perfect qubits,but the qubits we havetoday are imperfect,so we need additional qubitsto act as redundant information.In 2012, it was estimatedthat it would take abillion physical qubitsto break RSA encryption,but by five years later that numberhad dropped to 230 million.And in 2019, after moretechnological breakthroughs,that estimate plummeted to just20 million physical qubits.So how many qubits do we have today?Well, if we look at the stateof IBM's quantum computers,we are nowhere near that number of qubits,but progress looks to be exponential.So now it's just a questionof when these two curves will collidebefore all our existing publickey encryption can be broken.Because we've long knownthis threat is coming,scientists have been lookingfor new ways to encrypt data,which can withstand attacksfrom both normal and quantum computers.In 2016, the National Instituteof Standards and Technologyor NIST, launched a competitionto find new encryption algorithmsthat aren't vulnerableto quantum computers.Cryptographers from all over the worldsubmitted 82 different proposals,which were rigorouslytested, some were broken.And then on July 5th, 2022,NIST selected four ofthe algorithms to be partof their post-quantumcryptographic standard.So how do they work?Well, three of the algorithms are basedon the mathematics of latices.So let's do a simpleexample in the 2D plane.Take two vectors, r1 andr2, by adding togetherdifferent integer combinationsof these vectors, say threetimes r1 and one times r2,you can get two different pointsand all the points you can getto by combining these two vectorsin different ways iswhat is called a lattice.Now I will also give you the point C,and your task is to tell mewhich combination of r1 and r2will bring me to thelattice point closest to c.It's pretty easy to seethat we can get thereby going in the direction of r2 twiceand in the negative direction of r1 twice.Simple enough.But those vectors, r1 and r2 are notthe only vectors that cangive you this lattice.Take b1 and b2 for example.These vectors also buildup the same lattice.And now if I ask youthe same question again,can you tell me thecombination of b1 and b2that gets you to thelattice point closest to c?This has become a lotharder, but why is that?Each time we're taking a step,we're trying to get closerin either the X or Y direction,but with the b vectors,each time we take a stepin the right directionwith one vector, it puts usoff in the other direction.And that's why these vectorsare a lot harder to work with.In the end, it takes us a combinationof eight times b1 andnegative six times b2to get to the closest lattice point.That is a lot harder than before,but it's still a relativelyeasy problem to solve.But if we extend it to three dimensions,this already becomes a lot harder,especially because you'renot given the collectionof all lattice points.You're only given thevectors that make it up.So when you find a latticepoint close to the target,you must still find all theother lattice points near itto make sure yours is indeed the closest.Let's take a circle ofradius r in two dimensions.The number of latticepoints inside the circleis proportional to r squared.Add a third dimensionand the number of pointsin the sphere is proportional to r cubed.So just watch how the numberof lattice points growsas we increase the number of dimensions.Solving the closest vector problemis a piece of cake for yourcomputer in three dimensions.Even a hundred dimensionsshould be manageable.But in proposed future encryption schemes,we'll use around a thousand dimensions.Take one step in the right directionon one of those dimensions,and you could potentiallybe taking a wrong step inthe other 999 dimensions.You win some, you lose everything else.With that many dimensions,it becomes extremely hardto find the closest pointeven for the most powerful computers,that is unless you knowa good set of vectors.So how do we use that to encrypt data?Well, let's go back to ourtwo-dimensional example.Each person has a good set of vectorsthat describes a lattice,but they keep these vectors secret,and they only share their lattice publiclyusing a set of vectorsthat is hard to work with.Now, if I want to send someone a message,I pick a point on theirlattice, for example,say this point correspondsto the number seven.So if I wanna send the numberseven, I can take that pointbut then add some random noise to it.So the message I send is not preciselyat that point but close to it.Now, to decode the message,my recipient must figure outwhich lattice point isclosest to the message point.In a thousand dimensions,this will be extremely hard to dounless you have the nice set of vectors,which my recipient does.So it's easy for the recipient,who has the good vectors,but hard for everyone else.And as far as we know,this problem is extremelydifficult to solve for bothnormal and quantum computers.Behind the scenes, there'san army of researchers,mathematicians, and cryptographers,we're gonna make sure yoursecret data stays secret.These are some of the unsung heroesthat will keep us safe moving forward,avoiding mass surveillance by governmentskeeping critical infrastructure protectedand allowing you to liveas if quantum computerswere never invented in the first place.(digital buzzing)Something that fascinates me is being ableto see where the world is headed.And right now it's clearthat quantum computersand AI chatbots are going toplay bigger and bigger rolesin our lives in the coming decades.Even if we don't know exactlyhow they'll be implemented,I think it's important tolearn how they work right nowand you can do that with thisvideo's sponsor, Brilliant.Brilliant has an incredible courseon quantum algorithms.This one was co-developedwith Microsoft and Alphabet X.I love that you can simulatequantum gates and writeand execute real quantumalgorithms right in the lesson.No need to set up your owndevelopment environment.And if you want to divedeeper into cryptography,making and breaking codes isreally a matter of statistics.Strong statistical reasoning skillshelp us find patterns in dataand make sense of them,which is crucial to masteringjust about any topic in mathand computer Science.Brilliant's course on data analysiswill help you ramp up fast.It uses everyday situations,like business models toillustrate key conceptsin statistics and it's interactive,so you can get hands onwith data visualizationsand develop a real intuitionfor interpreting them.You know the thing thatsets Brilliant apartis they know how tobreak fundamentals downinto their core building blocks,whether you're learningmath, computer scienceor data analysis, Brilliant'sthousands of bite-sizedinteractive lessonshelp you master key conceptsand build to more advanced topics.You can try everythingBrilliant has to offerfor free for a full 30 days.Just go to brilliant.org/veritasium.I will put that linkdown in the description.And for viewers of thisvideo, Brilliant is offering20% off their annual premium subscriptionto the first 200 people to sign up.So I wanna thank Brilliantfor sponsoring this video,and I want to thank you for watching.
