0:00

In the next three segments we will change gears a little bit and talk about the

Â definition of a PRG. This definition is a really good way to think of a PRG. And we

Â will see many applications for this definition. So consider a PRG with

Â keyspace A that ouputs N bit strings. Our goal is to define, what does it mean for

Â the output of the generator to be indistinguishable from random? In other

Â words, we're gonna define a distribution that basically is defined by choosing a

Â random key in the keyspace. Remember that a arrow with R above it means choosing

Â uniformly from the set script K. And then we output, basically, the output of the

Â generator. And what we'd like to say. Is that this distribution. This distribution

Â of pseudo random strings is indistinguishable from a truly uniform

Â distribution. In other words, if we just choose a truly uniform string in 01 to the

Â N and simply output this string, we'd like to say that these two distributions are

Â indistinguishable from one another. Now if you think about it, this sounds really

Â surprising because if we draw a circle here of all possible strings in 01 to the

Â N, then the uniform distribution basically can ouput any of these strings with equal

Â probability. That's the definition of the uniform distribution. However a

Â pseudo-random distribution generated by this generator G. Because the seed space

Â is so small, the set of possible outputs is really, really small, it's tiny inside

Â of, 01 to the N. And this is really all that the generator can output. And yet,

Â what we're arguing is that an adversary who looks at the output of the generator

Â in this tiny set can't distinguish it from the output of the uniform distribution

Â over the entire set. I think that's the property that we're actually shooting for.

Â So to understand how to define this concept of indistinguishability from

Â random, we need the concept of a statistical test. So, let me define what a

Â statistical test on 01 to the N is. I'm gonna define these statistical tests by

Â the letter A. And the statistical test is basically an algorithm that takes its

Â inputs and N bit string, and simply outputs zero or one. Now I'll tell you

Â that zero, we're gonna think of it as though the statistical test said, the

Â input you gave me is not random. And one, we're going to think of it as saying that

Â the imput you gave me actually is random. Okay, so all this statistical test does is

Â it basically takes the input x that was given to it, the n bit string that was

Â given to it, and decides whether it looks random or it doesn't look random. Let's

Â look at a couple of examples. So the first example basically will use the fact that

Â for a random string, the number of zeros is roughly equal to the number of ones in

Â that string. In other words, the statistical test is going to say one. If

Â and only if basically the number of zeros in the given string X minus the number of

Â 1's in the given string X. These numbers are not too far apart. In other words, the

Â difference between the number of 0's and the number of 1's. Let's just say is less

Â than ten times square root of n. Okay If the difference is less than ten times, the

Â statistical test will say hey the string X looks random. If the

Â difference happens to be much bigger than ten times square root of n, that starts to

Â look suspicious and the test, hey the string you gave me does not

Â look random. A statistical test. Let's look at another similar example. We'll say

Â here, the statistical test will say one. If and only if say the number of times

Â that we have two consecutive zeros. Inside of X. But let's think about this for a

Â second. This basically again counts. In this string of, n bits. It counts a number

Â of times that we see the pattern zero, zero. Two consecutive zeros. Well for a

Â random string. We will expect to see 0,0 as probability one fourth. And there for

Â in a random string. We'll expect about N over four 0,0's. Yeah, N over four blocks

Â a 0,0. And so, what the statistical test will do is it will say, well, if the

Â number of zero zeros is roughly N over four. In other words, the difference

Â between the number and N over four, is, say, less than ten square root of n,

Â then we will say that X looks random. And if the gap is much bigger than N over

Â four, we'll say, hey, this string doesn't really look random. And then the

Â statistical test will output zero, okay? So here are two examples of statistical

Â tests that basically, for random strings, they will output one with very high

Â probability. But for strings that, you know, don't look random, for example,

Â think of the all zero string. So the all zero string, neither one of these tests

Â will output, one. And in fact, the all zero string does not look random. Let's

Â look at one more example of the statistical test just to kinda show you

Â the, basically statistical test can pretty much do whatever they want. So here's the

Â third example. Let's say that statistical test output one if an only if I say the

Â biggest blocks what we'll call this the Maximum Run of zero inside of the string

Â x, this is basically the longest sequence of zero inside of the string x. In a

Â random string you expect the longest sequence of zeros to be roughly of length

Â log N. So we'll say if the longest sequence of zero happens to be less than

Â ten times log N Then this test will say that X was random. But if, all of a

Â sudden, we see a run of zeros that, say, is much bigger than ten log N, then the

Â statistical test will say, the string is not random, okay? So this is another crazy

Â thing that the statistical test will do. By the way, you notice that if you give

Â this test, the all one string. So one, one, one, one, one. This test will also

Â output one. In other words this test will think that the all one string is random.

Â Even though it's not. Yeah, even though one string is not particularly random.

Â Okay, so statistical tests don't have to get things right. They can do whatever

Â they like. They can test, they can decide to output random or not. You know, zero or

Â one, however they like. And similarly, there are many, many, many, many other

Â statistical tests. There are literally hundreds of statistical tests that one can

Â think of. And I can tell you that in the old days, basically, the way you would

Â define. That something looks random. As you would say, hey, here's a battery of

Â statistical tests. And all of them said that this string looks random. Therefore,

Â we say that this generator that generated the string is good generator. In other

Â words, this definition, then, uses a fixed set of statistical tests, is actually not

Â a good definition for security, but more generally, for crytpo. But before we talk

Â about actually defining security, the next thing we talk about is how do we evaluate

Â whether a statistical test is good or not? So to do that, we define the concept of

Â advantage. And so let me define the advantage. So here we have a generator

Â that outputs N bit strings. And we have a statistical tests on N bit strings. And we

Â define the advantage of this generator, as denoted by advantage sub PRG,

Â the advantage of the statistical test A relative to the generator g. I'll define

Â it as follows, basically the difference between two quantities. The first quantity

Â is basically, we ask how likely is this statistical test to output one. When we

Â give it a pseudo random string just like here K is chosen uniformly from the C

Â space we ask how likely is the statistical test to output one when we give it a

Â pseudo random output generated by the generator verses now we ask how likely is

Â the statistical test to output one when we give it a truly random string. So here are

Â is truly random in zero random one to the n. Okay, and yeah. We look at the

Â difference between these two quantities. Now you realize because these are

Â differences of probabilities this advantage is always going to lie in the

Â interval zero, one. So let's think a little bit about what this advantage

Â actually means. So first of all if the advantage happens to be close to one. Well

Â what does that mean. That means that somehow, the statistical test A behaves

Â differently when we gave it pseudo-random inputs, when we gave it the output of the

Â generator, for when we gave it truly random inputs, right? It somehow behaved

Â differently. In one case, it output one with a certain probability. And in the

Â other case, it output one with a very different probability, okay? So somehow,

Â it was able to behave differently. And what they really means is that the

Â statistical test could basically distinguish the output of the generator

Â from random. Okay, so in some sense we'll say that this statistical test broke the

Â generator G because it was able to distinguish the output from random.

Â However if the advantage is close to zero Well what does that mean. That means that

Â basically the statistical tests behaves pretty much the same on pseudo random

Â inputs. As it does on truly random inputs. And basically there we would say that A

Â could not distinguish the generator from random. Okay, so this sum gives you a

Â little bit of intuition about why this concept of advantage is important. It

Â basically tells us whether A was able to break the generator, namely distinguish it

Â from random, or not able to break it. So let's look, first of all, at a very silly

Â example. Suppose we have a statistical test A that simply ignores its inputs and

Â always outputs zero. Okay. Always output zero. What do you think of the advantage

Â of this statistical test relative to a generator G? So, I hope everybody

Â say the advantage is zero, let me just explain, why that's the case,

Â well, if the statistical test, always outputs, zero, that

Â means, pseudo random inputs, it will never output one, so, the probability that

Â outputs one, is zero. Similarly, when we give a truly random input, it still will

Â never output one, and, so, the probability that outputs one, is zero,

Â and, so, zero minus zero is zero, so, its advantage is zero, so, basically, and, a

Â statistical test that ignores its, its input, does not able to distinguish, truly

Â random inputs, from, a pseudo random input, obviously. Okay, now let's look at

Â a more interesting example. So suppose we have a generator G that satisfies a funny

Â property. It so happens that for two-thirds of the keys The first bit

Â of the output of the generator happens to be one, okay? So if I choose a random key

Â with probability two-thirds, the generator will output one as its first bit, okay? So

Â that's the property of the generator that we're looking at. Now, let's look at the

Â following statistical test. The statistical test basically says, if the

Â most signifigant bit of the string you gave me is one, I'm gonna say one, meaning

Â I think it's random. If the most signigant bit of the stream you gave me is not one,

Â zero, I'm gonna say zero. Okay so now my question to you is what is the

Â advantage of this statistical test on the generator G? Okay, so remember I just

Â wrote down the definition here again. And I'll let you think about this for a

Â second. So let me explain. Suppose we give the statistical tests pseudo random

Â inputs. By definition of G, we know that with probability two-thirds, the first

Â bits in the inputs will start with the bit one. But if it starts with a bit one, then

Â the statistical test will output one. In other words, the probability that this

Â statistical test outputs one is exactly two-thirds. Now let's look at the case of

Â a random string. If I give you a random string, how likely is it that the most

Â signifigant bits of the random string is one? Well, for a random string, that

Â happens exactly half the time, and so in this case the statistical test will output

Â one, with probability one-half. And so the overall advantage is one-sixth, and

Â one-sixth is actually a non-negligible number, that's actually a fairly large

Â number, which basically means that this a was able to distinguish the output. We'll

Â say that a breaks the generator G with advantage 1/6. Okay, which basically

Â means that this generator is no good, is broken. Okay, so now that we understand

Â what statistical tests are, we can go ahead and define, what is a secure

Â pseudo-random generator. So, basically, we say that, as generator G is secure, if

Â essentially no efficient, statistical tests can distinguish its output from

Â random. More precisely, what we'll say is that, basically for all efficient

Â statistical tests, a... Statistical tests, a... It so happens that if I look at the

Â advantage. Of the statistical test E relative to G. This advantage basically is

Â negligible. So, in other words, it's very close to zero, and as a result,

Â this, statistical test was not able to distinguish the output from random, and

Â that has to be true for all statistical tests. So, this is a very, very pretty and

Â elegant definition, that says that a generator is secure, not only if a

Â particular battery of statistical tests says that the output looks random, but, in

Â fact, all efficient statistical tests will say the output looks random. Okay? One

Â thing I'd like to point out is, that the restriction to efficient statistical tests

Â is actually necessary. If we ask that all statistical tests, regardless of whether

Â they're efficient or not, not be able to distinguish the output from random. Then

Â in fact, that can not be satisfied. So in other words if we took out the

Â requirements that the test be efficient. Then this definition would be

Â unsatisfiable. And I'll leave this as a simple puzzle for you to think about. But

Â basically the fact is that restricting this definition into only efficient

Â statistical tests is actually necessary for this to be satisfiable. So now that we

Â have a definition, the next question is can we actually construct a generator and

Â then prove that it is in fact a secure PRG. In other words, prove that no

Â efficient statistical test can distinguish its output from random. And it turns out

Â that the answer is we actually can't. In fact, it's not known. If there are any

Â probably secure PRG's. Then I will just say very briefly the reason is that if you

Â could prove that a particular generator is secure that would actually imply that P

Â is not equal to NP. And I don't want to dwell on this. Because I don't want to

Â assume that you guys know what P and NP are. But I'll tell you as a simple fact

Â that in fact in P is equal to NP. Then it's very easy to show that there are no

Â secure PRGs. And so if you could prove to me that a particular PRG is secure, that

Â would imply that P is not equal to NP. Again, I will leave this to

Â you as a simple puzzle to think about. But, even though we can't actually

Â rigorously prove that a particular PRG is secure, we still have lots and lots and

Â lots of heuristic candidates, and we even saw some of those in the previous

Â segments. Okay now that we understand what is a secure PRG. I want to talk a little

Â bit about some applications and implications of this definition. And so

Â the first thing I want to show you is that in fact a secure PRG is necessarily

Â unpredictable. In a previous segment, we talked about what it means for a generator

Â to be unpredictable. And we said that, basically, what that means is that, given

Â a prefix of the output generator, it's impossible to predict the next bit of the

Â output. Okay, so we'd like to show that if a generator is secure, then necessarily,

Â it means it's unpredictable. And so the only way we're gonna do that is using the

Â contrapositive. That is, we're gonna say that if you give me a generator that is

Â predictable, then necessarily, it's insecure. In other words, necessarily, I

Â can distinguish it from random. And so let's see, this is actually a very simple

Â fact. And so let's see how we would do that. So suppose you give me a predictor.

Â In other words, suppose you give me an efficient algorithm, such that, in fact,

Â if I give this algorithm the output of the generator, but I give it only the first

Â I-bits of the outputs. It's able to predict the next bit of the output. In

Â other words given the first I-bit it's able to predict the I plus first bit. And

Â it does that with a certain probability. So let's say if we choose a random k. From

Â the keyspace. Then, clearly, a done predictor would be able to predict the

Â next bit with probability one-half, simply just guess the bits. You'll be right with

Â probability one-half. However, this algorithm A is able to predict the next

Â bit with probability half with epsilon. So it's bound to the way. From a half. And,

Â in fact, we require that this by true for some non negligible epsilon. So, for

Â example, epsilon =1/1000 would already be a dangerous predictor, because it can

Â predict the next bits, given a prefix, with non negligible advantage. Okay, so

Â suppose we have such an algorithm. Let's see that we can use this algorithm to

Â break our generator. In other words to show that a generator is distinguishable

Â from random and therefore, is insecure. So what we'll do is we'll define a

Â statistical test. So, let's define the statistical test B as follows. Basically,

Â B, given a string, x, what it will do, is it will simply run algorithm A on the

Â first I-bit of the string x that it was given. And, statistical test b is simply

Â gonna ask, was a successful in predicting the I-plus first bit of the string? If it

Â was successful, then it's gonna output one. And if it wasn't successful, then

Â it's gonna output zero. Okay. This our statistical task. Let's put it in a box So

Â we can take it wherever we like. And we can run the statistical test on any N bit

Â string that's given to us as inputs. So now, let's look at what happens. Suppose

Â we give the statistical test, a truly random string. So a truly random string R.

Â And we ask, what is the probability that the statistical test outputs one? Well,

Â 18:07

is going to be equal to some random bit X I+1. Random independent bit X I+1, that

Â probability is exactly 1/2. In other words, algorithm a simply has no

Â information about what the bit X I+1 is, and so necessarily, the probability is

Â able to predict X I+1 is exactly one half. On the other hand, let's look at

Â what happens when we give our statistical tests a pseudo-random sequence, okay. So

Â now we're going to run the statistical test on the output of the generator, and

Â we ask how likely is it to output one. Well, by definition of A, we know that

Â when we give it the first I bits of the output of the generator, it's able to

Â predict the next bit with probability 1/2 + epislon. So in this case our

Â statistical test B will output one with probability greater than 1/2 + epsilon

Â And basically what this means, is if we look at the advantage of our

Â statistical tests over the generator G it's basically, the difference between

Â this quantity and that quantity. There's a difference between the two. You can see

Â that it's clearly greater than an epsilon. So what this means is that if algorithm A

Â is able to predict the next bits with advantage epsilon, then algorithm B is

Â able to distinguish the output of the generator with advantage epsilon. Okay? So

Â if A is a good predictor, B is a good statistical test that break the generator.

Â And as we said, the counter-positive of that is that if G is a secure generator,

Â then there are no good statistical tests. And as a result, there are no predictors.

Â Okay? Which means that the generator is, as we said, unpredictable. Okay, so, so

Â far, what we've seen is that if the generator is secure, necessarily, it's

Â impossible to predict the I+1 bit, given first I bits.

Â Now there's a very elegant and remarkable theorem Yao back in 1982. They

Â chose it, in fact the converse is also true. In other words, if I give you a

Â generator that's unpredictable, so you cannot predict the I+1 bits from the

Â first I bits, and that's true for all I. That generator, in fact, is secure. Okay,

Â so let me state the theorem a little bit more precicely. So here we have our

Â generator that outputs n bit outputs. The theorem says the following, basically for

Â all bit positions, it's impossible to predict I+1 bit of the output

Â given the first I bit. And that's true for all I. In other words, again, the

Â generator is unpredictable for all bit positions. Then, that, in fact, implies

Â that the generator is a secure PRG. I want paraphrase this in English,

Â and so the way to kinda interpret this result is to say that it's basically these

Â next bit predictors. These predictors that try to predict the I+1 bit given the

Â first I bits. If they're not able to distinguish G from random, then, in fact,

Â no statistical test is going to distinguish G from random. So kind of next

Â bit predictors are in some sense universal, predictors, when it comes to

Â distinguishing things from random. This theorem, by the way, it's not too

Â difficult to prove, but there's a very elegant idea behind its proof. I'm not

Â gonna do the proof here, but I encourage you to think about this as a puzzle, try

Â to kind of try to prove this theorem yourself. Let me show you kind of one cute

Â implication of this theorem. So let me ask you the following question. Suppose I give

Â you a generator and I tell you that given the last bit of the output. It's easy to

Â predict the first bit of the outputs, okay? So given the last end bits, you can

Â compute the first end bits. That's kind of the opposite of predictability, right?

Â Predictability mean given the first bit, you can produce the next bits. Here,

Â given the last bits, you can produce the first ones. And my question to you, does

Â that mean that the generator is predictable? Can you somehow, from this

Â fact, still build a predictor for this generator? This is kind of a simple

Â application of Yao theorem let me explain to you the answer is actually yes let me

Â explain why how do we build this generator well, actually we're not going to build it

Â I'm going to show you that the generator exists. Well because an over two bits

Â first an over two bits doesn't necessarily mean that the generator here let me write

Â them this way what it means is that g is not secure. Because just as we did before

Â it's very easy to build a statistical test that will distinguish the output of G from

Â uniform. So G is not secure. But if G Is not secure, by Yao's Theorem, that means that

Â G is predectible. So in other words, there exists some I for which given the first I

Â bits of the output, you can build the I+1 bits of the output. Okay, so

Â even though I can't quite point to you a predicter, we know that a predicter must

Â exist. So that's a one cute simple application of Yao theorem. Now before we

Â end the segment I want to kind of, generalize a little bit of what we did.

Â And introduce a little bit of important notation that's going to be useful

Â actually throughout. So, we're gonna generalize the concept of

Â indistinguishability from uniform, to indistinguishability of two general

Â distributions. So, suppose I give you p1 and p2, and we ask, can these two

Â distributions be distinguished? And so we'll say that the distributions are

Â computationally indistinguishable, and we'll denote this by p1, a squiggly p. P2.

Â This means that, in polynomial time, P1 cannot be distinguished from P2. And we'll

Â say that they're indistinguishable, basically, just as before

Â if basically for all, efficient, statistical tests, statistical tests. A it so happens

Â that if I sample from the distribution P1. And I give the output to A. Versus if I

Â sample from the distribution P2, and I give the sample to A. Then basically A

Â behaves the same in both cases. In another-wards the difference between these

Â two probabilities is negligible. And this has to be true for all statistical tests.

Â For all efficient statistical tests. Okay? So if this is the case then we say that,

Â well A couldn't distinguish it's advantage in distinguishing two distributions is

Â negligible and if that's true for all efficient statistical tests then we say

Â that the distributions are basically computationaly indistinguishable,

Â because an efficient algorithm cannot distinguish them. And just to show you how

Â useful this notation is, basically using this notation the definition of security

Â for PRG just says. That if I give you a pseudo-random distribution. In other

Â words, I choose K at random, and that outputs a G of K. That distribution is

Â computationally indistinguishable from the uniform distribution. So you can see this,

Â this very simple notation captures the whole definition of pseudo-random

Â generators. Okay, so we're gonna make use of this notation. In the next segment,

Â when we define, what does it mean for a cipher to be secure.

Â