The 8-Year Battle Royale that Saved Encryption

Imagine a world where nothing is safe online. Your bank details aren't safe when you shop. Your privacy isn't assured when you browse. No confidentiality when you troll in the comment section. That would be our world if it weren't for one of the most powerful and underrecognized inventions. Encryption.

Banks and e-commerce use algorithms like RSA to protect your financial data. VPNs use it to protect your privacy. And when this user asked Reddit where RSA is used, they learned that Reddit's HTTPS certificate uses RSA. And in fact, most websites secure user data in this way.

But there's a problem. Many of these algorithms will be broken by quantum computers, allowing a bad actor with a sufficiently powerful one to discover our bank details, passwords, and god forbid, our Reddit histories. Regular announcements of more and more powerful quantum computers might frighten you, but fear not. NIST has prepared for the day RSA falls by hatching a plot to find quantum resistant encryption systems, the next RSA.

How? Well, the only way that makes sense. An epic near decade long battle royale featuring dozens of competitors where cryptographers could submit their schemes, launch attacks on rivals, and optimize to satisfy the referees. But only a handful survived to become the new standards that your security depends upon. Ingenious new methods mined from the deepest pits of pure mathematics, rivalries, drama, heartbreak, satisfying acronyms, and surprising twists. This story has it all. It's like beast games, but actually offering something to society.

Join me on this journey as we explore all the drama of this competition, the maths of these systems in full detail, requiring little background knowledge, how quantum computers even work, and why these new schemes are resistant to quantum attacks. also protect your data and your privacy. This is the race for postquantum encryption.

This video is long, even by my standards, but I promise you the whole journey is worth it. It's basically three of my usual math videos, around 40 minutes each, but with the narrative of this contest woven in between. So bookmark the video or save it in your watch later if you need to take breaks in return or dose up on caffeine and ignore your responsibilities for the next few hours. Whatever works for you.

Now I promised this video requires no background knowledge. So let's begin with cryptography and introduce some of the key terminology and some of the private key terminology. Firstly, we want to be able to send messages in a way that if someone intercepts the message, they can't read it, but the recipient can. This is encryption of my message into garbled cipher text that's nonsense to me, but that I can decrypt back into the message. Crucially, we want the method to be hard to crack with no obvious hidden patterns in the cipher text. Jeez, I wonder what that says. But also, we want a system that doesn't require transferring instructions.

[music]

For example, I could write a really complicated scheme that's tough to break, use it to encrypt a message, and then send the instructions on how to decrypt. But if I intercept the instructions, I can access the message. An ideal system is one where the attacker doesn't gain an advantage by knowing the instructions.

One option is called asymmetric key encryption. All parties have their own lock and their own key. Now, your lock is common knowledge. Anyone can take a copy of it and use it to secure a message. But once it's snapped closed, it is extraordinarily difficult to pick or unlock. Only its paired key can unlock it. And this [music] is kept secret.

Now, in practice, your lock is called your public key [music] because it's accessible to everyone. The key is called your private key. Now in reality we aren't talking about physical locks and keys but some mathematical principles where the public key scrambles a message and its paired private key unscrambles. As a very simple scrambling example, say yellow Alex has public key 9 and to encrypt I nudge the letters of my message nine places forward in the alphabet.

[music]

For demonstrative purposes, let's say this is total nonsense to me and I'm unable to even guess the private key, which is actually 17. I clock the letters forward 17 spaces and recover the message. Notice that only 17 recovers the original message. So without that, you can't unscramble. Now, in reality, this scheme is far too simple, but hopefully you get the idea. It's called asymmetric encryption because we all have different private and public keys.

A cleaner alternative is symmetric encryption where the recipient and I both have just one shared private [music] key which is used to lock and unlock the message. Continuing our example, let's have a shared secret key of nine. Locking pushes the letters forward by 9 while unlocking pushes them backwards by 9. So, it's great, but the tricky part is that we both need to know a shared secret key. How do I tell him what it is without it being intercepted?

I use what is called a key encapsulation mechanism or chem. This is a way of exchanging garbled information which only we can convert into a shared secret key which can be used for the remainder of the session. Perhaps the most famous example of this is the Diffy Helman key exchange. This works by everyone knowing two numbers. The recipient and I then choose random numbers and keep them [music] secret, keep them safe. We then take G to the power of our numbers, take the remainder after dividing by P, and show the answer to each other. I could intercept these, but that doesn't tell me what their secret keys are. We then take our partner's number to the power of our own secret key and take the remainder after dividing by P. The mathematics of this system is such that we both get the same answer, nine. And thus we have established a shared secret that we can use for the remainder of the session. And never did we have to transmit that number.

In practice, I could have just used brute force to discover their secret keys. I'm not an idiot. But in reality, they make the numbers huge enough that brute force is infeasible.

The second cryptographic challenge is that of digital signatures. This allows me to attach some content to my message, i.e. sign it with a signature, which allows the recipient to verify that it came from me. This is important for two reasons. Firstly, sometimes it's vitally important to know the exact origin of the message. But secondly, even if we can do all of this key exchange stuff, who's to say we haven't both accidentally shared secrets with a bad actor? This is called a man-in-the-middle attack. Imagine I thought I was establishing a shared key with yellow Alex using the Diffy Helman exchange when in reality I was redirecting the messages and establishing a shared key with both of these fools allowing me to snoop. Yeah, signatures can help avoid this.

As a very basic example, I send my message with the following signature and advertise five as my signatures public key. Anyone can then use my public key to unscramble the signature. It works because my signature has 21 as the private key which only I know. So only that can be used to generate the correct signature. Had anyone else signed the message with the wrong private key, the verifier would use my public key and verification would [music] fail. Again, this example is too simplistic because the signatures are easy to forge. So proposed signature schemes need to be better than them.

The final challenge is that however effective a scheme is, [music] it needs to be efficient. Anyone can make a secure scheme that involves garbling the message into terabytes of data, but that's no good in practice where we often need to execute these processes quickly and in bulk. Even data in the order of mere kilobytes needing a few seconds to execute can be too much when we need to send and receive thousands of messages. So there we have the goals, effectiveness and efficiency. And as far as quantum resistance schemes go, they also need to be built on mathematics that isn't vulnerable to the power of a quantum computer. For example, RSA, which we'll recap later, is built on the fact that a classical computer cannot find the prime factors of a very large number. It's vulnerable because quantum computers can do this. So, quantum resistance schemes can't be based on integer factorization. And this was actually one of the explicit stipulations in the rules for the NIST contest.

Who are NIST? Well, the US Federal Institute devoted to standardization. And with a description like that, probably the federal institute with the wildest office parties. If you've seen that Veritassian video on standard substances, that's a NIST warehouse that Derek is exploring. As well as standardizing weights, calibrations, and substances, they also standardize encryption schemes such as AES, which is widely used for online traffic. Why? Well, with dozens of available encryption schemes, standardization is essential. Firstly, for the parameters, it's important that every country uses the same version so that encrypting in one location means you can decrypt in another. And also, left to individual choice, parameters may reveal unintended security flaws. For an example of that, see my video with James Grime on how Enigma was broken. Secondly, the standardization process involves rigorous testing. Bruce Schneijider, cryptographer and apparent Squid enthusiast, puts it like this. Anyone can create an algorithm they can't break. What is hard is creating an algorithm no one else can break, even after years of analysis. RSA and AES are such algorithms, but they will fall to quantum computers, an event sometimes called Qday. So, the pressure is on to hunt for new algorithms no one can break, even with a powerful quantum computer.

To find these, NIST opened the floor to academics to submit their own schemes and attempt to break each others. Thus begins the race. There's a lot at stake. Rivers, Shamir, and Adelman of RSA are household names if you live in a house of computer scientists. So, comparable fame awaits the winners of the race, which is to say broadly unknown and underappreciated by the general public. Submissions had to follow a few normal rules, but also that if the scheme is patented, they had to agree to license the scheme to NIST. We'll return to that later. And for me, an essential unwritten rule is give your scheme a good name. Cuz you know what they say about me, it's lagger. I just love a good acronym. Falcon, Jopantis, Ramstake. All punchy and memorable. Others, h not so much.

30th of November 2017 was the deadline for submissions. Of the 82 schemes submitted, 69 were deemed by NIST to fit the criteria. Round one began about a month later with the posting of all algorithms for cryptographers to attempt to break. This is how vulnerabilities are found. Attack and exploit. And if an algorithm still survives, well, it's probably pretty secure. As we'll soon see, round one was a bloodbath. Think about that first scene in the Hunger Games where most contestants fall in the opening battle.

Now, I can't go into detail about all of these schemes, but let me first just give you an overview of the types and introduce some key players. Once we whittle down the pool of schemes, we'll explore them all in greater detail. So, we can see that there are three categories. Each scheme either provides digital signatures, public key encryption, that's like RSA, or key encapsulation like the Diffy Helmet exchange. As we said earlier, none of these can be based on integer factorization.

And that's why one of my favorite submissions didn't actually make it to round one, which is Daniel J. Bernstein's PQR RSA. They submitted a signature and a chem scheme, which were essentially RSA, but with the parameters inflated so enormous that even quantum computers would struggle to factoriize them in reasonable time. The catch, it involves terabytes of data and encryption took over a 100 hours. It was mostly a theoretical exercise to show that if all else fails, some encryption system is available. It was apparently a satirical submission, but don't discount Bernstein and colleagues just yet because they did enter the race for real.

It's actually worth taking a moment to introduce Bernstein as an important player in this story. Not only does he have an impressive academic record, placing top 10 in the infamous Putnham competition at age 16 and going on to develop many encryption schemes still in use today, he also has a proven history of fighting for transparency. It might shock you to learn that as recently as the early '90s, the US considered encryption software as a munition, a relic of the postworld war II era when encryption was used almost entirely by the military. But as time went by, commercial encryption became a necessity and thus civilians needed to share encryption software. But because of its status as a munition to publish his encryption code as a PhD student, Bernstein was required to register as an arms dealer. How crazy is that? As a result, Bernstein, backed by the Electronic Frontier Foundation, filed a lawsuit against the US Department of State and won, leading to scratching encryption schemes off the munitions list with First Amendment rights applying to code as a type of freedom of expression. It was a landmark victory that loosened government control over encryption schemes. Bernstein is now a professor at the University of Illinois at Chicago and co-developer of three of these non- satirical encryption schemes. He even apparently coined the term postquantum cryptography. So, he's one to watch. As to how he fares in the contest, you'll have to wait and see.

Now, these schemes are colorcoded based on their security assumption. Integer factorization cannot be used. So, what forms the basis of these schemes? Essentially, it has to be a mathematical problem that is known to be hard to solve by computer. Let me give you a very quick overview of the four main flavors.

Now, these schemes in green are the codebased schemes making use of error correcting codes. I made a trilogy of videos about my favorite error correcting code, the gole code. But in [music] brief, it's a system where if messages are sent through a noisy channel such that errors can occur, it can be repaired on the other side. For example, if you know that I'm going to either send you three zeros or three ones and you receive 0 1 0, you can correct that to three zeros. But if you don't have knowledge of the scheme, the system that we're using, correcting the message is known to be computationally very difficult.

In red is the multivariate polomial approach. This is based on the fact that if you have a polomial in many variables with coefficients from a set of size p working modulo p, it is incredibly difficult to find the roots. For example, working with three variables mod 7, what are the roots of this polomial? Your computer might be able to find them in this case, but it's a computationally hard problem with many variables and a big modulus.

The two blue schemes are hashbased built on hash functions. These are one-way functions which scramble data in a deterministic way but such that the output is extremely unpredictable. We can see that slight changes in the input cause massive variations in the output. For this reason, given some hash data, it's computationally very hard to find the input.

Last, but certainly not least, the most popular approach in yellow, the latis-based schemes. Many of these are based on something called the learning with errors problem. If I give you a system of linear equations, you know how to solve them, and computers can do this very quickly. However, if I add some random noise to the output and now ask for the solution that gets us closest, the problem is now extremely difficult. And don't worry if any of that was vague. I just wanted to give you an overview. We'll go much deeper into the important stuff later, but what they all have in common is some kind of chaos, some unpredictability.

As we'll see shortly, quantum computers can break integer factorization. Because that can be reinterpreted as a problem with hidden patterns. with randomness. With this unpredictability, attacks resort to brute force, at which point a quantum computer doesn't gain a practical edge. So these are the security assumptions, the hard maths problems at the foundation. The real challenge is to use them as part of an encryption scheme in a way that's secure and efficient. For example, hash functions shred data into unrecognizable swill, which sounds like effective encryption. But how would decryption work?

Here is where we meet another big player, Ginta Ding. He published one of the first encryption schemes based on the learning with errors problem back in 2012 and also literally wrote the book on multivariate public key encryption. He like Bernstein co-developed three schemes in the contest. However, it's worth noting that he patented some concepts of LWE based encryption. While he agreed to license his schemes to NIST upon entering the contest, it was unclear as to whether his patent applied to other Lattisbased schemes. I'm not here to speak on whether it's right or wrong to patent your ideas, but issues may arise.

Back in 2016, Google tried CECPQ1, a hybrid scheme combining New Hope with pre-quantum algorithm X25519 as part of a 2-year experiment. But they abruptly ended the trial after only 4 months, citing that they didn't want to promote this as the deacto standard. However, Daniel Bernstein alleges that Ginta Ding, whose LWE patent might apply to New Hope, contacted Google and asked them for money. This could be why Google stopped its trial. Now, I don't know for certain as I'm not a patent lawyer and I don't know if the patent really does apply to New Hope [music] and I don't know if Gintai Ding contacted Google as Bernstein claimed. Anyway, I'm not going to get bogged down with the legal minutia, but file this away for later. And that sets the stage for the contest.

Except if you're wondering about these schemes in purple, they are miscellaneous schemes utilizing unique approaches. For example, guess again uses the mathematics of random walks. About a month after the deadline, NIST posted these 69 schemes and cryptographers scrambled to find vulnerabilities. In the words of Anakin Skywalker, >> now this is pod racing. >> No, not that one. >> This is where the fun begins. And let me just say that while we're going to have a lot of fun exploring this contest, I have nothing but the utmost respect for every participant. Even if their submission didn't make it, every contribution is a valuable step in granting us all security in a postquantum world. So, let's dive in.

On the day that round one began, Loren Panny, a cryptographer with the world's most efficient academic record on the website, posted an attack against the scheme, Guess Again. Pany's paper titled Guess Once, described a way to decrypt cipher text without knowing the private key, breaking the algorithm. The Guess Again team allegedly ignored the attack, republishing their work and prompting Penny to write, "Guess what?" which provided a proof refuting the security claims that Loren Pani a collaborator of Bernstein's didn't actually co-author any of these proposed schemes. Instead, this one-man algorithm killer took shots at other schemes also publishing attacks against RBB and joining an attack against Rakos.

Now, while these schemes were broken by a non-participant, most schemes were attacked by fellow competitors eager to crush opposition and thus validate their own entry. Yong Wang of RLCE attacked McNe, but that attack proved to be invalid. However, Philip Gabri, co-author of five schemes, did make a successful attack, which ultimately finished it off.

Now, one of Gabri's schemes was Big Quake, whose authors seemed intent on making a seismic impact on the contest. Two of its authors, Ela Kubra and Jean-Pierre Tilish together with colleague Matthew Len attacked RLCE for certain parameters, but they were far from done. Kubra attacked Dags with BigQu comrade Alisa Blli and while the authors of Dags responded with a parameter change, it wasn't enough to see them into the second round. Jean-Pierre Tilich of BigQu wasn't done either. With his name on four schemes, all with great names by the way. It seemed he was eager to sniff out flaws in his rivals. Again with Matthew Leen, he took down Eden K, whose author congratulated them on the attack and withdrew. So that's nice. And similarly, Tish partnered with Debris Alazard to attack ranks, whose authors also respectfully bowed out of the contest.

Now, another dangerous competitor was Ward Berlin of the scheme Luov. His colleague Frederick Vicaran working with Bhut Castrich took shots at Gyopantis while also suggesting how to modify their scheme to nullify the attack. But when Ward Berins joined in, however, they brought down Gapantis for good. Berlin then turned to Walnut making an attack that Walnut defended. I agree that Walnut is not broken yet, but I don't think the attack is insignificant either. Fighting words.

There was also some disagreement regarding the security claims. Now while walnuts deflected an attack from researcher Simon Blackburn and another attack from both Blackburn and Berlin's more attacks piled on from Simon Philip MS and Anton Menshot and it seems that after a valiant defense walnut was finally cracked. Compact LWE was crushed when four researchers made an attack on the morning of the 5th of January. And if that wasn't enough that very afternoon three more researchers extended it. The authors of Compact adjusted the parameters to avoid the attack until Yanbin Pan's attack defeated the new version and finished it off for good.

Wrapping up the skirmish of the opening round, Leo Dukar, another heavy hitter with their name on four schemes, took aim at DRS. There was some initial confusion about their algorithm until he partnered with Yang Yu to publish an attack. Ron Steinfeld of Titanium attacked CFPKM, knocking it out of the contest. And meanwhile, Bo Yunyang, one of the authors of Rainbow and Ghee, attacked SRTPI, whose authors immediately withdrew.

Now, speaking of these two, they are projects of Ginta Ding. And unfortunately, his third scheme, the Ding key exchange, like many, didn't make it into the second round. Even though it wasn't broken, it didn't quite appease the NIST overlords presiding over the contest. Why? Well, there are many reasons why NIST might decide to discount an entry. Take Big Quake. After its authors like Jean-Pierre Tilich valiantly slayed many other schemes to carve a path towards victory, NIST decided not to take it into the second round, citing a worse key size than other schemes. Really sad to see that one go. Fortunately, Tish wasn't out of the contest as Bike made it through as well as Lake and Locker joining forces with Euraboros to form a new scheme called Rolo. This happened when schemes based on similar mathematics might as well combine strengths into one scheme. Entru Encrypt combined with Entrew HRSS Chem to form the much simpler named Entrew while Round Five and Hillif merged into round five. Sadly, all of these algorithms were dropped by NIST at the end of round one. Maybe they found vulnerabilities. Or maybe these were just far less efficient than other options. Maybe NIST just didn't like the acronyms. Unlike in later rounds, NIST didn't publicly offer specific reasons for individual schemes.

So, with those gone, we're down to just 26. And this is where I want to pause the contest to explore a little about the computational challenges that these schemes attempt to address. How is it even possible to create an encryption scheme that's immune to quantum attacks? We'll answer this question in two stages. First, I want to show you how quantum computers work [music] and what their strengths are. Secondly, after a quick break to check in on round two, we'll show how quantum computers break RSA. That's essential context for showing the limitations of quantum computers and why there is scope to create quantum resistant encryption.

In this video, we're not going to go too deep into the mechanics of how classical or quantum computers work, just their abilities in the abstract. So, here we go. A classical computer is built on binary digits or bits. They are in a zero state or a one state. Let's now say I'm terrible at arithmetic and I want to find out the double of all numbers from 0 to 7. Then I can write a short script to say take the starting number, double it and spit out the answer. Eight computations, eight concrete answers.

In contrast, a quantum computer is built from cubits. A cubit also has a value of zero or one, except its value isn't determined until we measure it. You can think of a classical bit as a coin on heads or on tails. It is what it is. A cubit is like a spinning coin with heads or tails, but its value is only determined when we look at it. By applying certain operations, we can alter the probability that it will fall on one side or the other. So, say I randomize the coin in a way that makes each face 50/50, but then I subject it to a magnetic field, which can [music] say make heads a bit more likely. The coin is still in an undetermined state, [music] but when I catch it, the result is locked.

How is this physically possible? Well, again, we won't worry too much about the mechanics here, but one way to do this is with an electron. This has a property called spin, which can be in any direction. But if I apply a spin up or spin down gate, it will return spin up or spin down. And the act of measuring a certain spin will force the electron into that spin. Now, for example, I can subject this electron to a magnetic field to make its spin sideways. And now, if I put a gate around it to ask whether it is spin up or spin [music] down, it will force it into one of these two outcomes with equal probability. Once it has been measured, its spin [music] is known and certain. Now, I can apply a different magnetic field to make it more likely to be spin up, but sometimes it won't be. the process is still probabilistic.

Another way to picture this, inspired by the many worlds interpretation, is that there are effectively infinitely many universes, [music] but in each when the gate is applied, half of them will give a spin up result and half a spin down. I don't know which universe I'm in, but by making a measurement, I find out. In the scenario where we skew the probabilities, the proportion of universes with spin up will be 75%. All these states exist in their own universe. We just don't know which one we're in until we measure and learn. However you choose to think about it, this is how particles behave and therefore how cubits behave. So we can, as David Murman said, shut up and calculate.

The standard way to denote the outcomes for one cubit looks like this. Then we associate each outcome with a probability. So in our earlier example, we might have a 3/4 chance of observing one. Now, we actually don't write the outcomes like this. We standardize them so that the coefficients of each outcome square to the probability of observing that outcome. Why do we do that? Well, these coefficients encode some physical properties of that cubit that I won't get into. I'll just add that these numbers can also be complex numbers. Taking their magnitude and squaring still gets us the probability. One nice byproduct of this standard way is that you can visualize these as a vector of length one being as the length is calculated by the root of the sum of the squares which must be one due to the fact that all these probabilities must sum to one.

With a two cubit system, there are four possible options and we write the state as a linear combination of these where again the square of the coefficient gives the probability of observing that outcome. And we can extend this to as many cubits as we like.

So let's do some calculations with a 4 cubit quantum computer. Earlier when doubling the integers from 0 to 7, I had to do eight separate calculations. [music] But with a quantum computer, I can initialize my cubits so that there is a 1/8 chance of each of these integers being observed. So I've done one computation and I've calculated all eight answers. However, the cubits are now in a superp position of all of these answers. So if I look through the window of this black box, I will only see one of the answers. And after measurement, the superp position collapses and my cubits are set in that specific state. If you prefer the many worlds approach, there are effectively infinitely many universes and in each the computer runs one multiply by two operation. It's only when I make an observation, I find out which universe I'm in. Either way, I only get one answer. So, to find out the doubles of all eight numbers, I'm going to have to run at least eight separate computations.

There's a very natural question to ask here. What the is the point of this? And I want this question to drive home something crucial we must realize about quantum computers. They can't solve every problem. They can't even improve upon classical computers for many problems. They are very good at only specific things. A common description of quantum computers is that they perform all calculations simultaneously, thus speeding up computations. But this is misleading. They only ever return one answer. So where might they be useful?

Well, let's play a very contrived game. I'm thinking of an integer and I'll tell you that it's square is less than 10. And I'll tell you when you're looking at the correct square. For this example, let's assume you know enough to realize it has to be between minus3 and 3, but you need a computer to verify the solution. Also, from now on, instead of representing things in binary, let's just assume I have enough bits to represent the necessary integers. So, with a classical computer, we feed in the inputs, we get the outputs, and now let's say I have an am I right function. Feed the outputs into this and it returns true or false. After seven distinct computations, we know the possibilities for my number.

Now, how might a quantum computer tackle this? Well, let's set things up in the same way. And we'll also have a quantum am I right function that we'll get back to shortly. Now, a clever thing we can do is entangle two sets of cubits. So, I've got one set of cubits, and there's a 1/8 chance that I'll observe each of these outcomes, and I'll entangle them with another set of cubits. There are many ways to write this but today I'll just concatenate them. The typical example of this is in two pair produced electrons. They must have opposite spins but it's random as to which spin each has. Each has a likelihood if I measure it of being spin up. But once one is measured and its spin is made certain, the others will be made certain even without measuring. How do we exploit this property? Well, we have two sets of entangled cubits all set to the same thing. But now we square the second set. This forms an input set and an output set. Now here's the clever part. I'm going to measure the output set. Notice that there are only four outcomes, all equally likely. So let's say I measure a nine there. Now I know that my first set of cubits are definitely either set to minus3 or three without even having to look. How do we use this? Well, let's bring this quantum am I right function back into play. Classical am I right returns true or false on the correct output. Quantum am I right has the effect of boosting the probability of the correct output. So let's say I apply it on my output set and say it inflates the probability of output four to 80%. Now when I measure, I'm most likely going to measure four. And now due to entanglement, I'm guaranteed to measure one of the two correct inputs. In the many worlds approach, all eight situations were equally likely. But then the am I right function boosted the probability of output four. After measuring, we were probably going to be in an input two or input minus2 universe. I can observe one of the correct inputs with certainty.

To summarize, in the classical case, that was seven independent computations, each followed by an am I right check. In the quantum case, it was one computation and then one am I right application. Unfortunately, I wasn't guaranteed to get a correct answer. it was only an 80% chance of observing a correct input. But if I repeated this, say four times, it's very unlikely that my process will yield a false positive. Now, this might not sound like a big deal, but what if there were a thousand options for my number? The classical computer would run a thousand computations, while the quantum computer might still only get away with just doing a few. Change this from a toy I'm thinking of a number problem into a real life I have a password problem and you might start seeing the power of quantum computers.

But and it's the biggest butt that I can think to discuss without getting my video demonetized. There is [music] a huge problem that I glossed over this am I right function that magically inflates the probability for the correct output. How do we actually make this? Most of the time we can't. This function is fictitious except for a few exceptional circumstances. I introduced it to give you a feeling for why quantum computers are considered powerful. But in reality, it turns out that making these is extraordinarily difficult, may be impossible in many cases. One powerful am I right function is called a diffuser which is used as part of Grover's algorithm to speed up brute force computations to an extraordinary degree. But even this doesn't help with many cryptographic applications where the numbers used are so large that even that saving doesn't grant a practical advantage. It also has the downside of requiring us to know the correct answer in advance. Not great for passwordguing applications.

Now, as a thank you for their generous support, I've given an outline of Grover's algorithm in the extended cut of this video available to my patrons. This video took me 5 months to make. If it bombs, I'll have basically made no money through YouTube in that time. So, it is only thanks to their support that I can take risks on videos like this. See below if you'd like to support me, too.

As fortune would have it or misfortune depending on how you look at it. Another powerful am I right function is called a quantum furier transform which is used as part of Shaw's algorithm to crack RSA and other current cryptographic standards. So let's dive into that. But first we'll take a quick break from the mathematics to check in on the NIST race now that we have a rough idea what these proposed schemes need to defeat.

If you recall, we were left with these 26 schemes and the list was posted on the 30th of January 2019. And by now you know what that means. >> Get a cannon ready. >> On the 14th of April, Vadim Lubeski and Peter Schwabber, colleagues on three schemes, both Crystal's Schemes and Falcon took aim at Qesla, breaking one iteration and forcing the authors to remove certain parameter sets. Unfortunately, NIST found that this made Q Tesla inferior to Dithium and Falcon, requiring signatures about 15 times as long and running two to five times slower. This was actually the only attack made by Peter Schwabber, whose name is on an impressive seven schemes still in the race. He's another big name in the field, a scientific director of the Maxplank Institute of Security and Privacy. And while he's a prolific co-author of schemes in the contest, it appears he was content to keep his head down and play less aggressively than other cryptographers in the race.

On the 5th of August, Daniel Kales and Greg Zavaruka of the unique picnic algorithm published an attack against MQDS claiming a method to forge signatures. Their response was very civil, acknowledging the attack and vowing to tweak the parameters to avoid it. This worked, but NIST felt that this made the algorithm far less efficient than other signature schemes like Picnic and Stinks Plus, so they dropped it.

Martin Alrech of New Hope and NTS Chem had previously made an attack against round five, which the authors defended by tweaking the parameters. However, in doing so, NIST felt that the complexity and inefficiency concerns meant that rival Latisbased schemes performed better. So, round two submitted in round one, adapted into round five for round two, didn't make it into round three. NIST would later compare New Hope to Kyber, deeming it similar, but ultimately inferior. So, unfortunately, they didn't select it for round three.

Now, previously, three authors of the combined Rolo scheme pointed out a mistake in the security claims of lack, while on the 16th of September, Mike Hamburg, the Three Bears solo author, points out that encryption isn't constant time. With this, NIST believed that further study was needed and despite good performance, it wasn't selected. And speaking of three bears, perhaps the most tragic fate befell this scheme. It didn't suffer any attacks, but NIST abandoned it, stating that it received too little community attention. I guess severe attacks are bad. Nobody attacking is also bad. Somewhere in between would have been just right.

A roller wasn't finished. And a great little story happens here when on the 1st of May 2020, a paper on algebraic attacks was published that could be applied to both Rolo and RQC. While both algorithms could be adjusted, NIST felt that the analysis needs more time to mature and encouraged further study, but decided not to keep them for round three. My favorite thing about this is that one of the authors of that paper was Jean-Pierre Tilish. Remember him, the big Quake guy who butchered many algorithms in the first round? Well, he's one of the co-authors of Rolo. So keen was he to launch attacks that he helped bring down one of his own schemes. And you've got to respect it. Weaknesses must be found, even if it's in your own work. Now, the only scheme by Tish in the race is bike.

Finally, several of our familiar faces return with Ward Berlin's Luov suffering an attack from Gentai Ding, who still had Rainbow in the race. N said that there is value in the science but that it is premature to trust the construction not arms dealer Daniel Bernstein whose three schemes still survive raised issues with leader crypt which was subsequently finished off with an attack from these four cryptographers and while we're discussing Bernstein one of his schemes is the classic mccles which absorbed the NTS chem scheme keeping the classic mccleles name appreciated the willingness for both teams to work together and that's it for round two.

Now only 15 schemes remain. And here NIST decided to split them into two brackets. The first track schemes that NIST preferred and the alternates schemes kept on as backups. [music] At this point, we'll also split the schemes into the chem and signature categories since they serve different purposes and thus are not really competing against each other.

In the signature race, NIST expressed a strong preference for Dithium and Falcon, stating their intention to standardize at most one of these. Also on the first track is Rainbow, granting a lifeline to Gintai Ding. Meanwhile, Gems, Picnic, and Sphinx Plus were relegated to the alternates bracket.

For the chem schemes, it's a three-way jewel between Kyber, Saber, and Entrew with NIST again stating that they are likely to standardize just one of these. Classic Mccle is also kept on the first track, granting a lifeline to Daniel Bernstein. Bike, Froto, HQ, Entry Prime, and Psych were all kept as alternates.

Now, what was the thinking here? Well, you'll notice that all the leading candidates in both races use the Latis model. NIST reasons that selecting schemes which are all based on the security assumptions behind latises carries risk. So they kept rainbow and the classic mccles in the first track as schemes built on different mathematics. As for why they picked those, well gems was considered similar to rainbow but with higher encryption time. Picnic and psych were kept for their unique approaches but NIST wanted to see more study on their security. Bike and Entry Prime remain promising, but security concerns needed addressing, and HQC is similar with performance weaker than bikes. Finally, NIST said that it is prioritizing schemes with wide use cases. Standardizing Frodo Chem isn't a priority because while it is very secure, it is also very slow, limiting its use. And I mean, I could have told you that he did get the ring to Mordor, but boy did he take his time. It's a similar story with Syncs Plus, which is considered an extremely conservative candidate. Even though its security is very strong, it again is slow with very big signatures, only good for high security applications where performance can be sacrificed. And so after a year and a half of competition, round two ended with seven finalists and eight backups.

And it's here I want to circle back to this security assumption and build towards answering that question. What makes a scheme resistant to quantum attacks? We've seen how quantum computers work, but what exactly can or can't be achieved with their power? To explore why systems are quantum resistant, we need to look at a quantum vulnerable system. So, in this next section, we'll recap how RSA actually works and how exactly it is broken.

As you might know, I'm not the first on YouTube to explore this. Minute Physics and Veritassium both made excellent videos on the topic. I'm doing my own version here for three reasons. First, I love the mathematics and I want to share how I think about it. Secondly, they make simplifications like when Minute Physics skips the quantum FIA transform, which Veritassium unfortunately parrots and I'm oversimplifying a touch here. I'm simplifying a little here. And third, they both skip the quantum for transform, which is honestly the whole reason why a quantum computer can solve integer factorization and it's the most beautiful part of the whole thing.

RSA is an asymmetric encryption scheme. So remember this is where we all have our own public key which encrypts and private key which decrypts. Now my public key is actually a pair of numbers. and my private key is kept secret. Say yellow Alex wants to message me with a letter Y which in ASI is 89. Using my public key, he does 89 to the^ of 127 modulo 527.

Now a very quick aside about modular arithmetic in case you're unfamiliar. This means we take the remainder after dividing. So 6 + 8 modulo 12 is 2 because 14 / 12 is 1 remainder 2. You can also think of it as stripping away chunks of 12 until you get a number less than 12. We're going to use some shortcuts in this video. 51 + 23 can be done by taking the numbers modulo 12 before adding. We get the same answer because whether we delete the chunks of 12 before or after adding, it doesn't matter. More powerful is that because multiplication is repeated addition, we can use this shortcut when we multiply. The long way to do say 51 * 89 is to calculate it and then mod 12 it. But the quick way is to mod 12 the numbers first and then get the answer. These efficiency savings really matter because yellow Alex's computer now has to do this without shortcuts. That is an extremely large number around 250 digits long. But since we're taking it mod 527, we can execute the exponents one at a time. 89 squared is this and then mod 527 it to get 89 cubed just times it by another copy of 89 and then mod 527 it so the numbers stay in a comfortable range transforming one giant calculation into lots of tiny ones which computers are very fast at in the end his message is transformed into the cipher text of 387 gibberish to any third party a bad actor might attempt to brute force messages here trying various numbers until they get a match. But in the real RSA, these numbers are so enormous that this won't work.

Now to decrypt, I take the cipher text to the power of my secret key, which I'll now reveal as 223 modulo 527, and I recover 89, which I transcribe as the letter Y. And again, brute forcing my private key won't work because in reality, there are simply too many options. It feels magical, but like all magic tricks, there's more going on under the surface to explain how it's done.

Now, because this video is mostly about quantum computers and the new quantum resistance algorithms, I'm going to gloss over a few steps here, but I'll include some notes in the description if you want to get the full details. As we do this, I'll pick a specific example for you to visualize, but build up the general theory at the same time.

Now RSA works because if we pick any number n as a modulus then there is a magic power r. It's magic because no matter what number x we start with x to the magic power is 1 mod n. For example take 36. Its magic power is 6. And don't worry about how we calculate it. We'll get to that shortly. 7 11 25 all to the power of 6 are 1 mod 36. The only catch is that x and n can't share factors. Numbers sharing factors can never be 1 mod n.

Now notice that once we've found the magic power, then actually any multiple of it will be magic. Because if I do x ^ of say r * k, this is x to the r to the k i 1 to the k i. 1 mod n. For example, 7 to the^ of 54, a multiple of 6, will still reduce to 1 mod 36. Of course, one to the power of anything is just one. So, I can delete these exponents here. RSA harnesses the power of this because if we have a power that gets me to one, then multiplying one more time returns the original number. X to the RK + 1 is X to the KR * X, which is 1 * X, which is X or specifically 7 55 will reduce to 7 mod 36. What's the big deal? Well, crucially, 55 can be split into two [music] factors. five and 11. So 7 to the^

Of 11 to the power of five will return seven. And because 7 to the power of 11 is unrecognizable, but it's recoverable with five, 7 to the power of 11 is scrambled. And then to the power of five unscrambles. Make 11 my public key for scrambling, five my private key for unscrambling. And hey presto, I have invented RSA.

There are two problems though. First is that if a bad actor discovered the magic power, they break the encryption. So if they discover six in this example, then they can keep taking multiples of 6 + 1 until they get a power that is a multiple of 11, my public key. Divide and they have my private key. So this magic power needs to be hard to calculate.

Secondly, this number x or seven as I've used here, you'll recall is the message and it must not share factors with the modulus. Otherwise, it doesn't work. Lots of numbers share factors with 36 and that limits which messages we can send. So, we need to be smart about which modulus we choose. Which numbers don't share factors with many other numbers? Well, your first instinct is probably primes. 37 doesn't share factors with anything except its multiples. And that's great except the magic power of a prime is always one less than it. That's Fermat's little theorem, which we won't prove here as I fear the proof would go on for too long. The same excuse Fermat gave for not proving it.

So which numbers to choose? Pause now if you want to consider. The answer is just to take the product of two primes. So a number like 35 that balances both issues. There aren't that many numbers sharing factors with 35. And also the magic power is difficult to calculate. In fact, it's the lowest common multiple of one less than each of its factors. Easy to calculate if we know the factors, but impossible to calculate without them.

"Big deal," I'll just factorize your modulus to break your silly little encryption scheme. 527 is actually 7 * 31. Pause now if you want to calculate his private key, but I know how. The so-called magic power is 240. Take multiples of that plus one until we find a multiple of 127. Then divide. Your private key is 223. And congratulations. You've broken our make-believe really severely awful version of RSA.

The real, sincerely amazing version of RSA uses numbers that are hundreds of digits long. As it turns out, factorizing large numbers is extremely difficult, intractable for classical computers. This is the advantage quantum computers have here. They can factorize very large numbers.

So, let's bring quantum computers back into play to see how Shor's algorithm works, which breaks RSA and other systems like AES, Advanced Encryption Standard, which I won't discuss here because it committed the cardinal sin of adopting an unforgivably boring name.

So, recall that we set N to be the product of two primes P and Q and that RSA breaks when we find those factors. First, we're actually going to turn this into an easier problem. We're going to find a number that shares a factor with N, another number that has P or Q as a factor. Let me convince you that if we can do that, then we can factorize N easily. For example, factorizing a number like this is hard. Your only recourse is to run a very slow factoring algorithm. But if I tell you that 9,211 shares a factor with it, then the very fast Euclidean algorithm will tell you the common factor. I explored this in more detail in my DVD screensaver video, but we essentially repeatedly divide. We stop when we reach a zero remainder and return the last nonzero remainder. This tells us that 61 is a factor of this and now we can divide to find the second factor. So the strategy is now to find a second number with a common factor and we do it with Shor's algorithm.

Shor's algorithm works by choosing a specific number X, then finding a power R such that X to the R is 1 mod N. To be clear, this number R may not be the magic power of N. For example, earlier we saw that 36 has magic power 6. So X^6 will be 1 mod 36 for every X. But for some numbers, different powers work as well. Shor's will just output a power that works for our choice of X. Then it turns that into a number sharing factors with N and we can proceed from there. We'll explore this step first, which uses a trick you learned in high school.

If X to the R is 1 mod N, well, remember that means that X to the R, after deleting a whole bunch of N's, is one, which we can rearrange into this. We're also going to assume that R is the smallest power that has this property. And for now, we'll assume that R is even. And now to invoke that high school trick. Remember the whole difference of two squares thing. So we can rearrange this into (X to the R/2 - 1) * (X to the R/2 + 1). This doesn't seem like a game changer, but trust me, it's so powerful that frankly, it should be nerfed in the next number theoretic patch. Why? Well, it's equal to K. Now, N is built from two primes P and Q. And K will be built from primes as well. Prime factorizations are unique. So among these two numbers are the same primes. And that means P and Q must appear in one or the other, or both.

Now, note that Case A is actually impossible because if this were true, that means that it's equal to something * N. And with some rearranging, we see that this is 1 mod N, and that's a contradiction because we assumed that R is the smallest power with this property. Now, Case C is uninteresting to us because that will deliver a number that just is a multiple of N, and that actually doesn't help us. But Case B is the jackpot because we found a number that shares a factor with it. So, we can execute Euclid's algorithm on these.

What if we find R, but then it isn't even? Well, then we can just choose a different base X and run through the process we're about to discuss and hope that this time we get an even R. So we can continue with this process here. So it's about time we discuss how these magic powers are actually found. And this is where we need a quantum computer because when N is hundreds of digits long, like it is in RSA, R has the potential to be hundreds of digits long as well. For a classical computer, there's no shortcut. You just have to keep taking powers over and over for longer than the age of the universe until you get one.

How does a quantum computer handle this? Let's say we're trying to factorize 1,387. Let's say that we have 20 qubits. Now remember that means that they are capable of representing 2^20 different numbers, and we initialize the qubits so that each one is equally likely to be measured. So that means they all have a coefficient of the square root of 1 / 2^20. And since that's the coefficient of all of them, I'll just factor that out. Now, these will be our input qubits. And like we did earlier, we'll entangle these with some output qubits. This will be the output of doing 2 to the power of the input modulo 1387. And now remember, somewhere during this process, there will be a magic power R with 2 to the power of R being 1 mod 1387, i.e., another input R also with an output of 1. So we've got 0, 1, 2, 3, and so on, and eventually R, which gives an output of one. And from there, the next input will give an output of two, and then four, and so on. In other words, this is periodic. And again, as we discussed earlier, 2R will also give an output of one. And hopefully, you can see this will continue every R steps until at some point we reach 2^20. There's going to be a lot going on here, so just remember we want R.

So at this stage, we measure the second register. There are actually only possibilities for what this will be, all equally likely. Let's say, for example, that we observe an 8 in the second register. Well, now our superposition collapses into this because without looking, we know our input qubits must be set to either 3R + 3, 2R + 3, and so on. Now, these are all equally likely with this probability because this whole sum has 2^20 entries and there are R rows, which means there's 2^20 / R options for the inputs that give 8 as an output. And so 1 / (R / 2^20) is the probability of each one being measured.

Now, what next? Well, measuring now would be useless. Let's say I do take a measurement on the first register and I get 9237. What does that tell me? I guess maybe that 3 + a bunch of Rs is equal to 9237. But there are a lot of options there, and now I've lost my superposition. Now you might think, "Okay, just restart the process from the beginning to get more information." But if I start again and measure the second register, maybe this time I observe a 661, a totally different output. A reading on the input register now won't tell me anything useful. Like say I measure a 16373. Well, that's saying that this initial value A plus a bunch of periods is this. But I don't even know what the initial value is here. For all I know, it's an enormous number. I'm not really getting enough useful information to infer the value of R.

So let's go back a couple of steps to when I had this superposition after measuring the second register and seeing 8. We want R. And I know that these states are equally spaced by R. So I need a way of measuring not one state, but measuring the distance between them. So how do I do that? Well, I am free to do operations to these qubits. I could times them all by two or add five to them all. Or I could do something really useful like applying a Quantum Fourier Transform. Now, this is technical. So first, I'll give you the overview and then we'll dive into how it works.

So the Quantum Fourier Transform swaps period for frequency. Let's draw our periodic superposition like this, all the way up to 2^20. All spikes are the same height because they're just as likely to be measured. The period is this distance R, and what I'm calling frequency is the number of spikes. And here there are 2^20 / R spikes. The Quantum Fourier Transform switches these, returning a new superposition with R spikes at multiples of 2 / R. And you might question why this solves anything. We still have a periodic function. But crucially, it's the same periodic function regardless of our initial measurement on the second register. Whether we measure an 8, a 661, a 32, after the Quantum Fourier Transform, we are looking at this function. So after measuring this, we can get multiple readings on the same function and infer the period.

So let's execute this a few times to get a few readings on this function. Let's say that I get this on my first measurement. So this number is one of those spikes, which means it must be a multiple of 2 / R. And dividing by 2^20, I see that K1 / R is approximately a half. So that tells me that this measurement is almost exactly halfway down this axis. And that tells me that R must be a multiple of two, since we've observed the spike exactly halfway down. The next few measurements tell me even more. So, we've observed a spike a sixth along and 29th along, and R must be a common multiple of all of these. So, we infer that R is equal to 18. We can double-check it if you'd like. If you do 2^18 modulo 1387, you will return 1. Now, we can do that high school trick to find 513. And since it isn't a multiple of 1387, it must share a factor. So applying Euclid's algorithm, we find a common factor of 19. Dividing gets us the other factor. Phew. So that's how we get there.

But how on earth does this Quantum Fourier Transform work that allows us to get these measurements? How can we take a function with one period and transform it into a function with a different period? Now, fair warning, this is a tricky bit of math, but stick with me because it involves some gorgeous visuals that build to a really intuitive picture. If you're unfamiliar with complex numbers, don't worry. It's only a couple of simple facts that we need. If you are familiar, stick around for a reminder. Anyway, for our purposes, complex numbers are points in this plane. An awesome property they have is that if you multiply two of them, the resulting number sits in a specific place. Its distance to the origin is found by multiplying the distances of the others to the origin. So here we have distance two, distance three. The result has distance six. Also, if we measure this angle from the positive x-axis and add them, we get the angle of the result.

Now, let's focus on the circle of radius 1. Multiplying two numbers on here will give us another number on the circle because distance 1 * distance 1 is distance 1. And if we take a number and square it, we double its angle. Cube it, we triple its angle, and so on. A root of unity is a number, say Z, whose nth power is 1. And that means that its angle theta is such that n * theta is 360. So theta is 360 / n. So the third roots of unity are here. The fourth roots here, fifth roots, and so on. It's all very pretty.

With this, we can actually define the Quantum Fourier Transform. And to do so, let's look at a very small example: factorizing the number 21. So we're going to attempt to factorize the number 21, which I'm sure some of you can do, but we need this very small example to understand how the Quantum Fourier Transform works. Same setup as earlier, but this time we have four qubits, and our output register, instead of doing 2 to the power of the input, will do 4 to the power of the input modulo 21. Why four? Honestly, because it produces a nice example. As it turns out, this is periodic with period 3, but we're not supposed to know that yet. That's what we're trying to find out.

Now we measure the second register and say we measure four. Now we are left with this superposition, all spaced three apart. And I must stress, because this is such a simple example, we have to imagine that this period of three is totally unknown to us. And remember, the idea is to measure the distance between these values. That's the period. And the Quantum Fourier Transform does this by swapping a function with five spikes distance three apart to a function with three spikes distance five apart.

So how does this work? Well, first, because we're working with four qubits, we'll work with Z, a 16th root of unity. The Quantum Fourier Transform gives us a new superposition. Let me first state what it is and then we'll explore what it means and why it works. So we start with the old superposition, which in general can be written like this, where each alpha i squared is the probability of measuring i. Now, the Quantum Fourier Transform gives us a new superposition, which I'll write like this, where beta i squared is now the new probability of measuring the number i. And here, a given beta sub K is defined to be the sum of all of the alphas, but where each is scaled by Z to the power of alpha's index times K. And for good measure, we times the whole thing by the square of 1 / 2^4.

Now take a deep breath, 'cause I know this looks horrendous, but it's simpler than it looks because remember, most of these alphas are zero. In our example, only those attached to 1, 4, 7, 10, and 13 are non-zero, and they are all the same: the square root of a fifth. So I can factor out that root fifth, write it as root 1 over 80, and I'm left with just this sum here. And to give us a sense of the purpose of this, let's take a peek at what these betas actually look like. If we calculate all the beta Ks in this case, find their magnitudes and square them, we obtain the probability of measuring each value K. Put them on a graph, and we see that we are incredibly likely to roll a 0, 5, or 11. And why these numbers? Well, because we've turned our period 3 function into a period 5 function.

But something feels a bit off about this. Why 0, 5, and 11 when apparently this should be period 5? That's because I lied a little bit earlier. This original function didn't have five spikes distance three apart. It actually had 16 on three, or five and a third spikes. That's because if I measure a four, or a 16, I have five spikes. But if I measure a one, I actually have six spikes. So the average of those will be 16 on three. It'll make more sense in a moment. And remember, we obtain this graph regardless of what we measure in the second register. So if we do all of this, say measuring a 16 in the second register, our resulting superposition is still transformed into this, and likewise if we measure a one in the second register. So we can get multiple readings on the same graph with ease, and we will prove that it doesn't matter which one we observe right now as we dissect this specific case to understand exactly why it works.

And to do that, we essentially need to understand the size of beta K for various values of K. We expect it to be large when K is a multiple of 16 on 3, because that's where we see those big spikes. And since we're claiming it doesn't matter what we measure in the second register, let's write what the betas look like for each possible measurement. So these are the betas if we measure a 1, 4, or 16 in the second register. And we'll take their magnitude to see what they look like. Well, lucky for us, the magnitude of a product is the product of the magnitudes. And on these lower two, we'll extract a Z to the power of K. And that will reduce all of these exponents by 1K. Actually, it's a Z to the power of 2K that I wanted to take out for this bottom one. But it doesn't matter, 'cause the point is the magnitude of a Z to the something is one, because it's still a distance one away from the origin. So we can basically just cross that out and ignore it.

So now we notice we're basically looking at the same sum in each case. And that's why it doesn't matter what we measure in the second register. Don't worry about the fact that there's an extra term in this top one. We'll see in a moment that won't matter. So I'm actually going to get rid of these bottom two now because to understand when beta K is large, we just need to analyze this sum. So let's now look in the complex plane at what these powers of Z look like. Recall that Z is a 16th of the way around the circle. Z cubed is at 3/16. Z to the 6 is at 6/16, and so on. So this is what the K=1 case looks like. What is the magnitude of their sum? Well, complex numbers add like vectors. So given that they are roughly evenly spread around the circle, there will be a lot of cancellation, meaning their sum will be close to the origin, i.e., the magnitude of their sum is low.

Now let's look at the K=2 case. To get our hands on this, we just take every Z and double its angle. Again, we see that they are spread out quite a lot around the circle. So their sum is close to the origin. It has low magnitude. That's the same story for the K=3 and K=4 case. But watch what happens next. Taking one more power. When K=5, we see them start to bunch up on one side of the circle, meaning that when we add them, the sum will run away quite far. The magnitude suddenly spikes at five. And at six, it still isn't bad either. Notice that the period of this is actually 5.33. So that's why we get the spike at five, as these K's are integers. The next spike will be at 10.66, which is closest to 11. And as we run the K's forward, we see that at K=11, we get another big spike.

So why is it that it runs away at multiples of 5.33? Well, I'm sure you realize now that the best possible outcome is if all these points bunch together and are actually in the same place. So they all run away from the origin in the same direction. Any deviation and their collective sprint will be inefficient. But since the first one is locked in place at one, the best option is when they are all sitting at one. And when K is 16/3, that inflates the exponent to a multiple of 16. So it's clear now when K is 16/3 or multiples thereof, these are all multiples of 16. Therefore, they're all one. And therefore, the sum has magnitude five, as large as it can possibly be.

Now this diagram is actually really satisfying when we let K take any real value rather than just an integer. So this dot represents the sum of the Z powers, and we can see that as K grows, the sum gets stuck around the origin with low magnitude, and then suddenly they all align and the sum flies off. We can plot the curve that their sum follows, and we see that it spends a lot of time wandering around the origin, only flying off here. It's so cool. I spent hours watching these dots go around. To make things even clearer, we can graph the magnitude of the sum against K. So this graph is now tracking this distance, and we can see this characteristic Fourier interference pattern. This curve, by the way, is given by this polar function. It was quite tricky to derive. Feel free to have a go at it yourself.

Now, because we actually only have integer inputs, there is a bit of jank when we go back to the discrete setting. But for large enough numbers of qubits, we have enough resolution to make the correct inferences. That's why when deciding how many qubits to use, we usually overshoot by quite a lot. Recall that N was 21. A good benchmark is to use enough qubits to represent more than N squared states. So 21 squared is 441. So we would use 9 qubits. This has the effect of confining the noise around the peaks. So now that if I roll 10 observations from this distribution, here are the results. Because these represent fractions of 512, we can see that they are really close to 1/3 and 2/3, indicating a period of 3, which, if you recall, was the whole point of this, even though we already knew and we had to pretend that we didn't know it, but that's how it's done.

For completeness, recall that we need this period to be even to execute that difference of two squares trick and complete the factorization. So, in practice, we would need to repeat this whole process with a different base, say two. This time, to check your understanding, I'll just tell you that these are our observations after the Quantum Fourier Transform. Pause now to answer the following questions, because remember, in practice, this is the only information we get. Dividing by 512, we see a period of 6. Therefore, the distribution will have six peaks. And after the whole difference of two squares thing, we can get a common factor with 21 and therefore factorize it in the most complicated way possible. But now you know how the process works and how it can be applied to much larger numbers. And that's everything you need to understand Shor's algorithm in its entirety. I really didn't want to skip the Quantum Fourier Transform because not only is it very pretty, it is also the reason that quantum computers are able to factorize large integers, allowing us to take multiple readings on the same function, thereby inferring the period.

So now you know exactly how quantum computers can crack RSA and why current encryption schemes are vulnerable. Equally as important, you now know that quantum computers aren't a magical black box that can solve any problem. No, the only reason they can crack RSA is because of this periodicity exploitable by the Quantum Fourier Transform. If we choose a problem whose solution doesn't have periodicity, like the learning with errors problem, it is resistant to quantum attacks. And it's problems like that on which new schemes are based. And speaking of new encryption standards, it's about time we checked in on the contest.

First, let me close out this section with one remark. Quantum computers are real, right? So, why hasn't RSA been broken already? Well, current quantum computers don't have enough qubits. As we saw, a lot of qubits are required, but even that is assuming that they are all perfect. For physics reasons, qubits are actually imperfect and have a chance to decohere. That means that we need way more than the theoretical minimum to crack RSA. Expert estimations vary. Some say 4,000 qubits. For others, it's 10,000. But at time of recording, the most powerful gate-based quantum processors have around a thousand qubits. Still, quantum processes are getting more powerful all the time. So that's why it's really important that we switch now to quantum-resistant schemes.

And speaking of which, let's get back to the competition. Now that we've seen a quantum-vulnerable scheme, let's now examine a quantum-resistant scheme. And not just any, but one of the winners of the NIST race. Yes, it's time to start crowning champions. So, take a break now if you need it. But come straight back because victory is at hand for one of these schemes. First, we'll explore the signature race. If you recall, NIST promised to standardize at most one scheme out of Dithium and Falcon. Rainbow was kept as a finalist. These three were considered more conservative choices. NIST posted this list on the 22nd of July, 2020.

"Get a caner ready." Three cryptographers point out a security flaw in Sphinx Plus. Andreas Holing replies to say that this is only a mistake in the proof and not an attack. He pledges to fix the proof, but then silence until the 31st of October 2021 when they finally fixed it. Sydney Antonov later made an attack based on the underlying hash function, but Holing deflected by using a more secure one. Antonov still had questions though as of the 13th of June 2022.

As for Gems, Gintai Ding of the Rainbow Scheme published an attack that completely eliminated Gems from the competition, leaving Rainbow the only multivariate-based scheme in the race. It all looked promising, but then Ward Berlin of the scheme Synplus, published an attack against Rainbow, titled "Breaking Rainbow Takes a Weekend on a Laptop." The Rainbow team scrambled to fix the error, dismissing comments that the attack was devastating. But in the end, Rainbow was eliminated from the contest. And in a shocking twist, Sphinx Plus, the alternate, was selected by NIST for standardization.

"It's core only today. I don't have time for alternates from the top." The drama doesn't stop there, though. Because NIST decided to standardize Sphinx Plus, and Picnic has a similar profile and therefore similar use case to Sphinx Plus, NIST decided to drop Picnic from the contest. And now we'll wrap up this battle, which NIST said will have one winner. Well, further analysis revealed various strengths and shortcomings. Overall, Dithium is slightly faster at generating signatures, while Falcon's are slightly smaller. Given the various merits, NIST decided that both will be standardized. And that's the conclusion of the signature race. It saw Gentai Ding removed from the competition, at least for now. One of Daniel Bernstein's schemes standardized, winning the contest despite being initially built as an extremely conservative candidate. And remember Peter Schwabe, the quiet competitor who only submitted one attack in the whole thing? Well, he's the co-author of two of these winning schemes. So, a two-way duel with two winners and the surprise victory of an alternate.

And speaking of Sphinx Plus, it was selected despite its bigger signatures and slower [music] encryption times to add variety. As we said earlier, if a flaw is ever found in lattice-based encryption, it's good to have an alternative ready to go. For me, I'm just happy that all three schemes have fantastic, catchy, and memorable names. Now, among these three winners, NIST advocates that Dithium be the standard go-to signature scheme for most applications. And we'll explore how it works later. For now, I actually want to put the spotlight on Sphinx Plus, the heroic alternate, because this is actually my personal favorite scheme out of all the candidates. The way it works is kind of bonkers. And it was actually learning about this specific system that motivated me to make this entire video. And I can't wait to share how it works. So let's dive into Sphinx Plus before exploring the outcome of the Chemra.

The basis for Sphinx Plus is hash functions. So we'll start with those and build up. Now, the fun of this construction is that each step is pretty simple, but it amounts to a sophisticated scheme. Each step will cause problems that the next step will solve, only to introduce more problems, and so on. And it's this seesaw of enigmas and eurekas that I love about this development. So allow me to explain, and I'll try not to make a hash of it.

A hash function essentially scrambles data irrevocably. The first way it scrambles data is that no matter what you put into it, whether it's a single digit or the complete works of Borbachi, the output will always be the same length. And secondly, the outputs are chaotic. Change a single bit of the input and the output is drastically different. These ideas combine into the notion that these [music] are one-way functions. Once you hash, you cannot unhash. There are technical terms for these notions that I'll provide here for the completionists. Feel free to pause and read, but for the most part, just think of it as a one-way, fixed-length scramble.

One application of hash functions is in password verification. So when you make a password, hash it and save that. And now anyone with access to the server can't unhash it to recover your password. But it does mean that when you type in the correct password, it gets hashed and compared against the hash value. And if the hash value is the same, it's extremely likely that you've entered the correct password. Now, I'm not going to cover hash functions in any more detail here. We're just going to use them. Hopefully, you can see that the outputs of a hash function like SHA 256 are incredibly sensitive to the input and trust that to our knowledge, the ones we use have all of the desired resistances. If you really want more detail, see the link below to a great video by Red Blob Blob. They show all of the steps.

The point remains, how do we turn this one-wayness into an encryption scheme? We can't use it to encrypt a message because then we can't decrypt. But remember, Sphinx Plus is a signature scheme. This has nothing to do with scrambling our message. The point is to tag the message with some additional information, a signature, which the recipient can use to verify that it was sent by me. As a first attempt, imagine I generate a random number. That's my signature. Then I hash it and make that public. Now, when the recipient gets the message, they can then hash my signature and compare it to my public key. Because of the one-wayness, a bad actor can't forge a signature because it's not possible for them to unhash my public key. But under this scheme, I am able to simply intercept the message, take the valid signature, and pass on my own message. I'd still be convinced it came from the correct place. Yeah, well, of course you would. The point is though, this isn't a secure scheme. How do we make a secure one?

Welcome to the world of hash-based cryptography. The idea is to make the signatures dependent on the sender and dependent on the message. Now, one of the earliest solutions came from the legendary Leslie Lamport. As a Turing Award winner, he ranks among fellow computer science giants like the RSA of RSA, Diffie and Hellman of the Diffie-Hellman Exchange, and his collaborator Donald Knuth. And yes, [music] that is how you pronounce it.

"I figure you got only five letters in the name. You might as well use them all." Among other things, Knuth invented the TeX typesetting system. And if you've ever wondered where the "la" in LaTeX comes from, here's your answer. And yes, that's how I pronounce it. Lamport's solution is pretty nifty, but as we'll soon see, terrible in practice. It's worth noting that this was proposed way back in 1979, and hash-based cryptography remained more or less a theoretical exercise until recent years. Yet another example of pure theory finding application decades later.

Let's go much smaller in scale as an example, confining ourselves to an 8-bit hash function that destroys information in a similar way to something like SHA 256. So first, I take my message and apply the hash function. Then I prepare my secret keys. Now, for the remainder of this entire section, I'm going to follow the convention of some computer scientists and call these secret keys because the common abbreviation in the literature is SK, while PK is used for public key. And you heard me correctly, secret keys plural, because I generate 16 different ones and then I hash them into 16 public keys. So, the hash of this is this, the hash of this is this, and so on. So, we're sticking with the idea that I send you some secret keys, and then you hash them and check them against my public keys. As a forged signature would hash into something else and fail verification.

The clever part here is that I only share some of my secret keys based on the message hash. So, I bunch the secret keys into a zero group and a one group, and then I index them from 1 to 8. Now, I go through my message hash. If there is a zero, I share a secret key from the zero group. And likewise for a one. And for the nth bit along, I share the nth key in the group. This entire string is now my signature. Eight secret keys, all eight bits long. Now the recipient hashes every key in the signature. Then they hash the message using the message hash as a guide for which public keys to compare. Because hash functions are one-way, only I could have made the secret keys that hash into these public keys. Now, if a bad actor intercepts the message and signature and tries to replace the message with their own but keeping the signature, it won't work because their message hash will be different somewhere. So, the recipient will be comparing this to the wrong public key and verification would fail. A forgery can only occur if the message had the same hash output. But that can't happen in practice.

There is a problem now though, because impostors now know half of my secret keys. If I reuse this system, more information is revealed. And after just 10 signatures, 99.9% of my secret keys are now public knowledge. Even revealing half of your secret keys is risky. So that's why this is called a one-time scheme. We generate it all, use it once, and then throw it away.

With full-scale SHA 256, the message is hashed into a 256-bit string. So, I need 512 secret keys and then hash them all into public keys. I generate signatures in the exact same way, but I have to go through all 256 bits. Verification works the same way, too. Hashing every key and comparing them to the public key. But this means generating 32 kilobytes and publishing 16 kilobytes of data. And another problem is that my signatures are very long. A 256-bit string is sent for each of the 256 bits, which is 8 kilobytes. Now, all this might not sound like a huge amount of data, but at the scale of millions of messages, it's incredibly costly.

Fortunately, there's an immediate way to mitigate one of the issues. Instead of going bit by bit and sharing a key every time, what if I group the bits together and go chunk by chunk? Let's say I stick with a full-scale 256-bit example. But let's say I split it into 8-bit chunks, of which there will be 32. Instead of assigning a secret key to every bit, I assign a secret key to every chunk. Now, bit by bit, I needed secret keys for a zero and a one. But an 8-bit chunk has the potential to represent any number from 0 to 255. The hashes are the public keys. So like before, I publish all of them. And then the recipient takes my signature, hashes each of the 32 secret keys, and uses the chunked message hash to determine which public keys to compare.

Taking stock, we now only need 256 public keys as opposed to 512, and our signature is 32 keys long instead of 256. Because I hash and chunk up my message, obtaining random subsets, this system is known as uh, luckily it's pronounced "HORSE," so I can keep my video monetized. But the downside, we can still only use this once, as I'm leaking a lot of information about an eighth of my secret keys every time. But we can solve that problem by combining this idea with the Lamport idea. In Lamport, remember we had a whole zero group and a whole one group. Well, why not do that with HORSE? Instead of one secret key for each number from 0 to 255, let's have a whole zero group, a whole one group, a whole two group, and so on, up to a whole 255 group, each containing 32 indexed keys, one for each of the 32 chunks. Now, hash them all to create a whole bunch of public keys. I sign like I did with the Lamport signature. If the 8-bit chunk represents the number K, I choose a key from the K group. And if it's the nth chunk along, I select the nth key in the group. So here, chunk one is a 237. I select key one from the 237 group. Chunk two is a 174. So I select key two from the 174 group, and so on. The verifier, I'm sure you realize by now, is going to hash the message, split it into chunks, hash each key in the signature, and then use the message hash as a guide for which public keys to compare. And we've solved the one-time problem. I only revealed 32 out of the over 8,000 secret keys that I generated, a 0.4% of them. So, I can probably reuse this system a few times before regenerating the keys. Hence why we call it a few-times scheme.

The catastrophic downside of this though is that I now have over 8,000 secret keys, 256 kilobytes of data. And not only do I need to generate all these, I have to publish 256 kilobytes of public keys. That's the seesaw trade-off. We have a few-times scheme with smaller signatures but with massive public key sizes. Now we can tweak the parameters of this. For example, if I make the chunks smaller, i.e., four bits, then I need fewer public keys, but the signatures will be larger, and vice versa. You can sort of adjust this to meet your requirements, but it will never be scalable. Once we get into the millions of messages, we'll have to publish gigabytes of public keys.

So, where do we go from here? Well, there are two natural ideas. Firstly, it would be nice if we could generate fewer keys altogether. Or it would be nice if we could generate all these keys, but we somehow reduce how much we need to publish. Both of these ideas actually bear fruit and both are implemented in Sphinx Plus. So this is where our development takes two separate paths. Let's first try the idea to generate fewer keys in total.

Now, this system of generating drastically fewer keys is so elegant that when researching this topic, I was furious I didn't think about it. Look at the problem. Masses of randomly generated keys. There is a way of generating just one key for each index. Can you spot it? Pause now to think. The principle is that we randomly generate one key for each index, and that's now the zero group. Now just hash them all to generate keys for the one group. And then hash them again to make the two group, and so on, until the 255 group. Then hash them all one last time to make a set of public keys. Remember, I'm free to share these because you can't hash backwards to find any of my secret keys. And with only 32 public keys, I only need to publish a mere kilobyte of data.

To sign a message, I do exactly the same as before. Except the advantage here is that I don't even need to store all of these. I just take my base-level key and hash forward the appropriate number of times. So, this first one here represents the number 115. I take SK10 and hash it 115 times, sharing that secret key. Chunk 2 represents 44. So I take key 2 and hash it 44 times and share that, and repeat for every chunk. So that's my signature. And now the verifier takes this chunk 115. Subtracts it from 256, that's 141. Takes my secret key and hashes it 141 further times. So that in essence, the total number of hashes on this is 256. They can then check that this is equal to my public key for that chunk. Then they repeat for every chunk, hashing each of my secret keys until the total number of hashes is 256 and check them all against my public keys. It's a drastic saving.

But whenever we solve problems, we create some. The biggest problem is that we've actually opened up the potential for forgeries. Let's say that a bad actor intercepts the message and signature and wants to swap out the message content. Let's also say that the hash of their message is such that all of their chunks represent a binary number greater than or equal to mine. This is extremely unlikely, but they can apply small tweaks to their message until they get lucky. Now they can forge a signature simply by continuing the hash chain. So here my first chunk represents the number 115 and theirs represents 187. This secret key is the base-level key hashed 115 times. If they just hash it a further 72 times, they'll have the valid secret key for that chunk. Repeat this for all chunks and they've successfully forged a signature. And the verifier will be fooled because they will see this chunk, think that they have to hash forwards another 69 times, do so, and it will match up with my public key. So, they will think the message has come from me. Sneaky.

Now, there's a beautiful little trick we can do to prevent this. But I do need two more secret keys. No big deal. Simply generate two more and hash forwards like we did with the others. Now, I include a little packet of information in my message. I tell the recipient how many more total hashes they'll need to do. So here, as we said before, they need to do 141 more hashes. Here it's 212 more hashes, and repeat. And let's say, for example, that that all adds up to 4,045. Write that in binary and append it to the message. I then sign those two chunks using these two bonus keys that I generated. When the recipient verifies, they also count how many hashes they've done and then check that my secret keys are the correct ones for that total number of hashes. Now, the impostor has a problem. If he hashes forwards to make a forgery, that means the total number of remaining hashes will necessarily be lower, and he has to append that at the end of the message. But because this is lower, that means that the two bonus keys will be previous ones in the chain. So he can't sign those two extra numbers because while you can hash forwards, you cannot hash backwards. Ingenious. This is called a checksum.

Now remember, we only need to generate all of these base-level keys, and we have the entire scheme. But we can also save on the amount of keys I need to publish. Let's just concatenate all of the public keys together and hash them into a single public master key. Now when verifying, the recipient can also do the same, taking all of their hash values, putting them together, hashing, and checking against my master public key. This whole system is called a Wintz scheme, named after Robert Steven Wintz. I wish I could tell you more about him, but I couldn't find very much online. It's also called WOTS, Wintz's one-time signature, which reveals a second problem. Now, whenever I sign a message, I reveal one secret key, but I essentially give away all the secret keys after it. With the amount of information I reveal, I can't really use this more than once. Still, this is something we can employ for its advantages, and we'll be using it later. So, let me condense all of this down and use this to represent a single instance of what. Now, let's rewind and explore the other.

option. So, this is where our development takes two separate paths. Let's now try the idea to generate all the keys but reduce how much we need to publish. What if there were a way to generate a whole library of keys, millions if we needed to, but where I can represent all of them with just one public key?

Well, that would be great because here I have like 8,000 keys and I don't want to have to publish them all. Even in horse I had 256 keys. Now, we saw a hint of how to do this in Watts where we concatenate all the public keys and hash them into a master key, but that only works there because the verifier ends up with all of the public keys. So, they can execute that concatenate and hash process. In horse, they only end up getting their hands on a few of the public keys, and it's random as to which ones. So, we need a smarter way.

Let's just be clear on the problem here. So let's say I've got two secret keys. I only want to share one of them and I need to convince you that it belongs to me and I want to do it with only one public key. Previously we hashed both of them into public keys and when I shared this secret key you could compare it to its corresponding public key but I want to represent them both with just one public key.

Now you might think okay let's concatenate them and then hash that into the public key. That way, the public key here is derived from both of my secret keys. But if I only want to share one of these with you, there's no way that the verifier can take the other one to concatenate and hash to make the comparison because they don't have the other secret key.

The solution is surprisingly elegant. Pause if you want to think about it. What we do is hash each secret key, then concatenate those hashes and hash into a public key. Now if I share this secret key, I also share this hash here. Then the verifier can continue the chain to get the public key to make the comparison. And notice that this secret key is still safe because you can't hash backwards.

If I ever want to use this secret key, I share it and I also share this hash, which the verifier might already have from a previous message, but it doesn't matter. They can now complete the hash chain and make the comparison to the public key. So the punch line is that by extending my signature just a little bit I can now represent two things with one thing where previously it was one to one.

Now there's no reason why we can't do this again. Now I can represent four secret keys with two public keys. But what if I don't make these my public keys? Let's go one step further and create one public key that represents all four secret keys. Now, if I want to share this secret key, I also share this and this. The verifier can then hash hash hash and then compare it to my one and only public master key, which represents all four of these secret keys. And because this structure forms a tree, we call this a root. And as you've probably realized by now, we can make the tree as large as we like, which you can probably imagine, but because I hate myself in my own time, here's a big example with 16 secret keys.

Ignore all the numbers on these secret keys, I kind of run out of cards. But if I want to share, say, this secret key, then I also need to share this hash value and this one and this one and that one over there. And because that string of hash values proves that this is one of my secret keys, I call it a proof path or a Merkel proof because this whole structure here is called a Merkel tree. And the name is from Ralph Merkel who conceived it back in 1979 and is one of the first developers of public key cryptographers and in his PhD thesis described one of the first cryptographic hash functions.

Now, the amazing thing here is that we can scale this up. In full scale horse, we have 256 keys, and that only adds a few more layers to the tree and therefore only a few more packets in my signature. And just to really convince you of the security of this, if an impostor learned a Merkel proof, as long as I don't use this one specific secret key, they can't make use of that information. If they tried to smuggle in one of their own secret keys, they would get a bad hash value. Even when they use the known correct hash values in a Merkel proof verification would eventually fail at the root.

Let's now get rid of this and I'll show you how it's implemented in horse. So back to horse where we chunk up our message into 8 bit chunks. We can now represent all the secret keys with just one public master key. We do that by building a Merkel tree hashing until we obtain a root value and I sign the message exactly like before except whenever I share a secret key I also share the Merkel proof that will take that secret key to the root value. The verifier then takes each secret key and [music] executes the proof path. Therefore obtaining the value of root for each of the secret keys checking that yes we receive the root in every single case. That means that with one public key, I have represented all of my secret keys. And because this is horse with a Merkel tree, it is called ho.

Now host is used as part of sphinx. So make a mental note, but actually forget about it because this isn't sphinx, it's sphinx plus. And one of the main improvements sphinx plus makes to sphinx is that instead of ho, it uses something else. And blessedly, something that we've already seen. Let's bring this idea back where we had a whole zero group, a whole one group and so on with 32 keys in each group, one for each chunk of the message. Recall that to sign a message, when the chunk represents the number K, I select a key from the K group. And when it's the nth chunk along, I select the nth key from the group. And just like we did with host, building a Merkel tree to represent our secret keys here, we're going to build a Merkel tree for every index. So all secret keys for chunk one will build up to their own route. Same for the secret keys representing chunk two, three and so on up to 32.

So then with the secret key for each chunk, I also include the Merkel proof that produces this route here. So the verifier can follow the proof path to hash up to this route here and they can repeat that for every single one of these chunks. But because the verifier necessarily obtains all 32 of these roots, let's just concatenate all these roots together into one master public key. The verifier can then do the same to check their answer. So now I get to keep the advantage of only giving away 4% of my keys. So it can be used multiple times and I only have to publish one 256-bit key. The downside is now that my signatures are absolutely enormous, but you know what? Forget it. We can't have it all. Let's just build a really secure signature scheme intended for high security where we don't mind sacrificing signature generation and transfer time.

Now, because this is a whole collection of trees, we call it naturally [music] a forest or force. And this is used in Spinx Plus instead of host. So, are we done? Well, no, but we're getting close. The last problem is that yes, this can be used a few times, but we want a system where we can send millions and millions of messages. As it is, we'd have to regenerate the entire thing every time we'd given away too many secret keys and it became compromised. And that might require the computer to remember which keys have even been used. We call such a scheme stateful. That's bad. As Daniel Bernstein points out, getting computers to remember things is easy. But if you have for example virtual machines using the same system, counting can be problematic if not done carefully. Ideally, we want a stateless scheme that we can just generate once and run forever.

How do we do that? Well, sometimes the simplest solution is the best one. Let's just generate lots and lots and lots of different force schemes. So many that it's extremely unlikely that I'll ever reuse one. Let's say we generate, I don't know, 2 to the^ of 64 versions of this. And when I sign a message, I just pick one at random. Even if I sign a trillion messages, there's only a 0.0 0.54% chance of having used the same force twice, which by the way wouldn't even be that bad because each force is a few times scheme. The obvious problem here is how the heck am I going to do that? 2 ^ of 64 is an enormous number.

Well, two things come together beautifully to get around this. Before we cover those, just a quick note that I can collapse this whole iteration of force down and use this to represent the whole thing. So this is a single iteration of force with all the secret keys that hash up into a single master public key. So the first thing is that instead of randomly generating all of these different secret keys, I simply use a random number generator with a fixed seed to spit them all out. More precisely, a pseudo random function or PRF is a function that takes one input value called a seed and uses that to generate a string of values that appear to be random but are actually deterministic. If you've played Minecraft, you know the world is randomized, but if you start with the same seed, you get the same world. Or if you're old like me, you remember generating random maps from a starting seed on the classic Worms. These numbers here, for example, they are statistically random, but all I'm doing is squaring and then adding the next odd number, keeping the final two digits. This isn't good enough to use in practice, but there are some very clever PRFs out there.

So, with one starting seed value, I can generate as many secret keys as I like, and I only need to generate them when they are used. So I have my 2 ^ of 64 iterations of force. And let's say I want to use this one for a signature. So then my PRF uses my fixed seed value and the fact that it's the third one along to generate all the secret keys required for this version of force. And then the hash function can take it from there to generate the public key. So that means that all of these force copies are kind of ghostly. They're not really there. They only come into being when they are needed. It's a bit like No Man's Sky. All of the planets and systems are already predetermined, but they only come into being when you enter a specific system.

So, that sounds great. I can have as many force copies as I want because only one of them exists at a given time. But what is my master public key here? I don't want to have a different master public key for each version of Force. Because if I sign a million messages, I need to call a million of these force copies into being [music] and I have to share a public key for each one. That means publishing a whole lot of data. So I need a smarter way. Ideally, I'd like to have one public key to represent all of these. And if your instinct is, well, make them into a Merkel tree, you're on the right lines. But here we bump heads with the greatest enemy of computation, exponential growth. I would have to hash together 2 to the^ of 64 different public keys on the first layer and then 2 to the 63 on the next layer and so on until a total of about 2 to the^ of 65 computations. That's simply too many especially as the recipient would also have to do that to execute the Merkel proof. So this whole thing is useless.

So it can make like a tree and get out of here. Instead, we build a tree of trees. Stick with me. This is the final step. We're almost there. To see how this works, let's reduce the size of things and pretend that even a giant tree of 16 versions of force is too large. Fundamental problem here is that the root is dependent on all 16 leaf nodes. Instead, let's cut it off halfway and say that the root is only dependent on these four. Now to generate my master public key, I only need to build this very small tree here. And notice that we've also created four more mini trees whose [music] root is also only dependent on four leaf nodes. It's a subtle change that makes all the difference because now like I said, my master public key is now only dependent on these four nodes here. And if I choose to sign a message with say this copy of force, I need to share the Merkel proof to get to this node and then the Merkel proof to get to this node. That's 2 ^ of 5 + 2 ^ of 5 computations versus 2 ^ of 15 for the whole thing. An enormous saving. And because all of these force copies don't exist until they are needed, that means that only these two trees exist at any given time instead of calling the entire giant tree into being.

But what is going on in this gap? How do these Merkel proofs combine? Well, here's the really clever part. At all of these intermediate leaves, our PRF generates more secret keys. We want to keep them small and simple. So we just make them winterit signatures the type with the hash chains. So when we initialize this entire system for the first time, our PRF will generate four different versions of watts at each of these four nodes. The master keys of these watts versions are then hashed together to make the next nodes until we get to the master public key for the whole thing. And I make these because when I sign a message with a given force, I have to share the Merkel proof to get to this node here, which will be some hash value. And then I take the watts that was generated there, take its secret keys, and sign that node.

There's a lot going on here. So, let me be really clear on exactly how this works. I like to think of it like this. It's a bit of a dance. I sign my message with these secret keys here. And I need to convince the recipient that only I could have made those secret keys. So we do the whole force thing until they get to this node here. So they will be convinced that this is a consistent copy of force. But how do they know that it's my copy of force? Well, I need to convince them. I say, okay, follow the Merkel proof until you get to this node here. And this again will be a consistent process as long as I convince them that this node really is mine. And I convince them by signing it with this winter scheme that only I know until they get to this public key. And then to verify that this was my winter scheme. They follow this Merkel proof until they get to my one and only master public key. I'll be honest, it took me a while to really appreciate all the little things that are going on here. So feel free to replay the last 30 seconds or so until it really sinks in.

If a bad actor tried to imitate me, they would require their own version of force. And if they tried to smuggle that in, they would get a different hash value here. And that would mean that this would be a different hash value. And now they have a problem because even if I've sent messages with this whole system before and they know the correct secret keys to sign this message, they will not know the correct secret keys to sign this message. And that's bad for them because with the wrong secret keys, they will hash up to the wrong public key and then the corruption continues. They will end up with the wrong hash value here, which means when the recipient hashes, they will not get my master public key. And that explains why it's okay to use what's here, which remember is a one-time scheme, because it will only ever be used to sign this specific node, the outcome of the correct hashes down here. So, the secret keys that we share will only ever apply to this node here. When the bad actor tries to smuggle in their own thing, they will not have the correct secret keys for any other hash value that could appear here. And what's more, we can add way more layers to this to increase the number of force versions we can store here. For example, this mini tree, four copies of force, two layers deep. Maybe I want to have 256 copies of force, in which case I need a tree that's eight layers deep. And I duplicate that 256 times. And I have 6 plus. Listen carefully. Observe the trees within trees within trees. To represent 6 plus, I'm going to put the force copies vertically and then expand the tree horizontally because I need more space in that direction. So in one version of Sphinx Plus, we actually have 2 ^ of 56 different trees, each containing 2 ^ of 8 copies of force for 2 to the^ of 64 force copies in total. Each of [music] these trees will hash up into a Merkel tree with one root node which I then sign with a version of Winterets. We then bunch together 256 copies of Winterets and build a Merkel tree from there. Eventually arriving at a route which is then signed with a winter signature. And then 256 winter signatures are bunched together there to build another Merkel tree. And we repeat until we've done eight layers of this until the final Merkel tree, which will eventually get to my master public key. So that's kind of what the whole thing looks like. But remember, when I sign a message, I only need to call into being the parts that I actually need. So let's see what an entire signature looks like.

So we start by rolling a copy of force. Let's say I roll this one. And now this mini tree comes into being. And now remember a force signature looks like this where I share a secret key for each chunk of the message depending on which chunk along it is. And for each secret key I have to share the Merkel proof path. I then share a Merkel proof path to reach this node here. I then sign that node with this winterit signature which remember looks like a whole bunch of hashed forwards secret keys including the two checksum keys that allows the verifier to reach this public key and then I share the Merkel proof to get to the next node. I then sign that node with this winter scheme which as you remember is a bunch of hashed forward secret keys and I share the Merkel proof to reach the root of that tree and I repeat this until I've got a total of eight layers [music] and then I'll be signing with another winter scheme here which will build up with a final Merkel proof to my master public key. So, it's quite a big signature, but if you're keeping score, the recipient now has to do 2 ^ of 9 computations per layer for eight layers, which is 2 to the^ of 12. And that dwarfs the naive giant tree construction of 2 ^ of 65 computations. It's amazing. I absolutely adore this. Scaling things up to such a huge extent seems like a crazy idea, but so many clever little tricks come into play that make it feasible. And that's essentially Sphinx Plus. It's big, it's bulky, it's elegantly inelegant, but it's incredibly secure because these hash functions are incredibly secure because they crunch data so randomly. There are no periodic patterns for a quantum computer to exploit. Even Grover's algorithm doesn't help as the numbers involved are so incredibly huge. So say we wanted to break this. Well, that would require us to reverse a hash function. But with brute force, a classical computer would need to run around 2 to the power of 255 operations. And a quantum computer with Grover's algorithm would need to run around 2 to the 128. An enormous saving, but still a crazy number. And that's just to find one hash pre-image. Breaking Syncs Plus would require many more. Phew. And that's it for Syncs Plus. Thanks for sticking with me. I absolutely adore this system.

Now is the perfect time to take a break, but come back soon as we're about to dig into the outcome of the Chemra settling a three-way jewel between Kyber, Saber, and Entrew. [music] As a quick recap, as well as this three-way jewel, classic McCle was also a favored candidate with these five schemes kept on as alternates. Now, while Frodo Chem didn't suffer any attacks, NIST felt that because its performance was significantly slower than other candidates, it wasn't worth keeping around. If only there were a Samwise chem to carry it to the finish line. As for Andrew Prime, one of Daniel Bernstein at Al's projects, while one of his schemes, Syncs Plus, won the signature race, the Chemra is a bit more divisive. Not only did he suggest that NIST is changing the rules of the contest to ensure that Kyber wins, a statement that NIST refuted. He also decrieded NIST for getting embroiled in patent conflicts. This is where Ginta re-enters the picture. He patented one of the first LWE schemes and his license may extend to other schemes using the LWE problem as a security assumption like Kyber.

>> Do any of these patents actually have a risk of covering Kyber and if so then well somebody should do something about that where I mean the easy thing to do is use Entrew.

>> Entru and Entrew Prime are based on a different Latis problem and Entrew is open- source. In fact, Entry is already being used by Open SSH, a set of programs allowing for secure client server communications. So, Bernstein feels like NIST could have saved a lot of trouble by just using Entru and not having to worry about patents. Now, Entry Prime uses a different ring structure to the main three candidates. And it has been suggested that they are more vulnerable in ways that Entry Prime isn't. However, NIST didn't see it that way. Entry Prime unfortunately is dismissed from the contest.

Now, because all three of these finalists are Latisbased, there is some cause to select a non-Lattis scheme as a chem standard, just as Sphinx Plus was selected to balance out the signature race. All four of these are attractive options for different reasons. Classic MCle is old, tried and tested, very secure, but it has massive key sizes, so NIST doesn't anticipate widespread use. HQC is also very secure and has a quote acceptable performance, though not optimal. Bike boasts the fastest performance of all of these, but NIST has less confidence in the security claims. And Psych is the radical outlier with a totally different security assumption and remains attractive because it has tiny key and cipher text sizes, though being so different means analysis needs more time to mature. Given the various merits and drawbacks, NIST felt that a fourth round would help determine a winner. So, all four of these entered their own race. Meanwhile, NIST felt confident in the security of all three of these schemes and felt that the overall performance of any of these chems would be acceptable for general use applications. But it did promise to standardize at most one. And while they reneed on that promise in the signature race, they did select one winner here. Based on a minor advantage in performance, NIST selected Kyber for standardization. And I mean, let's be honest, Kyber had far and away the coolest name out of all of these. And you'll notice Peter Schwabber once again is a co-author of one of the winning schemes. But what about the patent issue? Well, NIST secured a license with Ginta Ding. He joined Team Crystals as a co-author of Kyber. So when it is standardized, it will be available for anyone to use. These schemes remained in the competition for a fourth round. But for now, since we know that Kyber is a winner, let's explore how it actually works. And in doing so, we'll see how Dithium works as well. The Matsia isn't significantly complicated, but it's ingenious how it all fits together. So, here we are. Two schemes from Team Crystals, both with just excellent names, assuring us that the authors have sufficient nerd credibility. Your data will be secure even when transferring to an alien planet. And that means it's safe for one of us to go down there. Why are you both looking at me? May I? Oh, come on. At least give me some pants. I actually had the pleasure of chatting with Peter Schwabber, who kindly gave up some of his time to answer some of my questions. You might notice that he's the only author on all three of the schemes currently standardized. So, if anyone can be called a winner of this contest, it's him. I'm delighted to say that when I asked him the most important question, were Kyber and Dithium named as such purely because of the nerdy references? His answer was yes.

Hyber and Dithium utilize lattis-based cryptography, one of the most popular postquantum approaches. Due to their many similarities, we'll cover both of them in this next section. Starting with latises. What are they? A latis is a regular collection of dots. Here we take two vectors and take every integer combination of them. If we change the initial two vectors, we change the latice. Though not always, as sometimes two different pairs of vectors will yield the same latice. These vectors are called a basis for the latice. Once you've defined the basis, you've defined the entire lice. We aren't confined to two dimensions either. Throw in a third vector that exists in a new dimension and we have a 3D latis. Throw in a fourth for a 4D latis and so on. All visualizations in this video will be confined to just two dimensions. Although Kyber and Dithium utilize a clever kind of lattice which are higher dimensional but still easy to represent in 2D. We'll get to that soon. First, let's examine how to navigate a lattice mathematically. Ready? Hit it. In 2D, our basis is two vectors and any latice point is a multiple of one plus a multiple of the other. So long as we know these two coefficients, we have a root to find our point. Now, a simple way to express this is as matrix multiplication.

>> What matrix? If you haven't worked with matrices before, don't panic. This matrix B is the basis. This vector R is the root. B * R equals this lattice point here. Multiplying a matrix by a column vector is easy. It just means three times the first column plus -2 * the second column. Multiplying a matrix by a row vector on the left means 1 * the first row plus 2 * the second row equals this row vector here. [music] It's not yet clear why this is useful yet, but file it away in your brain for now. Now, because computers, even very large ones, can only deal with finite levels of computation, we don't usually have a lattice that can go on forever. To limit it, we do the Pac-Man routine and say that if you disappear off the top, you reappear at the bottom. And same for left and right. We already know one way to do this. We take the numbers modulo Q for some modulus. Say Q equals 20. Now, if we wind up with a point outside this range, we do a mod Q to bring it back into this space. We're almost done with the setup. Just let me give you a few more useful matrix facts. The inverse of a matrix is a partner matrix which multiplies to make the identity matrix. The identity matrix functions like the number one. Anything times the identity is just itself. So, you can think of inverses like reciprocals of real numbers. All the matrices we'll look at today are invertible and in general computers can calculate them very easily. And while some things have analogies with the multiplication of numbers, something very different about matrix multiplication is that it generally isn't [music] commutative. That is to say, A* B is not B * A in general. However, matrix multiplication is associative. If I'm smashing three things together, I can execute the multiplications in any order. Let me just say that again. We can execute the multiplications in any order.

>> What? You don't think this is amazing?

>> Now, I know what you're thinking. Big whoop. Everyone knows this. Why are you even reminding us? Well, it's because this seemingly pedestrian fact is so powerful. It's actually the whole reason why we are able to use latises for cryptographic purposes. And now that we have the setup established, welcome to the world of latisbased cryptography. Let's start by imagining that there are two parties who want to establish a shared secret using matrices. Well, let's have a public matrix B and think of this as the scrambler. Like in RSA, we'll be working with the modulus Q= 31. I have a secret vector S. They have a secret vector R. Now I calculate B * S and they calculate R * B. Now these will be gibberish vectors that a bad actor can't understand. So we are free to transmit them to each other. I receive RB and multiply it by S on the right. They receive BS and multiply it by R on the left. By associativity, RBS is the same on both sides. So we both establish a shared number seven which never had to pass through the channel. With just a little more work we can sculpt this into a public key encryption scheme. So now say that this is my public key and also BS is part of my public key. They calculate RBS as normal but then they also calculate RBS plus M where M is some message number. Say their message is the number five. 12 is now their cipher text. They send me that and I find RBS as normal and subtract it from their RBS plus M. Therefore recovering their message number five. Deceptively simple. And that's because there is some deception going on here. These pesky inverses which are easy to compute. A bad actor can just calculate B inverse, smash it into BS which is public and they've obtained my secret key. The entire challenge of latisbased cryptography is to utilize all that's good about this while circumventing this problem.

One approach is to use the learning with errors problem. Remember when I brought that up like 2 hours ago? Essentially B * S will equal some new vector T. If I give you B and give you T and task you with finding S, that problem is equivalent to solving a system of linear equations. But if I add to BS a small vector E, it is now extremely difficult to find S given B and T intractable for classical computers. This is called an error vector. S is now difficult to learn. Hence learning with errors. Now before we use this to fix our encryption scheme, let me just take a quick detour to explore why this is so difficult for computers to solve. Well, in 2D things look like this. B * S is some lattice point. Then B S plus E is floating off grid somewhere. So if we only have B S + E and we want to find S, that's equivalent to finding this point here, the point that's closest to B S plus E. But in reality, we don't know all the latice points in advance. We only know the basis. So if I have a seemingly random point and ask for the closest lattice point, there are a great many options, especially when the numbers start getting huge and this is only in 2D. Extending to higher dimensions exacerbates the problem drastically. Imagine a small neighborhood around this point, say a disc of radius A. Then the region where we might want to hunt for latis points is on the order of a squ. But in 3D it's now a cubed because it's now a ball. In n dimensions it's on the order of a to the^ of n. And whenever the exponent of a space is increasing the numbers will get to crazy sizes. Hopefully this gives you some intuition for why the lwe problem is hard. For now let's use it to modify our scheme.

So all parties now agreed to add an error term to disguise their transmissions. And here are all the error terms that we need. So I actually send B S plus E so that a bad actor can't infer S even if they had B inverse. The sender adds an error term to RB so that a bad actor can't infer R. Now instead of doing R * BS they can only do R * BS plus E. And that will change their cipher text because instead of RBS plus M, they'll have this plus M. But we also mask that with our final error term. I now do the decryption dance, multiplying their disguised RB on the right by S, and then I subtract that from their cipher text, which should give me M. And in a shocking twist, by adding all of these random terms everywhere, I've ended up with the wrong message. Who would have thought? This happens because in the original case, the RBS terms cancel out, leaving M. But in this new case, the RBS terms do cancel out, which does leave M plus a bunch of crap. Now, there's an elegant way to solve this problem.

So, pause now if you want to think about it. But this is how Kyber works. It's this entire process plus a mechanism for making this crap negligible and thus allowing me to infer M. Here's how. We'll start by developing a system where our message is just a single bit zero or one. We'll scale things up later. The principle is we want to make m big and loud and make all this stuff small and negligible. For example, if all of this stuff added up to say 0.1, then this whole decret will clearly round to the value of the message. Unfortunately, everything here takes integer values. So how exactly do we pull this maneuver? So the first step is to spread out the possible values of m as far apart as possible. So in the universe of numbers modulo 31, the numbers run from 0 to 30. But instead of naming them like this, we're actually going to number them using negatives. This helps us to see which numbers have a high magnitude and which numbers are small. We can see here for example that 0 and 15 are as far apart as possible. So what we'll do with our message is multiply it by 15 before transmission. The second step is to make this as small as possible. So if we just agree to build all of these vectors out of numbers say from minus2 to two hopefully it'll all [music] be small. Say it all works out to be a number like three. That means our decrypt, which is m plus all of this rubbish, will look like either three or 18, which we can then round to either zero or 15, whichever is closer. And it's clear we'll get the right answer. As some viewers might have spotted that in setting up this example, I did build all of these vectors out of numbers between minus2 and 2. So let's see if this works. If I make m zero, do we get a good decrypt? Well, let's try it. By making m0ero, my cipher text becomes three. The recipient then takes the cipher text three and subtracts this term 9 to obtain minus 6. And then we round it either to zero or to 15. And in the context of modulo 31, it's 6 away from 0, but it is 10 away from 15. It's closer to zero, so we round it to zero. And that is the correct message. for completion. Let's see what happens if the sender wants to send the bit one. Well, they will make this 15 instead, which makes their cipher text 18. We receive their cipher text 18, subtract this term 9, which gives us 9. And then we round it either to zero or to 15, whichever is closer. Clearly, it is closer to 15. So, we interpret this as a 15, which we interpret as the bit one. It works. It's so cool. This is effectively how Kyber works. And I say effectively because just like in Sphinx Plus, every solution creates problems. And so far there are two that we need to solve. Firstly, is there a chance that all of these error terms stack up in a way that leads us to the wrong M? And secondly, how do we turn this into a scheme that can transmit more than one bit? Because while I like answering questions with one-word answers, not everyone is as autistic as I am.

Let's start by scaling things up to allow for longer messages, which involves increasing the dimension. Fortunately, Kyber and Dithium utilize a really nice way to visualize this scaling without increasing the size of the matrices. They use polomials. Now our latis is actually a grid of polomial expressions like this one spanned by two polomial vectors. And like we did earlier, we make sure the latice doesn't go on forever by taking the coefficients modulo q and we also limit the degree of the polomial. That's the highest power of x available. We do that by working in this structure here. Complicated ring theory aside, this is where we take the coefficients modulo q and this is where every copy of x to the^ of n is replaced with a -1 which puts a limit on the degree of these expressions. So if the powers get too big, we can clock them back down. As an example, let's take n= 4 and q= 5 and multiply these polomials just like you did in school. So start by multiplying out. Now these powers are too big. So we replace the x ^ 4s with minus1 and continue to simplify. And finally I'll take the coefficients modulo 5 which you can do earlier to make the simplification easier. So that's how polomial multiplication works in this structure here. And just another note about how this is different from the previous examples we were looking at. Earlier I had the two basis vectors and I could take say 3 * 1 + 2 * the other. Here we can actually take a polomial times one plus a polomial times the other. While we can sort of visualize this in 2D, do bear in mind that this is a higher dimensional latice because there are just more directions that these vectors can go in. We can take multiples of it or it can go in the x direction or the x² direction. It makes the whole thing quite complicated. For example, let's take Q= 17 and ask ourselves, is this vector a member of this latice? Well, it is if it's a polomial time this vector plus a polomial time the red vector. And proving that one way or the other can be very difficult. The latis has turned from a neatly ordered grid into a fish maze. It turns out in this case we can multiply the basis vectors like this where here I mean this polomial time the orange vector plus this polomial times the red vector. It's really not easy to see or find these and I'll leave it as an exercise if you want to check my polomial multiplication. So that we don't get lost. Let's now look at a quick example of kyber using this polomial structure. We'll stick with n= 4 and q= 17. And we'll use the same basis we had a moment ago. I'll choose a secret key and error vector with low coefficients and calculate bs plus e like before. And by the way, now that we're multiplying polomials, this takes a while to do by hand. Feel free to bust out a pen and paper and play along. But I'm going to cut to the simplified version of calculations like this most of the time. Now exactly like before the sender prepares their R and a couple of error terms with small coefficients. Now because these polinomials have at most four terms in this scheme we can send up to four bits. So say we wish to send 0110 which we transcribe as this polomial. And just like before we're going to inflate it by multiplying by 8. That's a number that's farthest from zero in the q= 17 space. And we do the exact same dance as before with the sender calculating these two and sending them. And again like before the recipient will take this one times it by s and then subtract it from the cipher text. And now we round every coefficient to either 0 or 8 whichever is closer. And we can see that turn by term we'll have 0880. In other words the message was 0110. So we have successfully decrypted the message. It's amazing.

Now what about that other problem? Is there a chance that this rounding fails? Let's explore that now because the answer sadly is yes. Especially when we start thinking about Kyber's efficiency. Full scale Kyber actually utilizes polomials with 256 coefficients with Q is 3329. If you crunch those numbers you see that the public key is 2.25 kilobyt six times larger than RSA. And similarly, the cipher text is big. To solve the big public key problem, we use a similar trick to sphinx plus. Instead of sharing all of B, I instead just share a 256-bit number which is used as the seed of a pseudo random function to randomly generate the coefficients of the basis polomials. And now our public key is just 800 bytes. As for the bulky cipher texts, efficiency matters here because at scale any reduction is worth it. Now the idea here is to compress the cipher text by reducing the number of bits we need to represent these numbers. To explore this, it's actually going to be easier to look at these transmissions where we represent the coefficients as numbers between 0 and 16. So let me just replace those now. Now remember that in practice all transmissions are done in binary and in our example these numbers can be anything from 0 to 16. So five bits are needed. But what if I could get away with just two bits? Well, with two bits, we only have four numbers to play with. 0 1 2 and 3. So if we scale down our range from 0 to 16 to 0 to 3, that means dividing by 4.25. So do that with all of our numbers and round to the nearest integer. We've compressed. Everything is representable in just two bits. This is transmitted and the recipient can then decompress by taking a warm bath and reading a good book. But we can decompress the cipher text by reversing this process, multiplying by 4.25 and rounding. In practice, full scale Kyber compresses to cut the size of cipher texts to about 2/3 of their original size. At the scale of millions of messages, that is a big saving. But you might have noticed that we don't recover the exact numbers. Is that a problem? Well, let's now use these to decrypt. When we use this decompressed RB plus E1, we actually obtain this. So we subtract that from the decompressed cipher text and obtain this which after rounding actually becomes 0101 and we don't recover the original message. Is this a problem? Yeah, but also no but also kind of yeah. Decryption isn't guaranteed but in the real implementation the likelihood of failure is extremely low. Because this is a toy example with a small Q, the error terms are relatively large. But inflate Q to over 3,000 and the error terms are comparatively tiny. That reduces the likelihood of a bad decrypt. Real life Kyber has a probability of failure of under 1 / 2 ^ 128. So it's a problem, but not really a problem. Kind of hold that thought.

So there we have it. This is how Kyber works as a public key encryption scheme. We aren't quite done though because this doesn't say PKE, it says Chem, which means it's a key encapsulation mechanism like the Dippy Helman exchange where we establish a shared secret to be used in a symmetric scheme. Well, it's pretty easy to convert this into a Chem. Just pick some random symmetric key, encrypt it, and send it over, right? Well, yeah, but because there's a small chance that decryption fails, we need a clever way of knowing if it fails. This is because, say I'm communicating with a bad actor who transmits a key to be used in our symmetric scheme. Decryption fails, but I don't know that. So, I go ahead and encrypt my message using the wrong key. The bad actor then decrypts my message, which will fail, and he then concludes that decryption failed. That's a problem because now the bad actor knows some cipher text for which my secret key fails to decrypt. And if the bad decrypt is only wrong in a few places, he might be able to target those failure points and start to deduce my secret key, especially if he repeats and chooses some other cipher text options to test whether decryption fails, gaining more information every time. This is called a chosen cipher text attack. The moral is that if decryption fails, I need to ensure that a bad actor does not gain any information. And we do this in two ways. First, we prevent people from having a choice over the symmetric key. That means they can't select specific ones to make inferences about my secret key. Second, if decryption fails, I need to know so that I don't

Use my bad decrypt and I just use a random key instead that doesn't reveal anything about my secret key. But without knowing the original message, how can I check whether decryption failed?

Welcome to the world of hash-based cryptography. Oh, wait. We already did that. But we do use hash functions. And it's getting out of hand because now there are two of them. First, one that we're all used to that hashes into 256 bits and a second one I'll call H+ that hashes into 512 bits.

The main idea is that the sender and I can verify whether we are looking at the same thing by hashing it and sharing the result. If we share our hash outputs and we're looking at the same thing, it's pretty much guaranteed that alpha and beta the inputs are the same and anyone who intercepts this transmission can't infer alpha and beta because you can't hash backwards.

More than that, we can establish a shared secret by splitting the output into two 256-bit strings. Then we compare the second one. If these halves are the same, then we should be pretty convinced that the first halves are the same. So, we can go ahead and use those as our symmetric key. The benefits here being that the key itself never needed to be transmitted. So, there's no chance of intercepting it. And also we don't have a choice over what the key is because it's the output of a hash function. So that mitigates some of the problems we discussed earlier when looking at chosen cipher text attacks.

So this is the main principle. Let's look at it in practice. So all the Kyber stuff is the same. I have a public key and secret key as usual. Now the sender dreams up a random string row and hashes it into a 512-bit string which we split in half. The second half L will be used in a moment but the first half K will become the symmetric key. So their goal is to share K with me without sending it directly.

Now if I knew row I could do H+ of row and generate K myself. So they encrypt row Kyber style using my public key and sending the cipher text. And crucially, all of these random elements like R and the error terms are generated using L as a seed for a pseudo-random function. So just make a mental note. These are dependent on L. That's going to be vital in just a few moments.

I then receive the cipher text and decrypt it Kyber style. Now this should be row, but for all I know, decryption has failed. So I'll just call it row prime for now. Now I hash it just like the sender did, which should yield K and L. But if row prime is not in fact row, then these K and L will be different. So I'll call them K prime and L prime for now.

Now, here's the really clever part. I know that if L prime is the same as L, it's pretty much guaranteed that K prime is the same as K. But I can check that L prime is the same as L by re-encrypting row using my own public key using L prime as a seed to generate all of the random elements. I then compare my cipher text to the cipher text that I received because the only way that they would be the same is if all of these random terms are the same. In other words, they were generated from the same seed. That means L prime is L and therefore K prime is K. And we can go ahead and use that as our symmetric key.

If when I compare I get a different cipher text, well that means that we generated that cipher text from different random terms, i.e. L prime is not L and therefore there's no way that K prime is going to be the same as K. This meant that decryption failed and I basically just roll a new random K, call it Kyber, I mean sorry K bar, the hash of my bad cipher text, which effectively randomizes it and proceed to use that as my symmetric key. In this case, the sender and I will have different keys. So, our symmetric encryption will fail. But because the sender had no choice over their symmetric key, and I responded with a random wrong symmetric key, they can't gain any information to infer my secret key.

This whole process of converting a PKE into a KEM with a built-in fail-safe is called a Fujisaki-Okamoto transform. And it's used in other schemes as well. And that's basically it for Kyber other than to stress that the real implementations utilize much larger numbers with different parameters being available for different security strengths at the cost of speed. As NIST stated, they advocate that Kyber be the go-to KEM moving forward as it is resistant to quantum attacks due to the nature of the learning with errors problem. It's like I said earlier, the introduction of randomness rather than exploiting hidden mathematical patterns thwarts quantum attacks because these lattices are so big and the search space so chaotic. A quantum computer pretty much resorts to brute force and so doesn't gain a practical advantage over a classical computer. I love this scheme. It's actually fairly straightforward, but with lots of clever little bits and pieces to combat the issues raised by the introduction of that randomness in the first place.

Very similar is Dilithium, which we'll get into now. Dilithium won't take long to understand as it's just a different application of the same structure as Kyber. The main difference is that Dilithium is a signature scheme. So remember the goal here isn't to scramble a message but where I display a public key and attach a signature to my message. The recipient can then use my public key to verify that I sent the message and also it should be that verification fails if I didn't generate the signature, i.e. someone else was posing as me. So I need to use my secrets to make something and then convince the recipients that only I could have made it. And that all needs to happen in a way that doesn't reveal my secret. It also needs to be dependent on the message. Otherwise, a bad actor could intercept my message and my legitimate signature and swap out the message content.

First, let's deal with that message dependence problem. Much like we did in Sphinx Plus, I can hash my message and share the hash value. The recipient can then hash my message to check if they get the same thing. But nothing about this is unique to me. So prior to hashing, I make some value zed that only I could have made and hash that together with the message. That is now my signature. I now send the message, the signature, and a way for the recipient to construct zed so that they can do the same hash and check to see they get the same signature.

I need something that only I can make. So I need to make it with my secret in a way that someone can check that it came from me by using my public information and in a way that doesn't reveal my secret. And here the simplest answer is the best one. I simply choose a lattice point zed and as a lattice point it is B * R for some vector R and then I send R. But to make it personal to me I just add my secret key S. The recipient can then multiply this by B and subtract B * S + E, both of which are in my public key. They will then be left with Z - E. Now remember E is a small error vector. So by making it negligible, they can do a similar rounding routine like we did in Kyber, allowing the recipient to infer zed.

If a bad actor tried to pose as me, they don't know my secret key. So their version of R + S would be some faulty vector V. Then when the recipient attempts to verify this, they would times it by B, subtract B * S + E, and they would just obtain some new lattice point, which would in all likelihood not round to zed. And that's a problem for the bad actor because then when this is used in here and then hashed, it will produce a completely different signature and verification would fail.

But there's a big problem with this. Can you spot it? It's subtle, but we've introduced a catastrophic fault in here. If the recipient gets zed, that means they can subtract zed - e, which will tell them what my error vector was. And that means they can subtract that from my public information, find B inverse, and thus obtain my secret key. Really, really bad.

So, how do we fix this? Well, the answer is in this rounding process. What if instead of z - e rounding to zed, I have z - e and z both round to the same thing, say zedbar and now use zedbar to construct my signature. Therefore, the recipient can still do this verification step, but they never actually obtain zed itself and therefore can't get their hands on my error vector e.

Now, what kind of rounding system can we implement where small adjustments don't affect the result? It's actually surprisingly simple, and we saw something like it not long ago. Remember that compression system where we shrank the total pool of coefficients? In that example, we took a space of 17 options to a space of 4 by dividing by 4.25. When we do a very similar thing here. Let's choose Q=31 as our modulus. That means our polynomials can have these numbers as coefficients. Then we choose an even factor of Q-1, say 6, and divide. Then we round to the nearest integer. We obtain what is called their high bits value. Another way to think about it is that we've rounded every number to the closest multiple of six. These numbers are closest to six, the first multiple of six, so their high bits is one. These numbers are closest to 12, the second multiple of six, so their high bits value is two, and so on.

Calculating the displacement from these multiples of six tells us what we call the low bits values. Low bits is basically a measure of how close a number is to having a different high bits value. Those with high magnitude low bits are close to the boundary. A small tweak may alter their high bits, whereas those with a low magnitude low bits can safely be tweaked without altering their high bits value. And that's good for us because we want a rounding system where both zed and a slightly tweaked zed both get rounded to the same thing. So if we specify that all the coefficients of zed have small low bits then both zed and zed - e will have the same high bits and that's what we use as our rounding system.

Now that's everything we need to run an example of Dilithium. So let's use a similar basis to earlier with the same secret key except this time we're working in the Q=31 setting. I choose R such that B * R = Z with a low bits value on all of its coefficients. In practice, this is just rerolled until we get one that works. I calculate R + S and send it. And on receiving, the recipient will multiply it by B, subtract B * S + E, and end up with this. Now, prior to sending the message, I round this to its high bits to create Zbar, and that hashes together with M to make the signature. And the recipient's vector will also round to the zedbar so they can put it together with the message and hash it to check it against my signature. And never did I have to give away the actual zed. Incredible.

If it looks like someone might be able to infer zed from this, just remember that actual Dilithium uses matrices which are orders of magnitude larger than these. And the number of options makes brute force intractable. And that is in essence Dilithium. To be clear, I've simplified this one a little because there are a lot of additional steps after this to make this a viable scheme. But in my opinion, going through all of those in meticulous detail doesn't lend any additional insight into how this thing actually works. If you're interested, I'll link below to the Dilithium paper by Schwabe et al. and a great video series by Alfred Menezes that has all of the details.

And that's it for Kyber and Dilithium, the two lattice-based post-quantum schemes now standardized for all to use for their encryption needs. And that's it for the big mathematical sections of the video. I really hope you enjoyed learning about how your data will be protected in the near future. We're going to finish the video with the conclusion of the NIST race. What transpired after these winners were announced. It's been a long journey and we're almost there. Stick with me.

So on the 13th of August 2024, Kyber, Dilithium, and Sphinx Plus were standardized and released for public use. Falcon has also won the contest, but it hasn't yet been standardized. Maybe I'll make a video on that when it is.

As for these schemes, three remain in the race to this day is what I was going to say, but this video took so long to make that actually the contest is over and we have definitive winners. So, backing up a little bit, when did these four become three? Well, unfortunately for SIKE, a catastrophic attack from Castryck and Decru on the 5th of August, 2022, further developed by Minem and Martindale, effectively destroyed its chances. While parameters could be tweaked to avoid the attacks, it worsened the performance to such an extent that the authors of SIKE declared that it should no longer be considered a viable candidate. So, we now have three code-based schemes left in the race. And I noticed that Classic McEliece had its advocates for standardization, citing its robust security. And this is where my video would have ended. But as recently as March 2025, NIST announced a conclusion. They actually disagreed with the assessment on Classic McEliece. They don't foresee widespread usage. And because standardization is a lot of work, it's only worth standardizing ones that people will actually use. Another complicating factor is that the ISO, a different standardization body, is considering standardizing Classic McEliece. NIST worried that if they both standardize it, their standards might be incompatible. So while they eliminated it from the contest, they did vow to reconsider standardizing it if there was a particular version that saw widespread use.

That just leaves a final showdown between BIKE and HQC. Remember BIKE is the final remaining submission of the likes of Jean-Pierre Tillich who helped eliminate so many other candidates. Now BIKE was praised by NIST as being a good complement to Kyber given that it is a code-based scheme with a different underlying security assumption. That could also be said for HQC though, but its public key sizes and cipher texts are larger, making it less attractive. The deciding factor came down to the decoding failure rate. Remember how in Kyber there was a small probability that decryption would fail. Well, that happens with some of these schemes because the main way to thwart quantum attacks is to introduce that randomness, that chaos that opens up the possibility that all the randomness stacks up in such a way that decryption actually fails. It's incredibly unlikely, but it can happen.

Now, BIKE's decoding failure rate has been unstable with differing estimates and requiring parameter tweaks all throughout the contest. Even as late as this fourth round, adjustments needed to be made to circumvent attacks. HQC's analysis has been comparatively stable and hasn't suffered an attack since 2020. And that's why NIST eventually selected HQC for standardization. And that's the end of the road for the NIST contest. Congratulations to all winners and all participants.

Now, like with Falcon, HQC is a winner, but it hasn't yet been standardized. Maybe I'll discuss it in detail in the future, especially as it's a code-based scheme, and that could make for an interesting video. But I want to conclude today with some comments inspired by SIKE, a sort of underdog scheme with its own unique approach. When they bowed out of the contest, they made a lovely statement of thanks to all participants in the race. Such efforts are the means by which progress in science is achieved. And I want to emphasize that, too. As I said earlier, I have nothing but respect for all participants. We've had some fun dramatizing the race, but while the process was framed as a competition, really it was a massive collaborative exercise. The point wasn't winning or losing. It was in filtering, growing our collective understanding, discovering the best options for the benefit of everyone.

And that circles back to the start of the video, imagining a world where nothing is safe online. We now have more confidence that we are prepared for Q-day because your data and online traffic might already be secured by one of these algorithms. Google Chrome is planning to switch to NIST's standardization of Kyber 768. ExpressVPN has already switched over and Cloudflare, that cybersecurity company behind all those bot checks, is also planning to change. We live in a time when technology seems to be rushing ahead faster than our means of preparation. AI is improving faster than we can regulate it. Climate change is happening and our preparation is not doing too great. Are we ready for another pandemic? Who knows? And so on. It's nice to hear a story where we have known about a threat and some heroic researchers have done the hard work for the benefit of all of us to actually get us ready well in advance. These schemes will hopefully protect us for decades to come as quantum technology improves. And also more importantly, they all have much better names. What's that? After standardization, Kyber is now known as ML-KEM. God damn it.

Thank you so much for watching. This has been the longest gap between videos I've ever had on my channel. So, thank you so much for your patience. It's been a long journey, but I hope you enjoyed the results. This was an insane amount of work. I love being a one-person creator, but months of research, writing over 25,000 words, designing all of these trading cards, days of filming, weeks of editing. I poured well over a thousand hours into this. I can't believe it's almost over. I'm filming this in the middle of May. I haven't even filmed the Kyber and Dilithium parts yet. It just won't end.

An enormous thank you to my patrons. Those on the highest tier will also receive personalized versions of these cryptography trading cards as a thank you for all of their support. Making huge projects like this one is super risky. I'm at the behest of the algorithm. It's taken so long to make that if it doesn't perform well, I'll take a financial hit. The support of my patrons is why I'm able to make videos like this one. Thank you so much. My next project will not be an epic like this one. This has been another proof under another roof. Until next time. I know. I know.