I sure do. They are going to let me actually do some code. I am pretty excited here. Let me pull this out here because I can hear too many people right now. But one of the cool things is that now it's the lunch break, but okay, they're telling me I'm good now. But we're going to do some AI stuff because I feel like AI is kind of the cool thing right now, but I feel like also a lot of people are kind of struggling with what it is that it actually does. I'm going to show you today what it actually does, and that it's actually really simple to get started. So I'm just going to open Visual Studio here and show you from scratch, like that's really fast. Then what I'm going to do is I'm going to open this project, and then we're going to get into a little bit about what we're going to do. I have just a couple of slides. Oh, look, see, look, the Visual Studio, I have the release candidate installed right now. So notice that it loads up pretty fast, everything's in there. Let me show you the application we're going to build, and then I'm going to show you how Visual Studio helps me out with that. Let me make my code a little bit bigger here. Let me go to, I think, 150 so you can see. Very good. So that's all set up. What I'm going to do now is I'm just going to run this, and I'm going to go all the way back to old school. This is like WinForms stuff. So this is a WinForms project just to show you that AI does not care where it runs. So I'm going to run this program and show you what it is that we're building, and I'm going to show you the two functions that we have to actually build in order to get this to work, and we're going to be building some Python. It's going to be really cool. So notice that this here is a program and I'm going to draw with my finger a number, and then we have to recognize it, but notice that nothing happens because I didn't write that bit yet and that's what we're going to do. So if we go to this old school WinForms application, you can see there is a predict and there is a load of model. Now, here's the thing about machine learning that's really cool. When you think of an AI model, literally all you have to think about is think of it as a function. I'll give you an example. When we write programs, we usually think of a problem and then we come up with a series of steps to solve the problem called an algorithm, and what we do is we marry an algorithm and the input and out comes some answers. Machine learning is a little bit different than that. By the way, I'm going to take your questions as well, so make sure you get those in there as well. Machine learning is a little bit different. What we do is we simply swap two things. Now, instead of getting the algorithm as part of the thing that goes from the left-hand side, the algorithm is a thing that comes out of the right. So what's happening is basically for machine learning, you're giving a bunch of answers and the right input, and then it learns the right thing to do on its own. By the way, in machine learning parlance, we call the thing coming in data, I think everyone calls it that, and the thing that comes out is a model, but you should think of it as a function, something that you execute, and then stuff happens in here. I'm not going to get into too much of the stuff. I want you to see the boundaries of what comes in and what comes out to show you how to actually use AI inside of a.NET program. Basically, we want something like this. We want an int, get-digit, and we want to pass in a picture, and then we want a number to come out. Now, basically, when you saw this, I don't know if you saw this here when I ran it, because I wanted to show you what the input looks like here. So I'm going to draw the number three and hit Recognize. In the output window, you should be able to see here what it is that the computer actually sees. This is what we're giving the machine. This big long string, and if you squint enough, you'll be able to see into the matrix that that is exactly the thing that I drew. Do you see that if you squint at it? So that's what we're giving the computer. So if you think of the input, that's the picture we're giving the actual computer, and this becomes important when you train these things, because I want you to see what's going on. Now, as we go, I want you to notice that the tool is going to start to melt away and become super important to what I'm doing. Hopefully, this will become apparent. So I'm going to go back over here. We want to get a picture in there. We want to pass out a digit. In general, machine learning is all about creating some function, and you have to specify the shape and do all this other cool stuff beforehand. But you get this function, you pass in these numbers, and out comes the actual number. Again, the things that goes in is that huge array of numbers. So that's it for my slide. What I'm going to do is I'm going to code this the way I would normally code something like this. So I'm going to do this. I'm going to right-click here and I am going to add a new project. This is the thing that I want to show you, because this is where the tool starts to show up and be really cool. So notice that the first thing, here let me go over here, the first thing is that it remembers some of the stuff that I've already done, and I want to do a Python application. The other thing I can do is I can go in here to the language and pick the language that I want, or I can go to search for whatever templates I want to, I can pick the platform, I can pick the project type as well. One of the cool things you see here is it also has one for machine learning. There's some default scikit-learn projects that you can just by default start running. I love how fast we can get to doing the thing that we want. So I'm going to go ahead and select a Python application, because that's generally how I do my AI, and I'm going to call this a Terminator for no good reason, and I'm going to hit Create. So now notice that I'm actually in the same solution working on both Python code as well as C-Sharp code. So now as you know, if we want to write some machine learning code, we're going to have to do some internet sleuthing. So I'm going to say PyTorch MNIST here, MNIST because that's the example, hopefully there's an example that I can do, so here's one, this is the first one. Notice it has the same numbers that I have, and okay, so we have some code here. So what I'm going to do is I am just going to copy it, because that's what some of us do sometimes, and I'm going to go ahead and paste it, and I am just going to run this code as is. Now again, notice that I'm using Visual Studio next to this, you can see I have the code side by side, both in Python and in .NET, and what I have going on here, let me put this back so that they're all next to each other. What I have here is I have the actual code to run like digit recognition, okay? But there's a couple of things. For those of you that are Python users, this is ArcPars, notice that there's some arguments that I want to pass in, well, how do I do that?  Because by the way, I did not have Visual Studio, I repaid my machine a couple of weeks ago, and I installed my Python environments the way I like them first, and then I installed Visual Studio, and look at this goodness right here.  It knows all of my environments that I've previously set up, here's one for TensorFlow actual, TensorFlow 1.1.2, TensorFlow new version 2.0, this is using the PyTorch latest version at Conda environment and notice that the Conda environments are not the ones at Visual Studio itself. In fact, I went in there and I said, don't install yours, use mine, and they were like, we're good with that, and notice that we have all of that goodness in here. Okay. The next thing I need to do is I need to run this thing, but I want to save this into a format that actually works. So I'm going to go down and scroll here, notice that we have some saving stuff here. I want to save this not into a PT file, but into something called Onyx. Again, Onyx is just think of it as a DLL or as a JAR file. It's a way of encapsulating an AI algorithm. So I want to save this to Onyx and like I said before, what we do when we write code is we need to go and actually do some internet sleuthing. You can see here that I have already done some internet sleuthing and found a way to save something to Onyx. So I'm going to go ahead and I'm just going to copy this here real quick and I'm going to go back here because no one ever does this kind of coding, I don't think. Okay. So I'm going to notice the format's a little wrong, so I am going to do this, okay. I think this will work. So let's go to the solution explorer, and we need to give it some actual, remember we had to give it some things to do. So there's the working directory. Let me zoom in so you can see. All the stuff you would expect for to run a Python application. But to debug it, we need to pass in some special script arguments. So let's go and see what they are. Epox is a number of loops that it needs to go through. I am just going to do one for now because I want to make sure that this all works. So let's go to the Terminator code here. Epox is one and then I'm going to go here and I want to actually save the model to a file. So I'm just going to hit Save. I'm just going to make sure that the save model is in there. And now I'm going to save it and I am going to set this as the startup project and I'm going to run it, okay. Just like we would any other thing, notice that it starts to run, right. Everything is going in there. You can see everything is starting to get in there. Hopefully it'll, let's see, let me go back here to the Terminator. All right, everything is running, right. You can see everything's hunky-dory just like I would do anything else. Right now it's learning from a bunch of digits that it downloaded and it's going through the freeze epoch. And the reason why I do this, because again, I just downloaded this from some random code in the, uh-oh. So it looks like we have a problem. Oh, Onyx is not defined. Now here's the thing, I kind of did this on purpose because this is just what I would have expected if I was running in a C-sharp.  So let's go up to the top because I forgot to add this import statement, like a goober that I am. So we're going to hit go ahead and stop here and go up to the top and add this up to here, number one. And there's another error that I saw here. Like I don't think this file exists. So I'm going to call it the cnnmodel.onyx here and we're going to make sure to do this one more time. So I'm going to run this one more time and hopefully it works. Crossing our fingers. Crossing, I'm crossing my fingers right now. So as this goes, again, notice that something bad happened, a breakpoint stopped right where I wanted it to stop and I know exactly what's going on. This is the same thing that I would have done, you know what, other times with C-sharp. And this is cool because I've never like ran Python inside of visuals. Oh, dang it, looks like something else is going on. So let's look at this X here. Let's see, oh, look at that, I think I see it. So it looks like it's expecting a four dimensional tensor and instead I passed it a one dimensional tensor. Let's fix it. So let's go here and say X and we're going to use some PyTorch here. We're going to view minus one and we're going to do a view minus one and we have one channel, 28 by 28. And that's what we want.  It turns out that when we give it a lot of pictures, right? If you think of a picture as a set of pictures, that's the first value here that we're doing. How many are we giving it? I put a minus one in there to tell it just whatever's left over. One says there's one channel because there's only grayscale. 28 by 28 is the size of the pictures that we're giving it. And I think this part will work. Okay, cross my fingers one more time and I think we got it. Now again, the cool thing about this is that I'm debugging and I'm doing everything exactly the way I thought I would have done it if it was C sharp. So as this goes through, it looks like we're at 60, 70, 80, 90. This should all save correctly. Boom, we saved it. Everything is looking happy. And let me show you what it is that we're actually saving. So let's go to open folder and file explorer. And let me click on this thing called the CNN model. And you're going to see that again. It's just a function, but that's formatted in a very funny way. The input that comes in is those 784 numbers that you saw from the code I ran before in WinForms. And then a bunch of stuff happens and out comes this thing that's one by 10, which means that the output is going to be 10 wide. And what's going to happen is in that array of 10 things, there's going to be a number in each slot that says which number it thinks it is. All right, so now the question is, we've already done that. I actually trained a smarter one. You can see this Onyx one is smarter because I actually trained it for a little bit longer. And so that's the one we're going to use. So now we're going to switch over to Visual Studio. I've just trained this thing. I'm sorry, we're going to switch over to C sharp and we're going to start to load the model. I've already written some of the helper code down here to initialize the canvas and all the buttons and the show results. So what I'm going to do here is I'm going to start by writing this thing called an inference session. And we're going to call it session. Now here's the thing, and you're probably wondering, well, where does this even come from? Well, that's a good question. What I did beforehand, I'm going to set this one as the startup project, is I added a NuGet package. Anytime you do something in Onyx, you can run this thing in .NET called the Onyx runtime. And what the Onyx runtime does is it allows you to load up Onyx files as if it were something to execute and then it executes them. And so we're going to go ahead and figure out how to do that the same way that anyone else would. So I'm going to do this here, session equals new inference session. It knows about that. And it looks like it needs a file. So we're going to give it the file. There we go. And that's it. We're going to make sure that the output, the text box up here, let's see here. So we can tell that it's loaded, the URL is loaded. So text URL.text equals loaded. Okay. So let's make sure that works and let's see what's actually in there. So I'm going to run this here and set a break point like we would any other time. So let me load up the model here and we want this one right here. And you can see that it's loaded. And let's take a look at what's actually in the session itself. And this is the cool bit, right? So notice that we have the input metadata and notice that, hold on, let me open it up a little bit more and let me zoom in here. Oh, it disappeared too soon. I'm actually going to do a quick watch. So let's do a quick watch here and let's zoom into what it is that we're actually loading up. Notice that the input metadata is this thing on the zero. Notice that it says zero. Now, for those of you that were paying attention, when you looked at this, you remember that in the project itself, let's go back to that. Sorry, not this one, projects and numbers. You remember that in the actual project itself when I click on it, the initial node that we had here was labeled as a zero. The output node you recall was labeled as a 20. Why it named it that? I don't know, I can't give you the answer to that. So if you ask, I'll be like, I have no idea. But notice that it also knows about the output metadata. It's labeled as number 22. Now, what is it that we can do with the session? So let's go over here and let's, oh, no, we don't want to do that. So let's close and let's go one more time to the session. Let's do a quick watch and we'll say session dot. Notice that there is one thing you can do and that's run. And in the run, notice that it takes these things called named Onyx values. All right, so let's see if we can get that bit to work. So this is all loaded up. You can see that it's loaded, but we still need to do the recognition, which we haven't done. Okay, so the first thing we're gonna do is we are going to go to the predict area and like I'm free coding this, okay? So there's a real mistakes and that's okay. So the first thing we need to do is now that we have the session is we have to actually run this digit code. So what I'm gonna do first is I am going to go ahead and say session dot run and let's see what it needs, because I'm not even, okay, it needs a named Onyx value. So let's see what that is named Onyx value and it looks like let's do dot, it looks like you can create from an actual tensor float. Okay, and it looks like we need to give it a name and the name is gonna be zero because that's the thing that needs to go in and now we need to have a tensor. All right, so let's see how we do that. So in dot net there is this new data type called a tensor. So I'm gonna say tensor, I'm gonna say var, var of x equals new and there's a thing called a dense tensor of float and what we're gonna do is we are going to say it's of digit dot length, okay, and then pass that in. Okay, so now we have x here, looks like we can pass that, we have this named value, so this is gonna be the input equals and now we can actually run the session. So let's do this, so let's do, oh, I forgot, I switched from Python there real quick. So we're gonna say session dot run and I only have 10 minutes. We're gonna get through the session dot run and I am gonna pass in an input but it looks like it needs a collection of it so I'm gonna do this goodness here input, right, because it might have more than one input. Okay, looks like it's happy and then we're gonna say var output equals. Okay, so I'm gonna set a break point here because one other thing that's important is notice that this tensor does not have this data so let's fix that too. So for int i equals zero i is less than digit dot length and then i plus plus, what we're gonna do is we're gonna say x dot i gets digit dot digit i as well. Now here's the thing that's important is it expects it to be in 255, it expects it to be a value between zero and one and you remember when we were doing the output, we saw 255 so we'll just divide by 255 because that means it's the darkest color. Okay, so let's run it and see what happens, okay? So I set a break point there to load so let's run it and let's see what happens because I wanna see what's going on. So first we gotta load the model because if it's not there, it won't work. So there it is, now I'm gonna draw the number three and I'm gonna recognize. Okay, so it worked but we don't know what's in here. So let me do a quick watch here to show you what's going on because again, this is how I like to code. It looks like there is a zero element so let's go here to zero and see what that, oh, looks like it doesn't like that and the reason why is one, two, three. It's a read only collection so we gotta do first. We can do that and what's in there? When I go down there, it looks like there's a value in there. That's awesome, looks like it has a name of 22. So let's see what I can do, oh, looks like I can pull it out as a tensor. So let's do that and let's see if that, nope, doesn't like it and the reason why is because I need to tell it it's a float. By the way, does anyone else code like this? Notice that I'm now getting the value that I want and I'm gonna convert it to, let's see if I can convert it to an array because that's easiest. Okay, so two array. Okay, good, so I've got all of this code that I've figured out and what I'm gonna do is I'm just gonna do dot and just do this and now I'm gonna go back and see if I can rewind a little bit.  So now we can save it and then go back here, one, two. Okay, looks like it went back and now when I hit F10, let's see what happens. What do we get? A float of 10 and we get these crazy, we get these crazy numbers. So this is what I'm gonna do. I'm gonna hit, I'm gonna go back one more time and run it again but now I am going to do this output which is a show, I wanna show the result, so show result and we gotta do a prediction here. So how do we do a prediction on an array? Well, we want the max index, how do we do that? So I'm gonna do this, I'm gonna say var prediction equals array dot index of and then we're gonna pass in the output and then we're gonna get the output dot max because this will give us the index with the max and that's the prediction and so now when I say show result, show result I can pass in the prediction and I can pass in the scores which is the output. I'm gonna put in zero just cause that's how long it takes and I'm just gonna, we're gonna run this again and see what we got. So I'm gonna F10, F10, F10, F5 and hopefully you will, there you go. Looks like it predicted the number three, that's awesome. Now you're probably looking at these numbers thinking what in the heck is this doing? Well, let's do some side by side exploration here to give you a sense of what is actually going on. So I'm gonna do a new vertical group and I am going to hide these things so you can see what is going on. So it looks like here, I'm gonna move this one over here so we can do side by side the other way and this one over here, very good. So notice one of the interesting things that when we're loading this data up they're doing a funny thing here. Number one, they're normalizing the data which I did not take into account. So we need to fix that. So let's go see if I can figure what this is. So let's go to PyTorch, boom. Transform.normalize. So it looks like it figured it out. So we'll go here and then I'll normalize. Oh, here we go. So it looks like what this does is this subtracts the first value of divides by the second. So let's do that to make sure our output is real good. So we're good. Okay, so it subtracts the first number which is this number right here, minus this and then divided by this. Okay. Okay, so it looks like there's something right here. So that's gonna make it a lot smarter number one. And then number two, the other thing that's interesting is like those numbers are really weird. Rather, it give me like a probability of how confident it is. So what I'm gonna do is I'm gonna go up here to this code and I'm gonna look at this here and see what this is actually doing. By the way, again, hopefully you noticed that I'm doing things in Visual Studio that you would never think about doing in Python. I just hovered over and it's telling me. So this is the same as log of the Softmax. And so what I'm gonna do is I'm gonna say E to that power and it should give me something. Because remember, the opposite of log is E and you can flip them around. So let's fix that. So I am going to do this because I was very clever ahead of time. I put that in there, a conversion. So I'm gonna say V goes to system.math.exp of V. But then I'm gonna be even more clever because you know, we like to be clever here. So let me hit save here and let me move this over to the middle of the window here. You can do something really cool called using static. So using static system.math, boom. So now I can get rid of this thing right here. And notice that because of the way Lambda expressions work, I can also just get rid of all of this. All right, let's run it. Boom, with three minutes to spare. In C-sharp, let me load the model here that I just created. And now I'm gonna start to draw some numbers and then hit recognize and you should be able to see, oh, there's a break point. At five, you should be able to see that it's guessing the right thing and now with probabilities. Hey now, 99%. 99%, all right, let's do some other numbers. Let's do the number one. Recognize yes, it got that. The number two, recognize yes, it does that. The number three we already did. The number four, let's see what we got. The number five, what? It's a genius. Eight. Recognize the number zero. Yes. So notice that what I was able to do in Visual Studio 2019 is I was able to create a solution that actually depicts what I'm trying to solve with a number of different languages at the same time. Hopefully you enjoyed that. I obviously released the source code so you can play with it. But what I'm gonna do is I'm gonna get up and I'm gonna go over here to take any questions because my time is about up but I wanna answer any questions that you might have. Okay, 13 new posts. There's no questions. Everyone, look, I know that these, yes. Alch-Beng-Tema, machine learning, Haben-Die-Jungs-Iren-Sirage. I was totally perfect German, I feel bad. By the way, for those of you that wanna learn more about that, obviously we have tons of content to help you with that but the key takeaway was, in Visual Studio 2019, I was able to seamlessly create a machine learning model and use that to actually make predictions inside of a .NET application. It was pretty amazing for me. All right, before we go, I wanna make sure there's no more questions. Oh, look at this. Great, great, great. Yes, thanks, thank you. My friendship dues will be sent via check in the mail so we'll make sure to do that. Again, machine learning, the key takeaway is, we only have about a minute left and then we're gonna go to the next session. The key takeaway is that it's just a different way of writing an algorithm. Instead of you coming up with the steps, you give it the data and Visual Studio 2019 is an amazing tool for you to actually do that both in Python, in C-Sharp and whatever language you choose. Okay.


Hello everybody, this is Alex May from Royal University Bochum and you are listening to the talk how to meet ternary LWE keys So what do I mean by ternary LWE keys? So we are given a n-dimensional square matrix a and a target vector b and We have the usual LWE identity a times s is b plus e for some unknown s and e where s is the secret and E is the arrow vector and they are both n-dimensional ternary vectors and your goal is to find the n-dimensional ternary secret vector s So many efficient cryptosystems use secrets with this bounded range like our ternary keys And then this talk we will especially address and two versions But there are more versions in the paper like the signature schemes bliss and GLP and for the moment We'll assume that s and e are random ternary vectors Also our results apply to larger fixed ranges like if we add plus minus twos and I will give you an example on the last Slide for the bliss signature schemes and our results also apply to variants such as ring LWE and module LWE which only makes them slightly better But we will ignore these effects throughout this talk and in this talk we will address a very elementary question What is the combinatorial complexity of finding s and by combinatorial complexity and combinatorial algorithms here? I mean meet in the middle Meet in the middle algorithms But before I start with a meet in the middle algorithm, let us address the most simple algorithm namely brute-force algorithm So here we start with the LWE equation a times ssb plus e and now we search in the first step for all ternary s and We check whether a times s minus minus b is actually again a ternary error vector And in this case we output s so graphically that means We are looking among the columns of a for a ternary linear combination Denoted by s which matches the target vector b up to some error vector e And if we denote the search space size for our ternary keys by capital s Which is three to the n then the running time of our algorithm is basically This s which is three to the n and we get a polynomial memory So how we what we do now a meet in the mid meet in the middle algorithm on this So in the meet in the middle we would split a column wise in dimension n. So we would look at the first and Over two columns of a denote by a one and the second And two and we would also split s in dimension and half and and half. So this is depicted on the next slide So here a is written as a one and a two and now we get an identity a One times s one as one being of dimension and half is equal to minus a two times s two plus b up to the unknown error vector e and In an algorithm this would mean we would enumerate all as one now being of dimension and half and ternary and We would construct a list l one with all these candidates as one and the right-hand side at the left-hand side of our equation a One as one which we hash and you will see why we hash in a minute and the same we would do for s two Again being in half dimensional ternary vectors We would enumerate them and the left-hand side minus as a right-hand side I'm sorry minus a two times s two plus b and we would have said So why do we hash? We need that the right-hand side Equals the left-hand side up to our unknown ternary e and this is done by locality sensitive hashing Which was introduced by Otlushko in 97 so the consequence we output all as one and as two Such that they have the same hash value under our locality sense different edge function And you can easily show that the running time is dominated by the list construction Which is because s one and s two now have dimension and half three to the n half which is the square root of the search space But with a drawback that the memory is also the square root of the search space s Okay, so now I will give you a brief introduction into the representation technique Which is actually the key for the further improvements on ternary w e So what is the main idea of the representation technique which was introduced by Hauke Raoult Kramer and you in the context of subset sum Algorithms it said we split s now not in n half Dimensional vectors s one and s two, but we split s as a sum of s one and s two both being Full n-dimensional ternary vectors here. I give you an example. So look at this vector 1 0 minus 1 1 minus 1 and I split it such that both summands as one and s two obtain Exactly one one and one minus one So this is depicted here and you see four representations of s Namely, I can split the first one as a sum as I do in some one and some two of one plus zero or as Zero plus one as I do in some three and four and Similar for the minus one I can write it as a minus one plus zero which I do in some One and four or I could you write it as a sum of zero plus minus one as I do in some three and four Yeah, so this is what I called a representation zero. So basically we represent a The ones ambiguously by putting the ones either in the first summit or in the second summit and the same for the minus ones But notice that for the zero of our s we always write it as zero plus zero Now we could change that and even get more Representations and this is what I call rep one. So we additionally represent the zero s one plus minus one Or minus one plus one and here's an example. So the green zero is now represented as one plus minus one and You can think of more representations by using more digits for s one and s two. So for instance here I use twos so I represent the first one in s as the orange representation two plus a minus one Yeah, this gives us more representations and the drawback is it's harder to enumerate over the s one and s two but the big benefit is that once we have our representations Then it's enough to compute only a one over our fraction of s. So why is that? So let's look at our four representations above no matter which one of these we construct They are all equally good because they all sum to the right target vector s and that's Already the magic of the representation technique which was used heavily to improve subset some type problems and Here you see subset some directly. So in the subset some problem You are given a one up to a n and a target vector t And you have to find a subset of the a i set sums to t modulo two to the n and here you see the algorithm So the simplest algorithm is again improved force with complexity two to the n and then you have meet in the middle two To the n half and once you use representations you can improve over this exponent basically one third for something similar to rep zero before and If you use more complicated representations like rep one or rep two you improve to two nine respectively to eight which was as shown at azure crypt last year and It was also used for decoding So you can consider the famous syndrome decoding problem as a subset some problem Type problem over f2 to the n and then you have prong as algorithm from the 60s Which is a brute-force algorithm and then you have the stern and do more algorithm from the 90s and the ball collision algorithm from Crypto 11 which are basically meet-in-the-middle type algorithms and then you have the mmt algorithm from azure crypt 11 Which you consider a sort of a rep zero algorithm and the bgm m algorithm Which is currently considered to be the best syndrome decoding algorithm from your group 12, which you can see that basically as a rep one algorithm now since these Representations were also fruitful for the subsides subsides some type problems and since ternary lwe is also kind of a subset some problem because we have to find ternary linear combination of the columns of a The main idea is to use these representations here as well So this is what we do, but there are two technical caveats. So for ternary lwe It's not exact matching, but we have approximate matching So there's some error that we don't know which is different from subset some we have exact matching to t and also for syndrome decoding and there's another Technical caveat because at least because locality sense a flashing is not homomorphic and that caused some problems But I don't want to go into these details But instead I want to show you now the main idea of our new algorithm, which is called meet lwe for ternary lwe keys So we want to use representation So we use a full-size splitting of s s s 1 plus s 2 both being n-dimensional vectors So we get an identity a times s 1 is Minus a times s 2 plus b plus the error vector and the idea is now to check this identity on n minus coordinates Approximately and on our coordinates exactly and for these our coordinates We have to know the our coordinates of the error vector e which are denoted here by e r So let's look have a look at the algorithm meet lwe So in the first step you choose your preferred representation Rep 0 1 or 2 And then there's a loop that guesses the r coordinates of e denoted by e r And for every guess of e r You now enumerate again all s 1 within your representation and the left hand side A times s 1 and for all s 2 you enumerate the right hand side minus a s 2 plus b And then you output all sums as 1 plus s 2 such that the Meet in the meet in the middle identity As 1 is equal to minus a s 2 plus b plus e r is exactly fulfilled on our coordinates And it's approximately fulfilled on the remaining n minus coordinates And this approximate fulfillness you again check up via otlish goes locality sensitive hash function So the correctness of this algorithm should be now somehow clear to you But what about the running time of this algorithm because here we have a loop where we guess our coordinates of e And this might be a very bad idea. So let's look at this So the running time of our meet Meet l w e algorithm is actually denoted by capital t and it's 3 to the r because this is the guessing part for guessing r coordinates of e times for every of these guesses we have to do a list construction and some matching But recall that in the representation technique we have to construct only a 1 over r fraction of the search space Where capital r is the number of representations that we have and the right choice here in this identity 1 Of small r The number of coordinates that we have to guess is the identity q to the small r is equal to capital r And for rep for all our representations 0 1 and 2 We have that's the number of representations big r is bounded by 2 to the o of n And in l w e we usually choose q polynomial and n and all three identities imply now together from the first identity we get that r is lock R to the base q we write it to base 2 and then we plug in for r and q by identities 2 and 3 And this eventually gives us that the number of coordinates that we have to guess small r is slightly sub linear n n And this is good news because our running time Is 3 to the r which is now slightly A sub exponential n n where is the list construction time is fully exponential n n So asymptotically that means that our meat l w e algorithm doesn't suffer too much from The guessing of r coordinates so asymptotically it's actually the list construction time but for concrete Parameters like for entry parameters we Or of course have to take the guessing into an account, but let's start with the asymptotics first So here I give some asymptotics and for real crypto systems like the enter crypto systems Usually we choose secrets of a smaller weight. So for random Oh, let let me first define what the mate is so S has weight omega if s has omega times n non-zero coefficients So for random s you would expect that you have weight 2 over 3 But usually you choose a smaller weight so having a smaller number of plus minus ones in your In your secret and here in the table you see some weights So we start with extremely small weight like 0.12 and then we also have weights in the range 0.38 up to full weight 0.69 And then we can compute the running time T for these weights and you see here for the very small weight we obtain search space to the 0.3 But for the larger weights we have roughly Search space to the 1 over 4 and this gives our theorem So for these large omegas or meat l w e achieves Chiefs asymptotic complexity, which is a force root of the search space It also has memory requirement force roots of the search space, but if you compare for instance to the formally best known combinatorial algorithm Which was at least goes meet in the middle So we had the square root of the search space. So that means our new result Has another square root and we get the force root of the search space, which is already quite impressive And you will see that this also translates to significant speed ups in practice So let's look at some entry parameters and here I have two parameter sets for you So the first parameter sets are from the IEEE standard from 2008 And the second block of parameters is from the current NIST proposal of the entry team From which is currently a final candidate In the standardization process. So you see in the IEEE standard We have very small weights in With weights 0.12 and 0.11 Search space is ranging between 400 bits and something like 800 777 and ours our results Though asymptotically they should be search space To the 0.3 But in practice they are a little bit worse because we have to take the guessing into account But we also compare to lattices and you see here that our combinatorial algorithm actually improves our current lattice estimates that we have for this 2008 standard and you also see That lattices are somewhat more sensitive For increasing the dimension. Yeah, so the gap opens. So for the smallest dimension We have a gap of like five bits whereas for the largest dimension, which is around 1500 We have a gap of over 40 bits of this But you also see if you go to the NIST Parameter sets that our algorithm is very sensitive to the weight So for instance, if you compare the first parameters of IEEE and NIST, then they are almost the same dimension So you get for lattices almost the same Estimate but for our algorithm The estimate is much worse. So it almost doubles the bit complexity here Yeah, so the basic observation is That the hardness comes or the lattices are very sensitive to the dimension whereas our enumeration algorithm is very sensitive to the weight Okay, so let's wrap up so we improved over the ternary lwe lwe meet in the meet algorithm from Otlishko from the square root of the search space to the fourth root of the search space And there's already a quantum version of our algorithm Which achieves the fourth root of the search space and this is joint work with Egi van Hof and Elena Kirchanova from this year's pq crypto Our algorithm improves upon current lattice estimates in the small weight regime, but not in the large weight regime that was proposed by the Entrude and true team which seems to be a good choice. So they kind of anticipated our new algorithm And our algorithm also has potential applications for side channel attacks Where you get an approximation of the secret and you're left with a small weight regime And we show more generalizations in the paper So for instance, we show more time memory trade-offs using parallel collision search And we also give a plus example including non ternary keys with plus minus twos and there we get classically a very promising result. So we also get the fifth root of the search space Which seems that our algorithm generalizes quite well for that But this also brings us to the open problems. So to generalize as to arbitrary max norms and to analysis It seems that we need new mathematical methods Because our methods gets very very messy if you add a new digits for s And there are two more interesting open questions So one is can we close this gap between asymptotics and practical Parameters that comes from guessing of a small r coordinates. Is it really necessary or can we remove that? And last but not least now we have a combinatorial algorithm Which is best for the small weight regime and the lattice reduction algorithm, which is Best for the large weight regime So is there a hybrid algorithm that gives you the best of both worlds? And that's all Thanks a lot for your attention and goodbye