Over the years many natural cryptographic constructions were found to be insecure. In response, modern cryptography was developed as a rigorous science where constructions are always accompanied by a proof of security. The language used to describe security relies on discreet probability. In this segment and the next, I'll give a brief overview of discreet probability, and I point to this Wiki books article over here for a longer introduction. Discrete probability is always defined over a universe which I'll denote by u and this universe in our case is always going to be a finite set. In fact very commonly our universe is going to be simply the set of all n bit strings which here is denoted by zero one to the n. So for example the set zero one squared is the set of all two bit strings which happens to be the string zero, zero, zero one, One, zero, and one, one. So there are four elements in this set, and more generally in the set zero one to the N, there are two to the N elements. Now a probability distribution over this universe U is simply a function which I'll denote by P, and this function, what it does, is it assigns to every element in the universe a number between zero and one. And this number is what I'll call the weight or the probability of that particular element in the universe. Now there's only one requirement on this function P, and that is that the sum of all the weights, sum up to one. That is, if I sum the probability of all elements X in the universe, what I end up with is the number one. So let's look at a very simple example looking back to our 2-bit universe. So 0001, ten and eleven And you can consider the following probability distribution Which, for example, assigns to the element 00, the probability one half. The elements 01, we assign the probability 1/8th, to ten we assign the probability one quarter and to eleven we assign the probability 1/8th. Okay we can see that if we sum up these numbers in fact we get one which means that this probability P is in fact the probability distributio N. Now what these number mean is that if I sample from this probability distribution I'll get the string 00 with probability one half I'll get the string 01 with probability 1/8th and so on and so forth. So now that we understand what a probability distribution is, let's look at two classic examples of probability distributions. The first one is what's called the uniform distribution. The uniform distribution assigns to every element in the universe, exactly the same weight. I'm gonna use U between two bars to denote the size of the universe U. That is the number of elements in the universe, and since we want the sum of all the weights to sum out to one, and we want all these weights to be equal, what this means is that for every element X in the universe, we assign a probability of one over U. So in particular if we look at our example, the uniform distribution and the set of two [inaudible] strings, would simply assign one-quarter the weight, one-quarter to each one of these strings And clearly that, the sum of all the weights sums up to one. Well again, what this means is that if I sample at random from this distribution, I'll get a uniform sample across all our 2-bit strings So all of these 4-bit strings are equally likely to be sampled by this distribution. Another distribution that's very common is what's called a point distribution at the point X0 And what this point distribution does is basically it puts all the weight on a single point, namely X0. So here we assign to the point X0 all the weight, one And then to all other points in the universe, we assign the weight zero And by the way, I want to point out that this, inverted, A here should be read as, for all. So all this says is, that for all X that are not equal to X zero, the probability of that X is zero. So again going back to our example a point distribution for example, that would put all its mass on the string 1-0, would assign probability one to the string 1-0 and zero to all other strings. So now if I sample from this distribution pretty much I'm always guaranteed to always sample the string 1-0 and never sample any of the other strings. So now we know what a distribution is, and I just want to make one last point, and that is that because this universe U is always gonna be a finite set up for us, we can actually write down the weights that the distribution assigns to every element in U, and represent the entire distribution as a vector. So, here for example, if you look at the universe of an all 3-bit strings, we can literally write down the ways that the distribution assigns to the string 000, then the way that distribution assigns to the string 001 And so on, and so forth. We you can see that we can write this as a vector, in this case it will be a vector of dimension eight, there will be, there are eight strings of 3-bits as a result basically the entire distribution is captured by this vector of eight real numbers, in the range of all zero to one. The next thing I wanna do is define the concept of an event. So consider a subset A of our universe And I, I'll define the probability of the subsets to be simply the sum of the weights of all the elements in the set A. In other words, I'm summing over all X and A, the weights of these elements X in the set A, Now because the sum over the entire universe of all weights needs to be one. This means that if we sum, well if you look at the probability of the entire universe, basically we get one. And if we look at the probability of a subset of the universe, we're gonna get some number in the interval zero to one And we say that the probability of this set A, is the sum which is a number between zero and one. And I'll tell you that a subset A of the universe is called an event. And the probability of the set A is called the probability of that event. So let's look at a simple example. So suppose we look at the universe u, which consists of all 8-bit strings, right? So the size of this universe u is 256 because there are 256 8-bit strings. Essentially we're looking at all byte values, all 256 possible byte values. Now let's define the following event. Basically the event is gonna contain all bytes so all [inaudible] extremes in the universe such that the two least significant bits of the byte happens to be eleven So for example, if we look at 01011010 that's an element in the universe that's not in the set A, but if we choose a zero to a one. Then that's an element of the universe which gives in our set A. And now let's look at the uniform distribution over the universe U and let me ask you what is the probability of the, of the event A? So what is the probability that when we choose a random byte, the two least significant bits of that byte happens to be one, one? Well the answer is one-fourth, and the reason that's true is because it's not too difficult to convince yourself that of the 256 eight bit strings, exactly 64 of them, one quarter of them, end in one, one. And the probability of each string is, we're looking at the uniform distribution or probability of each string is exactly one over the size of the universe, mainly one over 256. And the product of these, you know, 64 elements, each one has weight one over 256 is exactly one-fourth, which is the probability of the event A that we're looking at. So a very simple bound on the probability of events is called the union bound. So imagine we have two events a1 and a2. So these are both subsets of some universe U Snd we wanna know what is the probability that either A1 occurs, or A2 occurs In other words, what is the probability of the union of these two events? This little U here denotes the union of the two sets. So the union bound tells us that the probability that either A1 occurs or A2 occurs is basically less than the sum of the two probabilities. And that's actually quite easy to see. So simply look at this picture here, you can see that when we look at, at the sum of the two probabilities, we're basically summing the probability of all the elements in A1, all the elements in A2 And you realized, we kind of double-summed these elements in the intersec tion. They get summed twice here on the right hand side And as a result, the sum of the two probabilities is going to be larger or larger than or equal to, the actual probability of the union of A1 and A2. So that's the classic union bound And in fact I'll tell you that if the two events are disjoint, in other words they're intersection is empty, in that case if we look at the sum, at the probability that either A-1 or A02 happens, that's exactly equal to the sum of the two probabilities. Okay? So we'll use these facts here and there throughout the course. So just to be clear, the inequality holds always But when the two events are disjoint, then in fact we get an equality over here. So let's look at a simple example. Suppose our, event A1 is the set of all n-bit stings that happen to end in 1-1 And suppose A2 is the set of all n-bit strings that happen to begin with 1-1. Okay, so N thinks of it as H or some large number and I'm asking that what is the probability that either a one happens or a two happens, In other words if I sample uniformly from the universe U, what is the probability that either the least significant bits are one, one or the most significant digits are one, one. Well as we said that's basically the probability of the union of A1 and A2. We know that the probability of each one of these events is one-quarter by what we just did previous slide And therefore by the union [inaudible] the probability of the [inaudible]. Is, you know, a quarter of the probability of A1, plus the probability of A2, which is a quarter plus a quarter. And we just proved that the probability of seeing 1-1 in the most significant bit, or 1-1 least significant bit, is less than one-half. So that's a simple example of how we might go about using the Union Bound to bound the probability that one of two events might happen. The next concept we need to define, is what's called a random variable. Now, random variables are fairly intuitive objects. But unfortunately the formal definition of a random variable can be a little c onfusing. So what I'll do is, I'll give an example, and hopefully that will be clear enough. So formally, a random variable denoted say, by X. Is a function, from the universe into some set V And we say that this set V is where the random variable takes its values. So let's look at a particular example. So suppose we have a random variable x And this random variable maps into the set 01. So the values of this random variable are going to be either zero or one. So, one bit, basically. Now, this random variable maps our universe, which is the center of all end bit binary strings, 01 to the end And how does it do it? Well, given a particular sample in the universe, a particular end-bit string y. What the random variable will do is simply output the least significant bit of y And that's it. That's the whole random variable. So, now let me ask you. Suppose we look at a uniform distribution on the set zero one to the end. Let me ask you what is the probability that this random variable output zero and what is the probability that a random variable outputs one? Well you can see that the answers are half and half. Well let's just lead them through why that's the case. So here we have a picture showing the universe and the possible alpha space. And so in this case the variable can output a zero or a one. When there is a variable output zero, there is a variable output zero when the sample in the universe happens to be, to have its least inefficient [inaudible] bid be set to zero. In variable one, output one When the sample in the universe happens to have its least significant bit set to one. Well, if choose strings uniformly at random, the probability that we choose a string that has its least significant bits set to zero is exactly one half Which the random variable output zero with a probability of exactly one-half. Similarly, if we choose a random end-bit string, the probability that the least significant bit is equal to one is also one-half. And so we say that the random variable output's one, also with exactly proba bility of one-half. Now, more generally, if we have a random variable taking values in a certain set v, then this random variable actually induces a distribution on this set v. And here, I just wrote a, kind of a, in symbols, what this distribution means But it's actually very easy to explain. Essentially, what it says is that the variable outputs v Basically, with the same probability that if we sample a random element in the universe, and, and then we apply the function x. We ask, how likely is it that the output is actually=to v? So formally we say that the probability that X outputs V, is the same as the probability of the event That when we sample a random element in the universe, we fall into the pre image of V under the function X And again, if this wasn't clear, it's not that important. All you need to know is that a random variable takes values in a particular set V, and in, induces a distribution on that set V. Now there's a particularly important random variable called a uniform random variable. And it's basically defined as you would expect. So let's say that U is some fine [inaudible] set For example the set of all N bit binary strings, and we're gonna denote a random variable R that's basically sample's uniformly from the set U by this little funny arrow with a little R on top of it. In this, again the notes that the random variable R is literally a uniform random variable sampled over the set U. So in symbols what's this means is that for all elements A in the universe, the probability that R is equal to A is simply R one over U. And if you want to stick to the formal definition of a, of a uniform variable, it's not actually that important But I would just say that formally the uniform random variable is an identity function namely R [inaudible] is equal to X for all X in the universe So just to see that this is clear, let me ask you a simple puzzle. Suppose we have a uniform random variable over 2-bit strings, so over the set, 01, ten, one and now, let's define a new random variable X to basicall y sum the first and second bits of R. That is, X simply is the sum of R1 and R2, the first and second bits of R, treating those bits as integers. So, for example, if, r happens to be 00, then x will be zero+0, which is zero. So let me ask you, what is the probability that x is = to two? So it's not difficult to see that the answer is exactly, one-fourth because, basically the only way that x is equal to two is if r happens to be 1,1 but the probability that r is equal to 1,1 is basically one-fourth because r is uniform over the set of all two bit stings. The last concept I want to define in this segment is what's called a randomized algorithm. So I'm sure you're all familiar with deterministic algorithms. These are algorithms that basically take a particular, input data, as input, and they always produce the same output, say Y. So if we run the algorithm a hundred times on the same input, we'll always get the same output. So you can think of a deterministic algorithm as a function that given a particular input data, M, will always produce exactly the same output, A of M. A randomized algorithm is a little different, in that, as before, it takes the [inaudible] and as input, but it also has an implicit argument called R, where this R is sampled anew every time the algorithm is run. And in particular this R is sampled uniformly at random from the set of all N-bit strings, for some arbitrary end. Now what happens is every time we run the algorithm on a particular input M we're gonna get a different output because a different R is generated every time. So the first time we run the algorithm we get one output. The second time we run the algorithm a new R is generated and we get a different output. The third time we run the algorithm a new R is generated and we get a third output and so on. So really the way to think about a randomized algorithm is it's actually defining a random variable. Right? So given a particular input message, M, it's defining a random variable which is, defining a distribution over the set of a [laugh] possible outputs of this algorithm, given the input, M. So the thing to remember is that the output of a randomized algorithm changes every time you run it And in fact, the algorithm defines a distribution and the set of all possible outputs. So let's look at a particular example. So suppose we have a randomized algorithm that takes as input a message M And of course it also takes an implicate input which is this random string that is used to randomize its operation. So now what the algorithm will do is simply will encrypt the message M using the random string as input. So this basically defines a random variable. This random variable takes values that are encryptions of the message M And really what this random, random variable is it's a distribution over the set of all possible encryptions of the message M under a uniform key. So the main point to remember is that even though the inputs to a randomized algorithm might always be the same every time you run the randomized algorithm you're gonna get a different output. Okay So, that concludes this segment, and we'll see a bit more discrete probability in the next segment.
