All right, so yeah, apologies for the small technical problem. So right now, let me try to switch to slides. There will be a little bit of a disconnect. I was too lazy to completely change them, but I'll connect the pieces to the presentation over here. So just to remind you where we were, we were at the setting of weak randomness. And essentially, we looked at these philosophical questions with randomness without any other perfect randomness. Is it enough? And for some applications, we kind of unfortunately had some evidence that for privacy applications, there is some evidence that implicitly ideal randomness is inherent. And so the next kind of direction that we are going to consider is, what happens if we have ideal randomness? This may be not a problem, but our secret key is weak, but we have local randomness or some kind of public randomness. Does it change the situation? And the motivation of these settings, there are many motivations. One of them is, let's say, I want to derive keys from biometric data, and biometric data is naturally non-uniform, but I kind of choose that I have to carry it with me. But maybe I have something which is reasonably to assume ideal random, or a liquid resilient cryptography, something was uniform, but because of side channel attacks, we lost some information. There are also some motivations from quantum computing, and also, as I said, there is also a motivation in kind of more information theory cryptography. There is a beautiful problem of privacy amplification where two people, they have local randomness, but for whatever reason, maybe they observe some kind of randomness, and there is an attacker maybe in between. He also observes something, but as a result, they get something which is, let's say, equal. More generally, it doesn't have to be equal, but let's say they already did what is called information reconciliation, and now they have something equal, but not yet truly uniform in using the public discussions they want to agree on something uniform. Either way, there are a lot of situations. So for now, the last kind of column is local randomness exists, but there is a weak secret. And the question is, what can we do in this setting? And as we will see, even though it will be apparent on this slide, we can do a lot, and one way to deal with this is to kind of directly use the source for a given application, and the other way, of course, is to possibly go through this route of randomness extraction, trying to extract something, and, you know, which is maybe close to uniform, and then just use what we already know how to do. And so here in these kind of slides, we'll do some kind of hybrid approach a little bit in between. We are going to use key derivation function, so we'll derive randomness, and then use something that we already know how to do in the case of perfect randomness, but there will be a surprise that we don't need to extract something which is statistically when computationally close to uniform, it is enough actually to extract something weaker. So we'll do something in between, but we will dramatically, you know, as I said, not dramatically, but we'll essentially go from the more of impossibility to the more of possibility. So I will more specifically talk about, in this setting, I'll just chose one area, but a lot of techniques kind of applied more generally to the setting of local randomness. So I will concentrate on this issue of key derivation where I have an imperfect source, I guess I'll talk about it here, and I want to derive something which is good enough for my cryptographic applications which was originally derived in the setting of ideal randomness. And what I will concentrate is what is the minimal entropy I need so that I can do it. So let me just try to formalize it and hopefully that will connect. Oh, I see, maybe I see so. I don't know, I guess I might need. I just want to make sure this, if I stand here, all right. So here, all right, good. All right, so this is the setting of key derivation. And as we'll see, local randomness, I'm not spelling it out explicitly on the slide, but it will be key for our possibility result because otherwise a lot of things are impossible as I said. All right, so this is our situation. We have an application key P which needs an M bit secret key R. And in theory, we want to pick, we will say R will be a uniformly random M bit string. And in practice, as I said, we have this imperfect source of randomness and there are many, many applications where this is the case. Yeah, one of the important applications I forgot to say which happens in practice all the time, you do let's say a key exchange, you kind of agree on, say, if you have one key exchange, you agree on some group element, but the application doesn't talk about group elements and it needs like a key for AS or something like that. So you need to kind of take this group element and some who hash it on, map it to this uniformly random key that's another great application. So we need a breach and the breach is a key derivation function which takes the source, whatever the length of the source and you write the keys that you want, okay? And only assuming the tax has many entropy as I already motivated, it's, you know, we would like to not to assume much more about it and, you know, get this result. And of course, if you followed what I just said before, in this level of generality, we have a big X here both for extraction and even for direct applications for privacy. And as I said, we'll use local randomness to overcome those impossibility results. Okay, so here, I mean, I'll go quickly but because as I said, our motivation is a little bit different than what I'm hearing here, but one question is what a minimal entropy a k enough to achieve real security approximately equal to ideal security. Ideal security is what we have through uniform keys and real security will be when we have this derived key. All right? And ideally, both information theoretic and as we'll see even in the computational setting it turns out, I mean, intuitively, we need at least, you know, we need an M bit key. Intuitively, it seems like we need at least M bits of entropy, but the question is can we achieve it? Maybe we can use less but it seems like below M is hard to get but can we actually stay close to M? A question from the other direction is and we'll see why I'm interested in this exact setting of parameters. What is the security relation when you have, instead of M bits of uniform key, I assume you have k bits of entropy. So you have, you need 128 bits keys but you only have 128 bits of entropy. Can you like one, you know, have like one-to-one exchange rate like euros and dollars or something like that between entropy and ideal randomness or something like that? So it'll be our kind of thing. And so ideally we'd like to get almost no security degradation and of course the question and dream, maybe we can do both of those things simultaneously. Can we actually achieve comparable security without entropy loss? There's one-to-one exchange rate, okay? So this is a kind of question that we are going to consider. So let's formalize the problem. So in the ideal model, we pick this uniformly, this M bit key and we assume that our application is absolute secure. Again, a certain class of attackers that could be computationally bounded, attackers unbounded and so on. And as a real model, we use this as a key and of course here just use age but as we'll see, even though I will not spell it out, age will need to use this local randomness to overcome our impossibility results. And, you know, already we know that we need this min entropy k. So age will be a carefully chosen and well-designed key derivation function. And a goal is to prove that if we start with epsilon security, we want to prove epsilon prime security in the real model. And so I am like really formalized because remember I told you we are going to get from this philosophical possibility and possibility into this greedy mode of actually trying to get, you know, one-on-one exchange rate and so on. So that's why I'm like giving all the letters here. And, you know, the point that we already, you know, hopefully drove home last time we design age but it must work for any NK source. So, you know, we want to have a general kind of key derivation function. All right, so yeah, we don't want like this kind of, I guess I should disable this gesture control but. All right, so we want our key derivation function and our application to be kind of hand-in-hand. All right, so, and you know, what is the smallest epsilon prime we can achieve in this level of generality? All right, so the first question then translate, what is the minimal min entropy to get let's say comparable security, let's say epsilon prime will be two epsilon. So we lose a little bit, but like essentially insignificant amount. So what is the smallest entropy so that, and you know, we hope that k star is equal to m. So right, so we'll call this k star. Question three will be if k is equal to m it's a complementary question. What is the smallest epsilon prime? We can call it epsilon star. And again, our hope is that it's order of epsilon and the dream will be that we can simultaneously for k equals m achieve epsilon prime equals order of epsilon. All right, so any kind of, this is like very high level, but I just, you know, of course that's like our dream kind of thing and I'll have to reconcile these impossibility results, but this is what we would like to do. All right, I'll pause here. All right, so theory versus practice, that's actually an important slide. So maybe, I guess, David from Intel would love to see if I am exaggerating things here or not, but so one thing that we have to contend as you know, at least for me as a politician is, you know, whether our kind of theoretical results will be actually applicable to practice or people will just kind of ignore it and do some kind of indirect route. And in practice, of course, many people until recently will say, you know what, I have this cryptographic hash functions, I'll just apply cryptographic hash functions and derive our key. And largely to thanks to people I can tell, well, we can compete not just because hopefully we'll get comparable results without these heuristic assumptions, but also because in practice, actually the extractor that I'm going to talk will actually be starting to become much cheaper and hardware than this cryptographic hash function, which wasn't the case until recently. We will kind of realize, listen, of course, if you have like a cute information and the related thing, it should be much faster than some crazy hash function which is like full purposes. So hopefully we'll get there, but for now, essentially, we still have to contend with people who maybe don't do things in hardware, they just say, okay, I'll just hash my source and get this thing. And I believe the trim through is true. And even though I've never seen it formalized exactly, so this is the kind of how I would try to formalize the fact that trim through is true in practice because I would say, well, here is heuristically what we can get. So if you just apply a random oracle to my source, unless attacker is lucky enough to query this kind of random oracle to guess what my source is and he has two to the minus k probability of the source, he's not going to get, he's not going to, essentially the source looks random to him. So if you kind of translate it, I mean, I'm actually, all right, there is like two lines that I need to write which I'm not going to write, but just believe me, maybe Hugo will, I don't know if Hugo is still here, but maybe I think Hugo will talk about it in detail because he will talk about theory of practice and kind of key derivation. But roughly speaking, if you plug parameters, I know I'm skipping some steps here, but this is a bound that you would get where essentially you'll kind of say, unless I query random oracle on my source, just the key derived is random. And if you plug in these parameters, that's indeed gives us fantastic things because if m equals to k, you already get to epsilon. So this would be like a practical justification of this kind of thing. And here, I mean, there is an obvious step here, I'm just, well, okay, let me not talk about it. So this kind of heuristic, we gave a lot of practical kind of criticism when Intel took it seriously, they used some of our papers as a basis of the actual random number generators inside Intel. Like for example, in practice, these functions are not like truly randoms, there is like modes of operation. So there is like valid criticism, but it's, you know, in practice, instead of people like wondering about entropy and reading my papers, it's just much easier to apply shot to the key and just assume that everything is going to be fine. So we would really like to have, you know, theoretical justification to say, listen, you don't need to do it, you can be faster, you can have savings hardware and you can get bounds closer to this. That would be really fantastic and we can actually bring theory closer to practice. Even though of course this bound is completely heuristic. All right, this is, I mean, even though I didn't derive it, but this would be like a heuristic bound. All right, so a little bit about extractors and this brings us to this like missing column here. So this is what we would like to do, we'd like to take X and derive R. Unfortunately, as I said here, I'm like putting just one bullet here and of course I spent like three hours justifying the need for this bullet, but unfortunately this is too good to be true. So what modern instructor says, listen, deterministic extraction is impossible because of all this, you know, at least in this level of generality, or unless you assume there are two independent sources or things like that. So we need to design these extractors that take public local randomness and then they use it and of course you can say, listen, if you have this randomness, why don't you just ignore this guy and use this guy? It's perfectly unknown. Well, because it's public or it's local. So essentially this randomness might be known to that hacker. So all the secrecy comes from this X, from my secret key. So I want the joint distribution of my extracted thing to be uniform even given the seed S. So but the seed, so we do assume truly uniform seed or at least independent seed, but now I'll assume truly uniform, but it's unfortunately public, right? And we need to derive something here. Is this point clear? So and as I said in this model, well, I will kind of implicitly prove it, but in possibility results no longer hold and we actually instead going to go after our dreams, okay? All right, so there are many, many uses in complexity theory beyond key derivation, but I'll just concentrate on key derivation. All right, so the formal definition of extractor there is some annoying form, but that's exactly the statistical distancing. So essentially I'm just wrote a definition of statistical distance, so you don't need to, you know, read it. But essentially it says that no distinguisher can tell it apart with probability more than delta. All right, so this is statistical distance. All right, so here is like a very trivial kind of lemma that extractors, remember I put this extraction, if we can do extraction, we can like trivially do everything we want because if the key is epsilon close to uniform, then I can get that my final security is original security plus the error of the extractor. It's a very simple kind of triangle inequality because the statistical distance is a very strong notion. And as we will see that will be the thesis of what I'm going to say it's like the notion is too strong, we can actually do better, but we'll get there. All right, so this is like a philosophical thing that we won't be clear for at least another 10 minutes, but I just want to say is that to prove this lemma, we don't really need like general distinguisher because, you know, so the previous thing works for any distinguisher. So nobody can tell it apart, but for a particular when we apply it as a key derivation function for application, there is a potentially strictly distinguisher because what is a distinguisher? It's usually the combination of attacker and a challenger. What do I mean? For any definition like encryption authentication, there is usually the formalized as a game. It says there is attacker and a challenger. I like, you know, Puy is attacker, he claims he can break my max, so I'll sample a secret key, he'll ask me what is a Mac of zero, I'll tell it to him, then he gives me Mac of one and I say whether he succeeded or failed, right? So in this case, if you want to argue that this combination of me and Puy cannot tell real key from derived key in some sense, you know, we kind of combine us together and make like one distinguisher which is this combination of these guys and depending on the particular sequence of the game, it's, you know, it could be potentially strictly distinguisher and you will see how it comes around. So, but before getting to this point, now essentially the question is what is the price? Right, so what is the best? Now that we understand this thing, so what is the smallest delta we can get as a function of m and k? Of how many bits do I need and how much entropy do I have? Right, how many bits I need, entropy I have or is the price, right? To get this thing. All right, so there is a very famous lemma which I will not prove here but implicitly will prove a stronger version at the end of this kind of presentation. So that's why for now just believe me is a bound but we will prove a better bound at the end anyway. So this is what this famous leftover hash lemma says. It says that if you choose something called universal hash function, I don't know if I have a definition, I don't have a definition but it's not needed yet so it's thinking about a random function. But essentially there are these extractors with even short seeds but you know, the seeds here are not necessarily short but this thing called universal hash function i k delta extractors where this is the error that you pay. So if you need m bits of entropy so intuitively as long as k is a little bit more than m this starts to be a small number and hopefully the more entropy you have the smaller is this number. But this kind of you can see that k has to be at least m to even get started, okay? So does it make sense? I'm happy to remind people definition of universal hash function if it's needed. So it's, they were actually already implicitly used in one of those facts. You know, but anyway. So universal hash function will say that the family H of S is I think, okay, let's say perfect universal just to make it simple or I need another letter. Gamma I guess universal. If for any x not equal to x prime probability over the choice of S hs of x equal hs of x prime is at most gamma. And best gamma is two to the minus m where m is output size. So it's a very simple definition, hopefully. It makes sense. It's like a family of hash functions for those of you who remember your algorithms classes. This is how you build dictionaries. You just want to make sure you hash into a smaller domain and you want to make sure that any distinct, any two distinct items will not collide this probability, you know, except the small probability. So this is definitions. There are many simple constructions. So anyway, so this is what leftover hash lemma gives us. All right, this is a bound that gives us. I mean, it looks kind of scary. Like it has crazy words like leftover hash lemma and so on, but it's really simple proof. Really easy to use and the functions are very efficient. All right, so as a corollary, what do we get? We get that new security epsilon prime is the original security plus the error of the extractor. And notice that in the leftover hash lemma there is local randomness. What is this guy? It's this description of the hash function. Right, so that has to be chosen at random and that's why, you know, we don't get into a possibility result. So in particular, I mean, let's forget about the other thing, but you know, if you want comparable security, if you want this number to be epsilon, K has to be M plus two log one of epsilon. So there is an extra two log one of epsilon that you pay and this is called entropy loss. And this is actually the only thing that I'm going to put in this column for extraction. For now, I'm going to put this number two log one of epsilon. So for now in this table, we'll just concentrate on the entropy loss because as Sfirma said, the margins are too small to put more stuff. So we'll just concentrate on one parameter which is entropy loss. And if you just want to do extraction, at least using this traditional kind of thing, we need to pay an extra loss of two log one of epsilon. And you know, if K is equal to M, we get no security at all. You know, epsilon star is equal to one. All right, any questions? So people are lost in the letters. All right, if you are lost in the, okay, so I'll give a table and then we'll go through the letter. And unfortunately, there is this very annoying but correct result of Rana Krishnan and Tashma which says that it's not just the problem with universal hash function, but any extractor, you know, if you have an extractor for any source of entropy K, delta, you know, this extra security must be at least this. So leftover hash lemma is optimal. You cannot beat it. So at this level of generality, if you want to extract something, statistically close to uniform like bulletproof security, you must pay this price. So let's see what we get. So we have this, this is like round one. So we'll have several rounds in this fight. Again, it's practitioners. So this is what practitioners have. So green stuff is good, red stuff is bad, blue stuff is unclear, you know. So here we have any application. So if you use a cryptographic hash function, I mean we will be, we cannot apply it to information and territory applications because we have heuristic stuff. So but it will be intuitively, we hope it's secure for computationally, secure applications, of course it's not probable, it's just heuristic. So this is like a general formula that we get. This extra thing, remember, there is this extra security loss, epsilon times two to the minus k, that's the ideal thing that we had, you know, using heuristic kind of argument. And this is what provable leftover hash lemma gives us. So it's worse in two regards first, you get to take a square root over this number and for numbers less than one, square root is actually kind of pretty bad.  The original security is very small, you don't get this extra thing. So that's why I kind of put a threat. So comparing to this, it's actually in case, for particular parameters, it's pretty bad. There is no security if k equals same here. Here you would have fantastic security already when k is equal to m. Entropy loss, here is zero. That's why, so essentially in the ideal setting, if you have a good hash function, you just kind of assume there is one-to-one exchange rate for, you know, entropy and randomness, which is of course unrealistic, but you know, we don't have like really huge attacks against it. And here we have like really great stuff. We have any application, very simple, much faster. Now with David here, we can really have much faster implementations between universal hash functions and cryptographic hash functions. But yeah, there's worse bounds here, but it's probable. All right, round one. Any questions about round one? So we need to put a few more kind of rounds. I need to cite a few more papers of mine so that we can close the gap here. All right, yeah. So that's my last slide. So it will be one of those like recent papers. They will be unfortunately still some gap, but yeah.  So I'll keep the suspense and we'll talk about, you know, how far we can close the gap. But there will be several rounds. Okay. Sure. If you go for the hash, so one. Okay, so every time you use a seed, you're right. Every time you use a seed. So yeah, I mean there is a union bound, so but usually, you know, this is the kind of absence we are talking about will be two to the minus like 64. And so on. And yeah, it's like every time you use a seed for a new kind of source, you kind of pay additively. So, you know, you use it like a thousand times instead of two to the minus 64, you get two to the minus 54. I don't know if it's inherent or not. I think for endomorphical, it's also kind of the case because you kind of, you know, so if you assume that there are 10 people using the scheme, but then they will, there are 10 attackers trying to break it. And then they can like compare that and the moroccal queries and see if I helped you to break it. So I think it's not a big deal kind of thing. It happens, it happens, yeah. Yeah, it's just additive, yeah. Of course, there is a big thing I'm assuming independence of the seed and the source. We do have some papers where we like this assumption, but right now, I mean, this is like, you know, orthogonal, but very interesting question, which, you know, feel free to ask me at the end, but it's an important assumption. Good. So how bad is this entropy? Because it looks like, especially for asymptotic terms, it's like negligible guy or it's like tiny number. So for any sources, they don't have this extra two log one or epsilon bits, you know, biometrics, physical sources. In general, entropy, well, I mean, unless you're like Intel physical RNGs, they have like entropy apparently for free, which is good. Or, you know, it's like, they have a lot of entropy at a lot of rate, but you know, unless you have such a good sources in practice, like especially for biometrics, or traditional, more physical sources that they use like in like traditional operating systems, they just kind of heuristically look at timing between interrupts and things like that, where there is a lot of like partial information known to a potential attacker. And also more like for practice, if you talk about different helman kicks change, the entropy corresponds to the group size. So if you want really fast elliptic, you know, curve, you will want to use a small group. And it means the entropy will be uniform over the small group. So you'll have less entropy. So, but you know, low entropy corresponds to much faster efficiency. So, so this is kind of, you know, significant for this, you know, applications. So just to give you an example, so if I want to use a minus 64 security and I want to derive a key for AS, I will get K star, like 256, so I kind of double to get 128 bits of, of true enter randomness, I need 256 bits of entropy. So for this practical thing, it's like double. It's not, I mean, it said it, for this practical parameters, it's kind of doubled. And heuristic extractors, you know, they don't have proofs, but they seem to have an argument that you need 128, which is, I mean, in practice could be a big deal if I assume my biometric thing has, you know, 256 bits of entropy or 128. So anyway, end result is, I actually don't know if it's true, I'm not a practitioner, but I would guess that practitioners might prefer this heuristic key derivation to probable key derivation. And you would like to tell them that they shouldn't. All right, so despite this RT bound, which was like a negative result, can we do something better? And there are several avenues for avoiding RT, so I don't know if people are geeky enough to get this joke, probably not. But so RT is the Sraddakrishnan Tashmabhad, apparently those windows RT for a while, it was, I don't know, some kind of version of Windows. Anyway, so what are the options? So one option is, well, so this is the first route. It restricts the power of distinguisher D or the class of NK sources, right? Because if in generality we don't do it, we have impossibility result. And here are several ways to do it. One, I'll talk about it in reverse order, I'll come back to it later. One, we already talked a little bit about this, maybe we restrict to efficiently sampleable sources. The second is, you know, much more popular is going to talk about it like tomorrow and so on. It's like to talk about, assumes that the distinguisher is computationally bounded, so maybe computational security will help. And that will be like the last slide, will be nice transition for Leo. And the third thing which is really what I am going to focus, so as you see there are a lot of Ds in red. So this is like the sequence of words that we've done starting at crypto 11 is we are not explicitly restricting the distinguisher D, but we are really implicitly restricting by considering special classes of applications. They're not going to be that special, they could be like all privacy applications, so it's a pretty big class. So in particular it will look like all privacy amplification, all authentication application, but we'll consider kind of key derivation for cryptographic use. And it seems like that's like super general, but turns out it is, but turns out we can beat this RT bound in this kind of sense. And the second round which really overlaps is like it's a different way to state the same thing here, but just a different perspective. The second round instead of explicitly restricting, talk about like abstractly what distinguisher, what sources or something like that, is just say listen, do we really need to derive a statistically random key R? Right, it's like, I mean there is a lot of overlap between these two questions. And for some applications you can convince yourself for one time pad, the answer is yes and in fact they even prove to you this kind of result for like one time encryption or something like that, I to some extent, well there is a gap between this local randomness, but in two Italy for one time pad, it seems like if my affiliation is really one time pad, if it's not statistically random it's, if I source a message there will be some partial information leaked. So this is, so at least for this one time pad, yes we need statistically random R, so we'll have to bite the bulletin, just take this thing, but for me and in fact I would argue most by the end of this kind of presentation, turns out the answer is no, we don't need statistically random R. And this is what I'm going to talk about. So the philosophy is, there is a punch line, there is a difference between extraction key derivation. And this is what I'm going to talk about in this column, concentrating on the entropy loss. So here we know that for extraction it's two log one of epsilon, and here we'll see if we can beat it. Yeah, a question? It's just like a different way to say it, it's just here I'm kind of explicitly, I mean there is a lot of overlap at the end of what I emphasize will be the same thing, at the end, it's just like different ways to, I mean they're very correlated this question, so nothing super deep, but yeah just two different ways to approach the square. You know, not even the different perspectives. Alright, so let's start with the predictability application and actually I'm going to repeat something that I already started here, but I guess it would be a good place to do it. So remember in this case, what is the advantage of the attacker? It's probability the attacker wins. And in this case probability attacker wins, in our case the attacker, remember the distinguisher was a combination, he simulated the whole game in his head between the challenger and the attacker, it's just in one case it was true, with truly random key in the other case in derived key, but anyway so this is a probability distinguish output one and this is a non-negative number, right? And this includes all kinds of applications where the goal of the attacker is to guess something, and he means that he does it with probability, anything significantly greater than zero, but for encryption he means like 51%, so that's like will be slightly different, as we will see. And so let's do a case study and look at key derivation for signatures of max. So what do we know? We know that probability attacker forges a signature is at most epsilon, right? That's our assumption, whatever is computationally secure information theoretic, we don't care. We just assume some whole lot of smart people like Ali Shamir or whatever like analyzed it and it's good, you know, with uniform keys we are good. So what we hope is that if we have the extracted key, we get this epsilon prime which is close to epsilon. This is our goal. And the key inside here from this perspective we only care as distinguisher which almost never succeed on uniform keys, right? We have this probability on uniform keys at most epsilon, so we care about this like relatively kind of restricted class of distinguishers, right? Because, but in general extractors would talk about all distinguishers and he care about distinguishers which almost never succeed. So in particular, we don't need like additive loss. Even if you have a multiplicative loss like times five, it's okay, right? You know, one-fifths times five is bad. It's like from one-fifths you get to one but one-fifths are already a large number. So we don't care but if it's like two to the minus 64 times five, it's still a pretty small number. So this kind of leads to this notion of unpredictability extractors. So this is like an abstraction that we introduced specifically for unpredictability applications. We say that something is key epsilon epsilon prime unpredictability extractor if the distinguisher succeeds with probability at most epsilon uniform key, he will succeed with probability at most epsilon prime on the derived key. So this is unpredictability extractor, like exactly what we need for unpredictability applications. And the theorems that we proved in a joint work with Shishtov and Daniel Vicks at Eurocrypt, I think, 13. I mean, we proved that general theorem I'm talking about two extreme cases just to talk about our questions. So we can either have comparable security, lose almost nothing in security, or maybe a factor of three, and the entropy loss is only log log. From two log one over epsilon, I'll give you particular numbers. And this is not asymptotic, this is exact. So this is like, you know, this is like essentially nothing. Or if you want really to assume k exactly equal to m, you lose still a pretty kind of negligible kind of small multiplicity factor in security. So this is what we will kind of show. And again, well, there exists such kind of extractors with these kind of good parameters. So let me tell you the plan of attack, and hopefully, and you know, in all cases, you know, the seed will be critical, but we are not building an extractor. We're building unpredictability extractor, but we are not building a traditional extractor. So this extractor, as I said, so, you know, this epsilon prime will be two tiny numbers, but if some event happens with probability one-third, for all I know, here it will happen with probability one, but we don't care about those events. Right, because then the signature is insecure to begin this. All right, so here is our plan of attack. So, and this is actually the key thing. So the key insight here, and I already kind of prove that it will come on the next slide. I will prove the same. I'm not about to remember entropy deficiency. Do you look like a factor two to the d? We'll come up on the next slide. But the key thing is for unpredictability applications, I don't need truly uniform keys. They already work with the key has high entropy. As long as the key has like entropy, almost uniform, but not full, it's okay. I mean, remember, we cannot jump off the cliff with unpredictability application. It kind of degrades slowly, right? Like for one time pad, we jump off the cliff. Like you lose one bit of entropy, you're screwed. In here, you don't completely jump off the cliff. So maybe it's kind of okay. And this is, so for example, if the derived key is random except the perth bit is zero. It's like just specific example. I assume that's our key duration. Then we can lose only a factor of two, because even for a truly random key, the probability, you know, it will be zero here with probability a half. So we cannot let them do it. You will lose more than a factor of two. And that's exactly the slammer that I'll put here. So let me actually try to formalize it. So fix, I mean, I'm just repeating it. Fix any authentication application P, any legal attacker. And we define this function F of R, which is advantage of the attacker. And this is, I'm like repeating what I did at the very beginning of this thing. When I did for security, one time max is V keys. I'm just doing it in full generality for any unpredictability application. And ideal security is exist from this notation. The key is just, so this is advantage of that kind of specific key. Now the key, if it's chosen truly uniformly, we get this formula for the ideal advantage epsilon. So it's really expected value of F of U. But the real security will be, I call it X here, I call it R, but just because R here will be jumping ahead, I derived key. So it's a minor difference. This is just especially, you know, whatever this probability distribution is, it's just expected value here. And this lemma that I already proved is expected value of F of R for any non-negative function is at most two to the entropy deficiency times that. That's exactly the lemma. I'm repeating it, except that I kind of did it for the case where implicitly I assume that the scheme is deterministic, there is no local randomness here. I'm just saying it doesn't really matter. It works for all signatures, max, identification, scheme one way function. Anything where the attacker has to guess something and his advantage is a number between zero and one, this thing kind of works. And so this is entropy deficiency. Anyways, I'll skip the proof because I've done it. The corollary is that epsilon prime is at most two to the d times epsilon. And what we did, we applied it for one time max, remember, and we got like the specific numbers here. That will be, I'll revisit it perfectly. So I'll revisit it in 10 minutes. We'll have an analog of this lemma for encryption. No, but I can tell you because for encryption, the advantage of that attacker is not non-negative.  It's like the attacker for some keys he can have minus, like one half for some keys, one half, so I mean, it will be clear why it doesn't work for encryption. But yeah, the reason is like totally silly because F is not non-negative for encryption. So I mean, I'll come back to it. And they will be the whole kind of half an hour on this. So any questions about it? Too many symbols or, you know, letters? I'm sorry, it's like, hopefully there will not be too many new letters involved. So let me summarize what we have. So this is our plan of attack, right? So step one, and this is what we completed. We argue that for any unpredictability application, P works well with only high entropy keys. So in particular, as long as the entropy deficiency is there, lose two to the D and you say, wait a second, that's like horrible, it's like two to the D is huge. But if D is like one or two, it's like nothing, right? So that's what we are going to achieve. But of course, if D is one or two, the key is not statistically close to uniform, it allows some bits to be zero and so on. But we say we don't really care for authentication, it's just a minor multiplicity factor, right? So this is, all right. And the second step is, well, now that we have this thing, what do we need? And it turns out, we don't need an extractor, we need to something which is called a condenser, I'll define it on the next slide. It's a relaxation extractor, but instead of saying extract something statistically close to uniform, I say extract something statistically close to a high entropy distribution, which is not necessarily uniform. But it has entropy M minus D. And then combining those steps will be done. No, no, well, it depends what D we'll achieve. So yeah, so you're right. So if we already have a key, we don't do key derivation function. So in the previous thing I kind of said, assume you already have key, you have entropy deficiency D. Of course, in this level of abstraction, if you don't actually ensure that D is small, if you talk about biometrics, probably D will be huge and that will be a huge number. But remember, we are going to talk about key derivation setting in this case, where we will control, well, not control, but we will achieve D and we will actually enforce D. So think about traditional key derivation, we'll extract something statistically close to uniform. So D is zero. You're statistically close to a distribution of entropy deficiency zero. And I'm saying instead of being statistically close to entropy deficiency zero, I'll be statistically close to entropy deficiency one. And all I pay is a factor two here, right? So hopefully it will be clear, but let me know if on the next slide, I didn't answer it, let me know. So this is like the kind of thing by using appropriate key derivation. So yeah, if it's just start with entropy deficiency, maybe it's like you can say, oh, how do I assume that my entropy deficiency is one or two? It's never going to happen with biometrics and so on. And I'm saying, well, we'll make it happen by applying a very good key derivation function matching with mean entropy. So essentially, what we will show is we can achieve with this entropy deficiency, that's a restatement of our theorem. With this entropy deficiency, we'll achieve little d equals one, or two, which means two to the d is two. Or with this entropy deficiency, which is zero entropy deficiency, sorry, with zero entropy loss, we'll achieve entropy deficiency log one of epsilon, which means two to the d is like log one of epsilon. I mean, there will be one theorem, this is just two extreme settings of the same theorem. All right, so let me try, so this will be a painful slide with a lot of painful letters, but I tried to use colors just to cheer you up. It's like, so hopefully you guys will go to this. I have never been this, how's it called, Gwell thing? I was told it's like very colorful, you know, this park. So it's beautiful, so I'm just trying to prepare you with a lot of colors, okay? All right, so let's try to give it lots of letters, lots of colors, but hopefully a very intuitive notion. All right, so Kd epsilon condenser. So given any nk source x, I want to output m bits, so it's like a key derivation function. They're allowed to be, you know, not perfectly kind of high entropy, but they could be epsilon close to some source of entropy deficiency d. So ignoring this epsilon close, essentially you instead of deriving uniform keys, you're deriving keys which have high entropy. That's all you do with the condenser. And so formally condenser is statistically close to this and the property is that the distribution of y-condition on the seed is m minus d, right? Yeah? This is one definition. Well, this is just a definition of, I mean, I didn't say if d is high or low, I'm just saying this is a definition of a condenser. And then we can see what we can achieve, but entropy deficiency? Well, I mean, this is the definition in the theorem. We can achieve d's and we can see how big, I'm not sure, so this is definition, right?  Oh, sorry, I guess I don't know if I'll state it. Yes, so I mean, so extractors is a special case when d equals to zero. What does it mean d equals to zero? It means I'm epsilon close to something with entropy deficiency zero. Well, the only thing with entropy deficiency zero is uniform distribution. So you get the definition of extractor. The problem is, you know, if you trace our thing, we're saying our original security was epsilon and we paid epsilon times two to the d extra. So extractors have d equals to zero, so you'll get to epsilon, that's great. But unfortunately, with this RT bound, it forces us to have large entropy loss.  You know, statistically close to perfectly uniform. And the amazing thing, which we kind of, we, Shrestha and Daniel, after we approved it, we kind of initially couldn't believe it, they thought there must be some smooth transition or something, and there was in the general form, but so this is what our theorem kind of says. It says, if you just, you know, instead of getting a key of mean entropy M, if you just, instead of getting a key of, you know, entropy 128, you know, if you want to derive 128 bit key, if you want to get a key which is like 127 bits of mean entropy, suddenly the entropy loss is exponentially improved from two log one of epsilon to like log one of epsilon plus four. The reason I put plus four, I wanted to say, it's not a asymptotic result, it's some huge constant, I mean, this is a number, you know, so hopefully you can actually compute exact things. Or alternatively, again, this is a number. K equals M, you can get the entropy deficiency log log one of epsilon, so I'll give you particular numbers on the next slide. Let me see, I think I'm okay. I was going to tell you a little bit about the intuition of the proof, but yeah, for now I'll just pause and take questions if people follow high level, what is going on here? Well, this is a bound, we prove, I mean, this is a bound. Yeah, and it turns out this is tight, yeah. Both of the, I mean, whatever the straight of C is, this is tight, yeah. I think we mentioned it in our paper. I think, I mean, we ask people if people consider it, I mean, the proof is not hard, it's like relatively standard. I think just people in complexity just, I mean, they didn't have applications to key derivation and they cared about like the obsessed about minimizing seed lengths and things like that, so, you know, yeah, if you ask like Rastan and Poliat, so he says, yeah, I don't know, but it's something I can compute in five minutes, but he didn't read it, so. But yeah, it's not a deep result, but I think it's good. I mean, it means that that's the result we want, something that people can understand and which applies to practice. Yes, I'll talk about it, yeah, I mean, remember there will be round two, I mean, in two or three slides, I will show you round two table, I'll talk about efficiency and so on. But yeah, you, it's a very good question. Unfortunately, there will be a little bit slower than perverse independence at universal hash functions, but good, yeah, so. All right, just a little bit about the proof. And maybe it's a little bit technical, but we'll see. All right, so this is intuition. I'll try to give the intuition. If not, don't worry about it. It's just a technical computation. So this is the kind of thing that we do. So we have something of min entropy k. So imagine that we have a uniform distribution on two to the k values, that's our min entropy k. And we are trying to derive something which is m bits long. So imagine we have this two to the k balls that we throw into two to the m bins. Overall, we have of course two to the n balls, but only two to the k of them are real. Those are the only one in the support of our distribution. And then, so we pick a random ball x. That's how we pick a random sample from our source. And we see what bin we got. And normally if the bins were perfectly kind of uniformly, every bin would have the right number of the balls. There will be perfectly balanced with the two to the k minus m. But here we are okay to have entropy diffusion CD. So we are okay if the bin would have size up to two to the d times its expected size. Right, if you throw it like perfectly balanced, magically, then we're saying we are okay with this. But of course, if it's more than this, that means that we fail the game. So this is the kind of, it turns out if you think about it, this is a very simple game. And because our key derivation function is kind of symmetric with respect to points, we can just pretend that we start with these two to the k balls. And let's say we throw them at random. So for now, let's just talk about perfectly random key derivation function. So everything is symmetric. So this is a game, two to the k balls, throw them at random, pick a random ball, and see what bin it ends up with. If the bin is like too heavy, we lose. Right, so this is our game. And yeah, and given dm epsilon, our goal is to say what is the smallest number of balls so that like high concentration bounds or whatever starts to kick in effect. So the probability we lose is at most epsilon. So this is a formalization of our condenser question, really. And as you can see, it's so obvious that it cannot be hard and indeed it's just like a two or three line derivation, which I'm not going to do with some chain of bounds and so on. But essentially once you do it, you get parameters of that theorem. I mean, but I'm just saying it's not, you see, it's not a very hard thing. It's kind of anybody who's taken elementary probability class can just do this derivation. But I just chose not to so that we don't see that chain of bounds and stuff. Okay, and thus the observation, this is a technical stuff in terms of efficiency. Of course here I'm saying a completely random key derivation function will work, but of course it means it's inefficient.  It turns out, and again, it's just a calculation with the different tail bounds and chain of bounds, like log one of epsilon dependence of i's. Why? I don't know, it's just you plug in and that's what you need to kill the union bound. So in particular, this is not bad because here in practice epsilon is like two to the minus 64. So yes, we need 64 y's independent hash function. So it slows and pair of independent hash functions, but I mean, I'm not sure. People haven't implemented it, but it might not be a deal breaker, okay? So, and there are some more improvements. All right, so the table, okay? So now let's do our round two, okay? So what do we do? So we did this, we covered all unpredictability applications, right? So we are in this table. And actually I'm going to start filling this stuff. So here I'm putting log log one of epsilon, okay? I mean, I'm not putting, and this is, I guess here I put heuristic derivation if you wish, we'll just put it here. So heuristic derivation is zero. So here we are coming actually pretty close to zero arguably, right? So ignoring the general formula, this is the entropy loss is log log one of epsilon. It's provable. The function is not as efficient. It's not universal hash, but it's not horrible and hopefully in practice probably given current limitations maybe a little bit slower than this, but it seems like with enough hardware support it could be comparable, okay? So just to give you a particular parameters, I assume I want to do a MAC. I'm actually, you know, syndication code like the computational, you know, it doesn't really matter, computation information trading. I want security to the minus 64 and I want to use AES as my block cipher. So this is the key length. So leftover hash lemma says listen, ignoring this column, it says, listen, if you want comparable security you need 256 bits of entropy. Heuristic guys will say you need one, you know, you have one-on-one exchange rate. So it's like 128.  Or for elliptic curves, it's like, you know, the elliptic curve size is like two to the one-thirty-eight as opposed to two to the one-twenty-eight. So it's, you know, it starts to be pretty good. So, I don't know. So, you know, I don't know. Because I call it a dream, I said dreams comes true. I'm not implying that this is like, was a major open problem or anything. But to us, it was surprising that, you know, we could actually provably come close to this heuristic bound with random oracle. Yeah. Yeah. Right. Yeah. If you do it for a Mac, for encryption, of course, but yeah, if you know that you're deriving key for the Mac, I think it would tell you that you were doing, but of course I want to be a little bit careful. I'm not talking about an extractor being CBC Mac, like the papers that you know, but I'm talking about you're using something else for key derivation. So in this case, we tell you that you should use this 64-wise independent hash function. But if you want to use a key for a CBC Mac as a Mac application, then this is a bound that you should, this is the entropy that you should assume, which I think is not bad. So, and also this is like also if you want to assume this one-on-one exchange rate, LHL gives you no security, heuristic gives you two to the minus 63, and here we get a respectable number. I wish it was two to the minus 58, but I didn't want to put two to the minus 57, so I'll put like dot nine, but yeah, it's not bad. All right, so now the big kind of question, what about indistinguishability applications? All right, why doesn't what we do for privacy, for unpredictability applications work for indistinguishability applications? What's the difference? So we already kind of know that it's impossible for one-time patent intuitively. It's a statistical application. If the key is not uniform, you get some information about the message. So, all right, so it looks like nothing is possible. We have a counter example, so we can go home. Still we'll try to do a similar plan of attack and see if there is something we can do, just like we'll blindfold it, we'll try to be pedantic, we'll try to build this condenser, so whatever, and then see maybe there are some surprises along the way. And there will be. So this is what it will be a little bit technical, but not too bad, I think. It will be very intuitive in retrospect. So we will identify a subclass of indistinguishability applications, which will not include one-time pad, but will include everything else essentially, which work well only for high entropy key. So for authentication, we know that any application works well with high entropy key. So here, for privacy, it's not true always, but for some applications, we will understand exactly for what applications high entropy key works, okay? And as a small technicality, it turns out here, we will see why from the proof, like literally to slide, a slightly more convenient notion of entropy will be any entropy, but I don't want to dwell on it for, I mean, mean entropy also works, but it will get just better balance with any entropy. So I'll define it, it will be like two slides from now. This is just a technicality, not a conceptual point, it's just to get better parameters. And we will have an equality similar to this expected value kind of thing, which I don't know why I'm pointing there, where it was like three hours ago. So we'll get this similar kind of thing, but still we'll be able to beat left over hash lemma. And the step two, we'll build a good condensers, for whatever parameters we need, but this optimization is, we only need to do it for this weaker form of entropy, so we will get some benefits from it. So this is a plan of attack, okay? So let's see how we implement it. All right, let's concentrate on this thing. That's where the key kind of surprise maybe comes in. So let me try to do it here. So first, earlier than I decided, let's talk about inequality. So first I need to define what the entropy is, but this is just a technicality because it will be more convenient to work with. So collision probability over distribution i is a probability that if you take two independent samples, what is the chance that they collide? And this chance is simply summation of all r, it's p of r squared. Because what is the chance that two samples are equal to five? It's like p of five squared, six p of six squared, and you just sum it up. And it's easy to see that this is at least mean entropy. So in some sense, if we know, so why is it good? So of course, if we know that mean entropy is 17, we know collision entropy is at least 17, right? But what I'm saying is, but remember, this is going to be the derived key. So it will be easier to derive key of rainy entropy is 17 than mean entropy is 17. Because maybe any entropy is 17 and mean entropy is not 17, but it's okay. I mean, we will only need rainy entropy. So that will be kind of why, just as a technicality, we will win a little bit. All right, so this is the definition. I hope it is scary if it like buzzers, you just think of mean entropy, okay? You will only need to switch to rainy entropy when we actually build something particular and we'll get better parameters for it. Okay, all right, so this is a new lemma, okay? So the new lemma works for all functions, not just for non-negative functions. So this lemma will give us weaker bounds, but it works for all functions. And the importance of non-negative functions will come in the next slide. All right, so this is a lemma. You want to look at the expected value of the function with respect to the real distribution and see how much worse is it than with respect to the ideal distribution, right? So this number, remember, well, jumping, but anyway, this number will be epsilon, but so this is like a relatively natural thing. Previously, we were okay with multiplicative laws, but because this is privacy amplifications, we cannot have this multiplicative laws here. So we have to subtract those things. But there will be multiplicative laws here. So this is equal to the square root of two to the D minus one. All right, so this is the centripet deficiencies. So this is the price here. And then there is this bizarre term, which I am going to dedicate like two or three slides on. All right, but this is our term is expected value of F square of the uniform distribution. All right, so I'm not going to give you the proof, but the proof is three lines, but I'll write the first line of the proof and we will see that how to complete the remaining two lines. All right, so once again, just let me just tell you the importance again. Once again, I'm trying to, what am I trying to do? I'm trying to get the price of using a non-uniform, not a key of entropy deficiency D. Happens to be really is enough, you know, but I could put entropy here. I want to see what is the price I have to pay if I have entropy deficiency D in the privacy application. And this is the kind of price that I pay. You know, sometimes the number will then accept to pre-large like a one-time pad, unfortunately, or something, but sometimes it will be low and we will see exactly when, okay? So is it too scary, I don't know if it's too scary or not, but does it make sense? So this is our new inequality. All right, so the way to prove it is like you just take this guy and you expand it by brute force. So this is pure pharma and as this times F of R, this is a common thing, you just take this. And of course, one, do you have something like that? It's like, you know, it's a dream of a mass high school geek student, you apply Koshish words. It's like all of us want to apply Koshish words in a paper. So I managed to achieve it, that's great. So it just applies as Koshish words. So it's not a textbook thing, it's actually useful for something. So, you know, I don't know, I normalize it in a way which is convenient for me. And then once you do this kind of thing, you start to see that this looks like expected value of M squared and this thing, if you do enough derivation, you know, there will be some of squares and that starts to relate to the collision entropy.  So not a hard proof, even though it didn't completely fit in the slide, but 50% of it fit in the slide, okay? All right, so this inequality hopefully is okay. So let's put it on the next slide. So why is it nice? All right, so I'm just repeating this inequality and why is it nice? All right, let's see. So it works even if F can be negative and as we'll see, that's what we'll need for indistinguishability applications. And the first, and now we have the separation of power, right? So the first term is independent of the application. So application is this function F. So function F is an intuitive advantage of the attacker or something like that. So this is just how good is our derived key. And this thing, and the second thing is only for uniform distribution. So we have the separation of power, it's like the stuff for the application we can analyze without worrying about the keys and the stuff about key derivation we can analyze without worrying about application, which is great, right? So that's exactly what we are looking for. And also like a small technical benefit that will improve some of our parameters. It's a nicer entropy, you know, we can work only for condensers so we don't need to derive a key with high mean entropy. We only need this rainy entropy, which just will be a small technicality. And rainy entropy came up because of this kosher Schwarz, so nothing super deep.  Okay, and so the only question remains, of course, well there are two questions remain, how do we achieve the small d? That will be a relatively simple question and you know, what is the price of achieving the various d's and so on. But the second question which is very bizarre is like, what is this guy? What is the expected, you know, so we know the expected value of f. Remember, you know, f was the advantage of the attacker on a particular key, you know, in an application so that we know by definition when the key is uniform, this is what we call epsilon. Right, so this is the advantage of f, but what is the expected value of f square? This is like a bizarre thing for which we don't have like before our sequence of papers, we didn't have an analog, it's something which didn't seem to be like naturally related to something. It's just, you know, came up in the proof, but now that it came up in the proof, we would like to understand this guy. All right, so this is going to be, I'll take questions if, you know, just to make sure if people are with me on a conceptual road. Yeah. So you say that the distinguishing, the indistinguishability kind of definitions are compatible with this framework? Yes, yes, well, yeah. If you go for like simulation-based definitions where you're also talking about differences between the real world and ideal world, I think so. It's like essentially this f, it encompasses the entire, well, actually, you know what I, okay, let me think about it. I'm not sure. I guess with simulation definitions, you have like 20 attackers that exist, a simulator. So, so I'm not, yeah, it's a good question. It's one of those things where I might say something wrong, so I, you know, I see that there might be some technical difficulty. Yeah, good question. So I'll try to maybe think offline and by tomorrow we'll give you the answer. But for now, I guess I'm only confident about like normal, you know, normal applications was not simulation-based, but, you know, game-based kind of definitions. Yeah. Yeah, we tried it and unfortunately it didn't come up, it didn't come up with anything. That was like the most obvious thing we tried it and I was sure there is something missing. I spent several hours to it, I couldn't get anything super useful. It still bothers me why this course is the only thing that seems to make a difference. I mean, we could kind of free derive some of the bounds, but we couldn't approve anything, so. But, you know, feel free to write because as I said, for me it was one of those things where, unfortunately, I wish I had like a deeper purpose of doing it, it's just it happened to be pretty kind of mechanically. And, but, you know, we kind of did it mechanically, but modularly, we said, okay, this is it, okay, let's, you know, not worry about the big picture. Let's look at this guy, what can we achieve? All right, like, plug in numbers, get it. Okay, let's forget about this, let's look about, so we kind of did it pedantically and we got those results, which hopefully occurred. But yeah, we, you know, we tried this holder, didn't seem to help us up now. All right, so let's try to answer this question. This is perhaps the most interesting and surprising thing. And as I said, I'm doing it slowly just because I don't have very good intuition about it. It's something that we just defined and just blindly followed and, you know, got the result. All right, so in cryptography, we have this paradigm. So when you're asking me about simulation paradigm, in cryptography, we have another paradigm which is different from mathematics that when there is something which we've never seen before, we give it a name and define it and then we state a theorem in terms of a new parameter, okay? And then hope that maybe some future work, in this case, it was our work itself, can understand this parameter better. So we give it a name, so we'll say it's square security. So we'll say that P is gamma, what is this letter, I don't know, sigma? Sigma square secure, again, is some class of attackers. Again, it's completely information theoretic. I mean, it works for both computation and information theoretic. If any attacker A, you know, if you look at the expected value of his square advantage, you know, the square of his advantage and you take expected value of this thing, it's at most gamma. So this is a definition, delta, whatever this is, sigma. All right, I think, I don't know, how many people know or did Goldrich or heard of a name or did Goldrich? Okay, only three, yeah, Goldrich, yeah. So he has a name for this. Whenever he has a Greek letter, which he doesn't know, he calls it agla. So I don't know if it's an official thing, but I'm just going through letters until I heed one of them. So, all right, sigma. Okay, so, and now we can state a lemma. You know, it has like one more letter, a lot of colors. So let's just see. It says that if P is epsilon secure and this new thing which we don't yet understand, sigma square secure, then P is epsilon secure with the model where we have entropy-deficient CD. So now I'm saying for any privacy application when the key has entropy-deficient CD, its real security is going to be the original security plus this thing, square root, and then there is this new guy which we just named sigma and this two to the D minus one. So this is what we have. You know, very simple proofs, very little intuition for now, but, you know, it's not too bad. All right, okay, let's see. So now, of course, it motivates this understanding this sigma security, the square security. And in particular, one thing we would like to do is not to reinvent the wheel and say, listen, there are all those smart people who started real security. Maybe we can just relate this sigma to epsilon in some natural way and then we'll be in a good shape. And indeed, that's fortunately what we managed to achieve. So, let me just see, okay. So we'll call this application square-friendly in case you don't understand this joke. So this is like black square of Malevich, is one of those famous paintings that Malevich managed to be lucky enough to have to be the first to draw it because I think a lot of us have the skill level to do it when we were born too late. And, you know, but not all museums are square-friendly, but Hermitage, I think, is square-friendly.  So now I'm explaining my joke, so it's deep. It's, okay. So we'll say that p square-friendly is essentially sigma is at most epsilon. There is some food nodes that, you know, it's okay when sometimes we can like, allow the attacker to be, you know, more powerful here than here, but not by much. You will see why a little bit, well, maybe you'll see why if you ask question, but now I'm like hiding it in the food node. Okay, so here is a simple application. All unpredictability applications. Unfortunately, so this paper came out before the papers that I presented with these balls and bins. So unfortunately, from predictability, we have this fantastic dream come true kind of bound, but at that time we didn't have it. And here is a very simple proof that if the function is non-negative, you know, and, you know, it's between zero and one, if this is like a predictability application, f square, a number, square between zero and one, it's like it's only smaller than the number itself. So it's trivial that sigma is at most epsilon. So in this case, you know, it's all unpredictability applications are square friendly. Unfortunately, the bounds that we get will be weaker than this. So, you know, we are not going to get a final improvement, but I mean, we will get actually something good with much simpler key derivation functions. That's what will be the case. There are some non-square free applications like one-time path PRF, PRP, PRG. I have this thing. So I don't know how much time do I have? I mean, we started a little bit late. So, I mean, I don't know if I should go into this kind of thing, so not, you know, this is like essentially just telling you that some applications are not square free, and then maybe let me tell you the next bullet, and then we'll see. So what we notice in this crypto paper and a follow-up PCC paper, that even though some applications like two random functions, PRG and PRFs, and one-time path are not square free, in particular, these applications, well, they better not be square free because we shouldn't get any improved security for these applications. For at least one-time path, we know. And indeed, for these applications, the sigma is one, unfortunately. So in this thing, I tell you why, but so the question is, is it horrible? Well, yeah, for one-time path, maybe it's horrible, but PRFs, PRPs, PRG, luckily it doesn't really matter because nobody uses them as object by themselves. They're only useful for like something else, like building Macs or encryptions. But as the end goal, nobody cares about them.  So this is like building blocks. So in our case, as long as we're having key for the final application, that's what we care about in the final applications, like, you know, so here, well, PRF may not be the final, but for the most importantly, standard, reusable encryption, not like one-time encryption, one-time path, but a computationally secure encryption, like KALGAMAL or, you know, like CBC encryption or something like that. Those applications are always square-friendly and that's like one of those like really surprising things. And in particular, so what does it mean that they're also square-friendly? It means, using our previous lemma, that let's say if I talk about, this is one of those things which like really surprised the hell of us initially. So you talk about one-time path, I told you, okay, if I give you a one-time path with entropy deficiency or key, with entropy deficiency one, there is no security. You can leak one bit of the message. But if you use, let's say, KALGAMAL encryption or, let's say, some computationally secure encryption which is computationally secure. So you can use it like multiple times, encrypt many messages. There, if I give you a key with entropy deficiency one, you cannot always lose security. So in this, you know, it actually is lost relatively gradually. So how gradually, just to tell you with entropy deficiency one, if my security is epsilon, it turns out the new security cannot be worse than square root of epsilon. So if it's like if my security is 2 to the minus 64, with one bit of entropy deficiency, it jumps to 2 to the minus 32, which is not fantastic, but it doesn't jump all the way to one, like one-time path, which is like nothing. So that was kind of a really surprising kind of thing. And of course, you can say, wait a second, what comes? So indirectly, part of the reason is that public or in general multi-reusable encryption, it has to use local randomness for every use. Because otherwise, if you encrypt zero twice, you would get the same result. So for these applications, the encryption scheme must be probabilistic just to ensure semantic security. So translated to our setting, when I say that my secret key has entropy deficiency one, I still assume that my local randomness is good. Right, I mean, I don't know, it's actually a great, possibly open area to see what happens if my local randomness is weak, but I'm not going there. But essentially for encryption, we kind of showed, well, even in the standard setting, it has to be probabilistic. So if the secret key has like one of few bits of entropy deficiency, but we still have this local randomness, which is anyway needed to render my ciphertext, the security cannot disappear right away. That was something which is kind of maybe obvious in retrospect, but I was kind of surprising, and that's why we got this kind of result. Yeah. That's a good question. So let me think about it. Some who I assume stateless, so let me just think if not based encryption.  So when we argue that encryption, CPA encryption is, yeah, so in the proof that the square security of CPA encryption is at most like real security, I kind of need to run that attacker twice. I mean, I have like slides about it. So I'm not sure how the state, so let me again, let me just think about it. Yeah, I think it's probably going to be a problem, but. Yes, I think so.  So even if you use state, you shouldn't be able to encrypt even one bit. So yeah, it didn't work. Yeah, just because, you know, listen, if it's, if it doesn't use local randomness, we are back to security with Viki, so yeah, you will not get any security. So that's actually, well, maybe people don't care, but yeah, that's maybe one reason. Usually deterministic encryption, aside from state is like preferable. There are all those like, no problem with randomness and so on. But randomness, but here, we have like one advantage of probabilistic encryption that it's security doesn't degrade if the key is not perfectly uniform. Well, for this deterministic encryption, you get this same jump as for one-time path.  Because, you know, I will need to run the attacker and you know, I will need to rewind the nodes, which I cannot do. Okay, so for now, maybe I'll keep the suspense. Possibly, Hugo will talk about it. If we have time or we have questions, I would love to show you as a suspense why this is the case. But just to connect with this thing, I think from the perspective of randomness, this is where local randomness is used. For all these applications, there is some kind of randomness in addition to the key. So like for CPCP encryption, there is like fresh randomness for big pseudo-random function. It's like pseudo-random function where the points that the attacker learns the value of the pseudo-random function are chosen at random. This is kind of yet another like local randomness that comes for free. So this is a little bit, I guess. Yeah, for Q, it's independent hash functions. I'll have to think about it. Or maybe it's just because of this factor of Q. Anyway, I'll take it offline, but yeah, there is the explanation why it doesn't contradict our result is in all these applications, natively, there is local randomness. So let me tell you what we get for these applications after we get these caveats. Oh, okay, good. I actually can almost tell you what we get. Well, so if you look at the previous slide, essentially we can put epsilon over here. And this is a new thing which will allow us like huge savings. That we can actually put epsilon instead of sigma. While traditionally for like one time pad, we can generally put only one here. And by putting epsilon, we get this huge savings that we can build actually condensers with non-trivial number. Because if you look here, if sigma is one, there is nothing, not much you can do because d will be at least like a little bit more than zero. So well, actually, there is something you can do. You can build a traditional extractor, but then d will have to be like really, really tiny, like very, very close to zero, like, you know, and that's exactly what we achieve. And here it turns out we don't need to achieve d like so small because we have this extra sigma which is equal to epsilon. So this is the philosophy. For these square friendly applications, we can achieve much, much higher values of d for our condenser. All right, so let me just kind of, we're almost there. Just I'll tell you the plan, but essentially now we need to build condensers and there is like a relaxation. We don't need to do it from an entropy like we did for authentication applications. We only need to do it for any entropy. And this is, if you haven't seen leftover hash lemma, this will be a better proof of leftover hash lemma, more general kind of. So this is my definition of universal hash functions. You know, for any two points of probability of collision, here I'm talking about perfect universal hash function, so it will be two to the minus output size and they are abundant and very easy to implement in hardware and so on. Like metrics, vector multiplication is one of them. So this is LHL, so this is essentially what leftover hash lemma states. I'm just going to translate it to my language. I'll say that universal hash family is a condenser for any entropy. I'm putting these two with very good parameters. So it's like a KD epsilon. So epsilon is like, it's not a close to mean entropy. It's actually gives you this mean entropy. So the derived key has entropy deficiency D, where remember we only care about this number two to the D minus one and two to the D minus one is equal to this number. So once again, so you get a condenser where the quality of the condenser, which is this number is two to the output length minus mean entropy. And this, I mean, I know it might be a lot of letters, but it's like conceptually, it's like a very clean statement. It's just as for any entropy, we have this perfect condenser where the quantity we care about, this is how it relates to our original mean entropy and the key that I want, the length of the key that I want. And the proof is like one line. What is the probability that you have a collision between H of X and H of X prime? For two independent samples, right? Because I need to look, my derived key is H of X. So let's derive it twice and see what is the probability of collision. Well, there are two choices. Either I'm unlocking X collides, well, that's two to the minus K, that's my real entropy. Or X is not equal to X prime, but the hash collides. But because the hash is universal, this is two to the minus M. That's it. And if you translate it back, if you just call this is equal to two to the minus D, whatever, you translate it back, you get this. So, oh, sorry. But remember what we would like to show is that this is equal to two to the D minus M by definition. So we get this and we get the bound. So this is a proof of leftover hash lemma if you haven't seen it. Okay, I mean stated in language of condensers, but of course, if you say D like so low, if this is like epsilon square, this two to the minus one is epsilon square, square root of epsilon square is epsilon. So you get the standard leftover hash lemma. Yeah, so, but this is really the hard, in the language of condensers, this is really what leftover hash lemma is saying. It's saying universal hash functions allow us to reduce entropy deficiency from possibly a huge gap of N minus K, where N and K are somewhere like really big numbers or something to essentially, this number two to the minus one is two to the M minus K. So if K is a little bit more than M, this is like a really tiny number. All right, so this is a corollary, all right? So if you lost me, I mean, hopefully you follow the concept. So let me tell you the punchline, all right? If P is epsilon secure and square friendly, like the case of encryption or authentication application, then the universal hash and family yields key derivation function whose security is original security plus square root of square security because the square friendly we put epsilon times this number that we got from leftover hash lemma. All right? So let's try to see, let's just put it over here. We have round three, we're almost there. I mean, if needed, I can stop actually here, close to here. So what do we have? Computationally security, we have entropy loss zero. Anything, we have two log one of epsilon using unpredictability condensers we saved, sorry, using unpredictability condensers, we got this really tiny number, but it's only for unpredictability applications. Here we have a wider class of application. It includes unpredictability applications, but it includes also some privacy implications including encryption, you know, chosen plaintiffs or chosen cyber tech secure encryption. And we say we still save a factor of two. Why is factor of two? Because if we want this to be equal to epsilon, we already have one epsilon to begin with. Here we didn't have that epsilon to begin with. That's why we needed two log one of epsilon. Here, because we have epsilon from square freeness, we only need log one of epsilon. So we save a factor of two in the leftover hash lemma. Right, so I'll put it here. Here by the way to complete it's the same, I mean, soundness kind of follows from this. So this will be like for the purposes of this table, at least from the perspective of key derivation, this would be like the, what local animals buys us. You know, extraction will achieve this entropy loss for some privacy amplifications including like encryption, we will save a factor of two. Fall on predictability, we get almost two zero and you know, the same kind of household soundness if you think about it because it's the same goal. So, and the function is here. So here, even for predictability applications, it might be useful because this function is much more efficient than this and you still save a factor of two. So it's actually a useful result, yeah. Which one, sorry? Oh yeah, yeah, so that's, there was a bullet. So that's actually slightly non obvious thing. So if there is interest, I'm totally happy to spend five minutes, I can do it now.  That's actually one of those things which is not obvious and it's like a really cute trick how to kind of argue. So for unpredictability, it was very easy. It just was like one line, right? The sigma square, you know, the square for privacy for encryption, there was a very cute trick which will take me five minutes to define. So it's not obvious. And there's a lot of surprises. So using the square free stuff, for example, you know, for the rest it might, but you know, I'll just tell it for the experts. We could apply it not just for computational things, we can apply it to like four ways independent hash functions. We applied the square free whatever the streak with square freeness. And what we got, we just like pedantically plugged in things, we didn't know what we get, we were looking for more applications and we solved like an open problem. We built something called like non-malable extractor which was like an open problem in my previous paper on like privacy amplification. And some who completely surprising, it was like totally syntactic, I didn't want to build non-malable, I mean, I wanted to build it, I didn't know how.  We looked at other applications where it doesn't like syntactically, we just built non-malable extractor, for example. And now there are much better non-malable extractors, but that was like the first non-malable extractor we explicit, oh, the second, yeah, so we had a paper at fault, this like some complicated guy and this was like totally elementary. So yeah, it was like very surprising powerful framework, but yeah, if we have time at the end, I'll be very happy to show you the streak. Yeah, yeah, or I can do it offline, of course, I'm here until Friday, so should be good. So yeah, so this is kind of the picture concentrating on this kind of thing. Okay, so yeah, like in terms of theory versus practice, so it's not as great, but if I want to do CBC encryption as my final application, with leftover hash lemma, we need entropy 256, heuristically 128, so here we like stuck in the middle. But it's still not bad because it's for free. It's like using the same key derivation function that people use with leftover hash lemma, we just say, oh, you know, it's the same kind of thing, but a more careful proof shows you that you don't need as much entropy, you can need only like half the amount of entropy over here. And so in the last five minutes, if I could stop here, I was going to just throw away this remaining two points. So I did this, I wanted to just tell you very quickly about these two points just in a few minutes and hopefully we'll be done. So what about efficient simplability, right? So maybe we can actually have additional saving if the source is known to be efficiently sampleable as opposed to arbitrary. So here, unfortunately, we have a negative result. We show at least efficient simplability does not help to improve entropy loss below, so for general application, this RT bound, it was information theoretic, but we strengthened this definition of Tashmallow bound for extractors that we showed that even for any candidate extractor, which claims to achieve better than two to log one of epsilon entropy loss, we can give an efficient resource that could fool it. And the efficient sample of source some kind of full waste independent, whatever, and that affirmative results is a sampleable Radakrishnan-Tashmak conjecture from Huga et al paper. So Huga might talk about it on Thursday, I think, Huga-Kravchik. So also for square friendly applications, unfortunately, yeah, we cannot get better than log one of epsilon. I mean, it's great that we saved the factor of two in entropy loss, but we cannot, at least in this level of generality, go below it. And also from predictability applications in this level of generality, we cannot go it. I mean, you'll have to make some kind of more assumptions, but efficient sampleability by itself, unfortunately, is not enough. So this is kind of a negative result. Yeah, and essentially the idea is in all those, you know, before efficient sampleability, you usually pick like a random source under the constraint and it turns out for this proof some kind of bounded twice independence is still kind of enough. But yeah, those proofs were super painful. So, you know, I'm hiding a lot on the three dots, but... So what's in your mind? Oh, counter example? Sorry. It's an old paper with Krzysztof and Daniel Vicks at Eurocript 2013. Or maybe it's 14, I think the slides are old. So I think it was right after we submitted the paper. But yeah, I think it's Eurocript maybe 2014. All right, so this is our table. This just shows optimality of these numbers that we cannot in this level of generality improve these numbers. All right, so final kind of things that I want to just tell you a little bit and maybe that would be a perfect transition to Leo's thing because Leo is going to talk about computationally bounded distinguishers or what is known as pseudo-randomness. So maybe we just want pseudo-random as we can do stuff. And here we have a mix of positive and negative results. The first thing is kind of I'll mention it briefly. So what is guys whose conjecture we proved? This shows that SRT conjecture implies so if you want to build the Sardakrishnan-Tashma bound for all computationally bounded D, then you need one-way function. So in principle, if one-way function is this, we know we can beat this RT bound because at least for like large enough entropy you can extract anything and then apply pseudo-random generator and get a lot of pseudo-random bits. But that of course requires computational assumptions and it kind of shows that, well, it's kind of inherent. This kind of applying something of pseudo-random generator to something shorter that you extract is kind of inherent. But this of course was only true under this conjecture but luckily because this is no longer conjecture and theorem we do show this just kind of unconditional that you need computational, so this is kind of you can view it as a negative result, you need computational assumptions like one-way functions to beat the Sardakrishnan-Tashma bound. So how far can we go with this thing? So Huga is going to talk about it. So this is just a summary, I'm stealing thunder from those talks but it's just like literally two slides so I'll just tell you high level points and those guys will go in much more details. So we beat this, I told you that if we have something we can first extract, loses two log of an absolute entropy and if there is enough to apply pseudo-random generator if we are left with one or two bits it's not enough to apply pseudo-random generator but if it's enough we can apply pseudo-random generator to arbitrarily expand the output and have like no entropy loss and all those kind of thing but we need to start enough to be able to lose this two log one of epsilon. So this is kind of the thing and there is also this thing that Liu is going to talk about this is something called dense model theorem it says you know what let's do the converse instead of like first extracting and applying pseudo-random generator let's do the following, we have this thing which is short but you know, but it's at least security parameter but it's just non-uniform we have a key which is non-uniform let's expand it using a pseudo-random generator first and then apply extractor and I hope this kind of works but unfortunately Liu is going to talk about that there is this really horrible runtime degradation and the reduction so it's a beautiful result but it's not applicable to any kind of realistic setting of parameters but it's a beautiful result in theory but it will not apply to anything and maybe Liu will contradict but you know, it never gives you anything kind of practically useful but it's a beautiful result but you know, maybe I'm wrong this is, I mean it's not a criticism it's just a beautiful kind of thing so what we kind of did and it was really surprising this will be like a nice transition to this computational thing so what we did is that you know what we didn't think about necessarily this approach but we said can we design a square-friendly key-derivation function and if it's square, I mean it will be computational so we'll derive a key-derivation function with ideal randomness, right so we'll have a ideal randomness we'll do a key-derivation function with ideal randomness and if it's square-friendly then we know that this will be good enough even when we have an entropy deficiency so the solution was kind of the following we are going to so this is our key-derivation function so we'll use it, you know it's enough to use only a big pseudo-random function and this is important because otherwise it's not square-friendly so this is our key-derivation function we take our source and here we assume the source is perfectly uniform this is the beauty of our technique we derive a bound for perfectly uniform source and then because it's square-friendly we get something even if the source is not perfectly uniform so we set R to be applying this pseudo-random function with our key to a random c-desk because it's a big pseudo-random function the c-desk is going to be, you know it's chosen at random so the big PRF says it's secure for random but public input says so this is pseudo-random, right so if F is a good pseudo-random function and X is truly uniform this is a good key-derivation if I tell you S if the key is secret the output is pseudo-random so this is exactly what a big pseudo-random function is and because, and it's important because otherwise it won't be pseudo-random you know, square-friendly but likely randomness is enough here so that's good so in order to apply, unfortunately you don't see it because I hid this kind of question about how to argue square-friendly but in order to show that this is a good square-free application I need big PRF to be so if I need to be secure again it's one query with a big key I need its ideal security to be secure with two queries just believe me this is kind of the price you have to pay for this square-friendliness and and we can actually, instead of just using a full-fledged PRF we can easily build it from a pseudo-random generator so I have this bullet over here and maybe, alright just because Leo is here I'll show you the bullet I apologize, I'll literally finish in one minute or two minutes, alright so sorry for taking extra but I really like it and I know Leo told me that he will talk about dense model theorem so let me talk about it here so this is this new dense model theorem so I'm going, my goal is you know, I'm just going to apply what I did on the previous slide but I'm going to build explicitly a pseudo-random function which is secure again is two random points so what is, how to build it like that so alright, so sorry, okay so I'll start with a different question because that was supposed to be self-contained so how to build a pseudo-random generator with big seed? so naive thing is just apply it with whatever they're saying and hope it's good but we already know on the example of one-time path, a simple generalization this is not going to fly the moment you lose one bit of entropy deficiency PRGs are not square-friendly you know, in this level of generality it's not going to work so what dense model theorem says it says that if you apply g of x even though it's not pseudo-random it's like longer right now but the output has pseudo-entropy much bigger than the input length so essentially you take this input it has entropy deficiency you expand it right and you actually sum it all close to something which is the same entropy deficiency but now lengths to m this is what dense model theorem kind of says and that's what Leo is going to prove over there and now you can say, you know what 2m-d is much bigger than m so we can apply a regular extractor and if you wish, I can also apply g on top of it afterwards anyway so this is going to be pseudo-random so the problem is in this standard application so dense model theorem is this horrible degradation in the running time so here is our version which is like very simple it says that if even really, you know, we will prove even the rainy entropy of the sources as the entropy deficiency is d so here is what we can do we can build, so this construction is a weak pseudo-random function secure with two queries but this is a specific construction you take the source here you assume it's perfectly uniform you expand it you view it as a key of a perverse independent hash function and you apply it with this seed s and it turns out, you know, it's easy to see that this is going to be secure again it's two queries and it's easy to see that this is pseudo-random even given s yeah, so this is kind of, as I said this is our kind of weak PRF you can easily check that the thing inside is a weak pseudo-random function and there is no degradation in the running time maybe a factor of two but the price we pay in the original weak dense model theorem you get this perfect security degradation you only lose d bits in security here we also pay with the square root so I probably lost most of you here so I don't know, maybe Leo will pick it up so my point is so this is what I wanted to say so what this dense model theorem says it says that if I have something which is if the pseudo-random generator is not perfectly random but has entropy deficiency once I expand it, I get a longer string and dense model theorem says that the entropy deficiency is kind of the same or at least I'm close to the same entropy deficiency so now I can apply extractor and get whatever I want and so on and essentially there are these two surprising proofs for the same construction this is a general proof using the traditional dense model theorem and we have this proof using our kind of square, free, whatever you know, two-query, weak PRF kind of thing and you look at it and they are like very similar because this is it's very easy to see that this particular construction is pairwise independent sorry, it's a good extractor so this follows from leftover hash lem or something so we have syntactically two very similar constructions with very different proofs and you know, they're kind of incompatible we give good T but we lose in security but still give some security they achieve the best security you can hope so you lose debits in the entropy you lose debits in security but you know, the running time degradation doesn't make it applicable to a real life situation so it would be great to kind of find a common proof you know, to have this symbol unified proof anyway, in case I lost you guys this was slightly before the transition to Leo he can debunk my claims over there so I'll come back to this kind of thing so and I'll just mention the great open question this is a really good time to finish this is my last technical slide before the summary so this is our round five last round I'll stop here so let me see what we get let's just summarize so we're concentrating on this kind of thing and this is a number that you just trust me as I follow from this, you know, derivation so ideally you have entropy loss zero here for any applications we have this two log one of epsilon we have some predictability entropy loss very, very small but only from predictability for a wider class of square friendly we have log one of epsilon but what if you want computational security using our proof of this new modified dense model theorem we can use any pseudo random generator and this is the kind of entropy loss we get and for applications where epsilon PRG is comparable to epsilon this will be like another log one of epsilon so this is a security of any original application whatever application we want you know this could be like a PRF or one time pad or whatever but of course it has to be computationally secure we only get computational security at the end and using auxiliary pseudo random generator we can kind of get the following this kind of entropy loss so and it's a great open question of course for computational security in this level of generality computationally secure, computationally secure we still have this kind of gap so I think this is like a really great open question I think so I mentioned like three open questions that I like in different parts of the in different three hours for the first hour I personally like really this question about IP with one block source interactive protocol with verifier having one weak source my conjecture is it should be impossible to do for the second part I showed you you know the question was does secret sharing inherently require two randomness and here my kind of fascinating question is for computationally secure applications possibly using a new trick well definitely using a new trick can we actually come closer to matching the entropy loss of heuristic thing so here we make some improvements using computational assumptions the improvement is this factor of epsilon PRG over here in the entropy loss so essentially this like epsilon PRG we assume like a yes encounter mode is like two to the minus 64 secure we like save 64 bits in entropy deficiency or something like that so we do get this non-trivial saving which is great I mean the question is can we improve it I think this is like a really fascinating open question if computational extractors can get us closer to this dream bound yeah you mean like which one sorry yeah so I mean it just comes from this kosher Schwartz well there is something because I mean if I go very quickly back you know so in this bound I told you for this theorem you know well I mean it doesn't directly answer square root but at least in terms of this entropy deficiency in this level I mean it doesn't maybe there is a different kind of proof and maybe you don't follow square freeness yeah and this application this example it wasn't for encryption it was for some super artificial square friendly application that we designed just for the purpose of this thing so maybe for encryption you couldn't do something better it's actually it's a great question maybe it's like yeah there is a better analysis for encryption so just to conclude sorry for taking a little bit longer so this is like the third open question if you can do something better so this was kind of a road from heuristic to you know kind of how to do stuff in the middle so anyways there is a difference between so if you want to get the message for this third part there is a difference between extraction and key derivation we get this fantastic entropy loss from predictability applications save a factor of two for square friendly application we motivate the square security for which I'm sure I would like to understand it better it's I don't think anybody looked at it it's like a bizarre notion by itself the square you know expected value of the square of advantage over like choice of I don't know choice of key so it still confuses me a little bit so and then there are a few more observations efficiency of the ability doesn't help good computational KDFs require one-way functions and of course a great open question is this is like what I really like better computational KDFs close to theory versus you know so can we close the theory versus practice gap in the further now maybe we kind of saved like 64 bits you know by using this new dense model of theorem but it would be great to to get more so I think that's where I stop sorry for taking a little bit more time