This course will introduce you to the foundations of modern cryptography, with an eye toward practical applications.

Loading...

From the course by University of Maryland, College Park

Cryptography

417 ratings

This course will introduce you to the foundations of modern cryptography, with an eye toward practical applications.

From the lesson

Week 2

Computational Secrecy and Principles of Modern Cryptography

- Jonathan KatzProfessor, University of Maryland, and Director, Maryland Cybersecurity Center

Maryland Cybersecurity Center

[SOUND].

Â In the last lecture we defined the notion of pseudorandomness and

Â I'll just recall that definition here.

Â If we have a sequence of distributions, Dn where each distribution Dn

Â is a distribution over strings of length p(n), for some function p,

Â will say that that sequence of distributions is pseudorandom if for

Â all probabilistic polynomial time adversaries A.

Â There's some negligible function epsilon such that if we look at the difference in

Â probabilities, between the probability that A(x) outputs one when x is sampled

Â according to D(n) and the probability that A(x) outputs one when x is sampled

Â according to the uniform distribution over strings of length p(n), then

Â the absolute value of the difference of those probabilities is at most epsilon n.

Â So intuitively, for any statistical test A, running in pro probabilistic polynomial

Â time, the distinguishing gap, right, the probability with which that statistical

Â test can distinguish whether it's given a string sampled according to D(n), or, or

Â whether he's given a string sampled according to the uniform distribution, or

Â the strings of the appropriate length.

Â It's at most epsilon(M).

Â We now want to define the important notion of pseudorandom generators.

Â I'll abbreviate this by PRG.

Â In practice, you may also hear of pseudorandom number generators

Â abbreviated PRNG, and for our purposes those are going to be the same.

Â But I'm going to stick with the terminology PRG, pseudorandom generator.

Â So, a PRG, a pseudorandom generator, is an efficient deterministic algorithm

Â that expands a short, uniform seed or input into a longer pseudorandom output.

Â We'll define this more formally in a moment.

Â But intuitively, this is just an algorithm that is given a short input,

Â converts it into a longer output and it has the property that if you sample its

Â input uniformly, then its output will be pseudorandom.

Â And pseudorandom generators are very useful whenever you have a small amount of

Â true random bits, but you want lots of random looking bits.

Â So just as a toy example or a made up example, say we have some algorithm that

Â requires 10,000 random bits, 10,000 uniform and independent bits.

Â We said in an earlier lecture that actually sampling true

Â randomness is very difficult.

Â You have to collect mouse movements or

Â collect timings between network events or typing at the keyboard.

Â And it takes actually quite a bit of effort and

Â time to collect true random bits.

Â So imagine that we've collected, say, 100 random bits,

Â 100 uniform and independent bits.

Â This assumes we've collected them and then processed them appropriately to

Â smooth them out and get some number, say, 100, of true random bits.

Â Well, what we can do is we can apply a pseudorandom generator to those 100 bits

Â and get a 10,000 bit output with the guarantee that as long as our

Â input bits are random or close to random, i.e, close to uniform,

Â the output of that pseudorandom generator will be random looking.

Â And if we then run our algorithm that requires those 10,000 random bits using

Â as its random bits, the output of the pseudorandom generator, then the output of

Â that algorithm will be as good as if we had run it on 10,000 uniform and

Â independent bits.

Â So pseudorandom generators are very,

Â very useful when you have a small amount of true randomness and you want to

Â extend it into a larger amount of things, of something, which is as good as random.

Â More formally, let G be a deterministic, polynomial time algorithm.

Â So, not only is this algorithm efficient but it's also deterministic.

Â If you run it twice on the same input, you get the same output.

Â We'll require also that G be expanding.

Â This just means that the output of G is longer than its input.

Â And in particular we can denote the output length of

Â G(x) to be equal to p of the length of x.

Â So this means that when you feed,

Â when you feed G with some input string x that has length n.

Â Then the output has length p(n), and

Â will require that p(n) be greater than n for all n.

Â In pictures, what we have is this algorithm G which

Â we're viewing here as box.

Â And it takes as input a short seed.

Â Okay, we're going to continue to refer to the input to G as a seed.

Â It takes that short input and produces a longer output.

Â Now what's interesting to note here is that this deterministic algorithm,

Â or this deterministic function G, defines naturally a sequence of distributions.

Â And it does that in the following way.

Â We can define distribution Dn to be the distribution on strings of length p(n).

Â Remember that p(n) was the output length of G when given an input of length n.

Â It's going to be the distribution on strings of length p(n) defined by

Â choosing a uniform seed x and then outputting G(x).

Â This is a valid distribution on strings of length p(n) where it

Â is defined by this process by which we sample a uniform seed and

Â then apply G to that seed to obtain a string of length p(n).

Â If you wanted to work through this formally, what it means,

Â well then it means that we're defining the following distribution d(n).

Â We're defining a distribution d(n) where the probability of any particular string y

Â of length p(n) is equal to the probability with

Â which G(x) is equal to y when we sample x uniformly.

Â That is the probability that D(n) assigns to some string y is exactly

Â the probability with which G(x) equals y, which is exactly the summation over

Â all inputs x, such that G(x) equals y of the probability of x.

Â And you can continue to further manipulate this and what you get in the end is that

Â it's the number of inputs x, such as G(x) equals y divided by 2 to the n, right?

Â It's the number of x's that map onto this string y multiplied by 2 to

Â the minus n because we're sampling x from the uniform distribution on n bit strings.

Â And so the probability of any particular x in that set being chosen is 2 to

Â the minus n.

Â So you can think about it either way, you can think about it formally, or you can

Â think about it in terms of the randomized experiment, which is also formal,

Â it's just that we're not, we're not explicitly writing out the distribution.

Â These are exactly equivalent ways of looking at the same randomized process.

Â We can then define this particular algorithm G,

Â to be a pseudorandom generator,

Â if this sequence of distributions Dn defined by G, is pseudorandom.

Â If we expand that out.

Â What this means, is that for all probabilistic polynomial time attackers A,

Â there's some negligible function epsilon such that,

Â if we look at the probability with which A when given input G(x) outputs one, and

Â compare that to the probability with which A, given a uniform string y outputs one.

Â The absolute value of the difference in those probabilities will be

Â at most epsilon.

Â So, in, more intuitively, this means that no efficient algorithm a can

Â distinguish with probability better than epsilon whether it's given G(x),

Â right the output of a pseudorandom generator,

Â when run on a uniform string x or whether it's given a completely uniform string y.

Â Right, so that means that our pseudorandom generator really is giving us

Â something that looks random.

Â It's producing for us strings of length p(n) that are indistinguishable for

Â any efficient attacker from a uniform string of that length.

Â Do pseudorandom generators exist?

Â Unfortunately, we don't know.

Â This is one of those things where we can't hope to prove the existence,

Â that we can't hope to prove the existence of without resolving,

Â in particular, the question of whether p is equal to np.

Â And in fact we require a, a even stronger assumptions than that.

Â Never the less, what we can do is that we can assume that certain concrete functions

Â G are pseudorandom generators and in fact this is exactly what we do in practice.

Â In practice, we have particular examples of deterministic functions G,

Â that people have designed and people have studied and people have analyzed and

Â have found no way with which to distinguish their output from uniform,

Â a uniform string of the appropriate length.

Â So it's reasonable therefore to assume that those functions G

Â are indeed pseudorandom generators.

Â And what we can then do is use those pseudorandom generators or

Â use those functions G to build other cryptographic schemes.

Â In addition from a more theoretical point of view.

Â It's known that we can construct pseudorandom generators from

Â weaker assumptions.

Â The assumption that some algorithm is a pseudorandom generator is a relatively

Â strong assumption.

Â It's not really clear a priori why it might be reasonable to

Â make that assumption about any particular algorithm.

Â However, there are weaker assumptions we can make.

Â And, starting from those weaker assumptions,

Â we can then build a pseudorandom generator,

Â where we can prove that the resulting algorithm is a pseudorandom generator

Â given some assumption that we start with, which is more reasonable.

Â We're not going to cover the details of any such construction here, but

Â I refer you to my textbook for more details on that.

Â Now, in either case,

Â we can assume that we have some G which is a pseudorandom generator,

Â whether we take as that G some practical construction or whether we take for

Â that G something that we've constructed based on even weaker assumptions.

Â But we can take that G.

Â We can start with the assumption that it's pseudorandom.

Â And we can then use it to construct an indistinguishable encryption scheme that

Â is a scheme that, that achieves computational secrecy.

Â And if you recall back to our discussion of the principles of modern cryptography.

Â Remember how we talked about the importance of assumptions?

Â And then using those assumptions to come up with constructions that we

Â can prove secure.

Â This will be an example of that.

Â We'll start with the assumption that sum G is a pseudorandom generator.

Â We'll build from that an encryption scheme.

Â And then we'll be able to prove that the encryption scheme satisfies our

Â definition of security under the assumption that the G we

Â started with is indeed a pseudorandom generator.

Â And we'll see exactly how that's done in the next two lectures.

Â Coursera provides universal access to the worldâ€™s best education,
partnering with top universities and organizations to offer courses online.