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

409 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] Recall the three

principles of modern cryptography.

Definitions, proofs, and assumptions.

We've already spent quite a bit of time building up definitions of

secure encryption.

Both for the case of perfect secrecy and then for

our relaxation, of computational secrecy.

We've also seen a little bit of proof.

We had in particular, the proof that the one time pad encryption scheme,

satisfied our definition of perfect secrecy.

We haven't yet had the opportunity to explore the use of assumptions.

In the last few lectures, we've defined computational secrecy and

talked about how by relaxing the definition of perfect secrecy,

we can hope to circumvent the inherent lower bounds and

impossibility results that perfect secrecy comes with.

We've also defined, or introduced, the pseudo one time pad encryption scheme.

And our goal in this lecture is to rigorously prove that the pseudo one

time pad encryption scheme, meets our definition of computational secrecy.

Unfortunately, we're unable to prove this statement unconditionally.

We can't prove unconditionally, that the pseudo one time pad encryption scheme,

is computationally secret.

For one thing, such a proof is beyond our current techniques.

As I've mentioned several times already, proving unconditionally, that some

encryption scheme which is not perfectly secret, is computationally secret,

would imply in particular a proof that P is not equal to NP.

A longstanding unresolved question, in complexity theory

which seems completely beyond our current techniques to address.

There's also something a little bit more fundamental than,

that which is that the pseudo one time patent encryption scheme, as we defined it

depended, or was defined based on some underlying component G.

G was a function that took a small input and produced a larger output.

In the case of a pseudo one time pad, it took as input the key, that the two

parties shared and expanded that into a pseudo pad that the party the parties then

XOR with the message to encrypt and XOR with the ciphertext in order to decrypt.

Though we can't really hope to claim anything about the pseudo one

time pad in general, unless there's something about the particular G

that we used with which to instantiate the scheme.

So security of the pseudo one time pad must depend somehow on what

particular function G we plug in.

Or and, and or, what properties that function G has.

So, what we can hope to prove is security of the one time pad, sorry,

of the pseudo one time pad encryption scheme,

under the assumption that G is a pseudorandom generator.

This actually tells us a couple of things, right?

First of all it tells us that if, we begin, with a secure,

with a pseudorandom generator G and then build the pseudo one

time pad encryption scheme from that, then the scheme is secure.

It also tells us that we can feel free to swap in different functions G.

We can put in any function G that we like,

as long as it satisfies the property of being a pseudorandom generator.

And given that assumption, the scheme will be secure.

Now before we turn to details of the proof, let me just revisit the definition

of pseudorandom generators in a little bit of different form,

than what we've seen before.

I wanted to go through it actually pictures, because part of the proof

of the pseudo one time pad encryption scheme is going to be my picture.

So remember that we have some fixed, function G which is an efficient,

deterministic function and let's assume for concreteness, that G

is length doubling, so that means that its output, is twice the length of its input.

We can now view our function G,

as being involved in an experiment of the following form.

Somebody comes along with an algorithm D, D here stands for distinguisher,

this algorithm D takes as input a string Y and outputs a bit B.

And we can think of these as D taking of input some string, some long string.

[COUGH] And trying to determine whether Y was chosen uniformly at random, or whether

Y was output by running the pseudorandom generator G on some uniform input.

So that means in one case, we have Y being sampled uniformly from a dis,

from strings of length and we can look at it the behavior of D,

when it's fed with a string Y sample, according to that distribution.

So in particular right,

we can calculate the probability with which D outputs one, right?

The probability with which B is equal to one, where that probability has taken over

the choice of Y, according to the uniform distribution on strings of length 2N.

And, also over any randomness internal to the algorithm D itself.

We're allowing, the possibility, that D itself can be a randomized algorithm.

So we can compute that probability.

It's a well defined probability for each value of the security parameter N.

Ultimately, we can look at a second case.

We can look at the case where, what we have is an experiment in

which we first sample a uniform N bit string, K and

we then feed that as input, to our function G and

take the output call it Y and feed that to our algorithm D.

So now, we can again look at the probability with which D

outputs the bit B equals one.

Where the probability is now taken over the uniform choice of K,

chosen uniformly from strings of length N.

And again, that's a well defined, probability for each value of N.

If G is a pseudorandom generator, that means that for any efficient D,

any efficient distinguishing algorithm D.

The probability, that D outputs one in the first case,

when Y is sampled uniformly from strings of length 2N,

is very close to the probability with which D outputs one in the second case,

when we sampled k uniformly and then it compute Y equals G of k.

That's the definition of what it means for G to be a pseudorandom generator.

It's a pseudorandom generator if and only if, this holds for any efficient D.

Before going into the details of the proof, I want to discuss,

at a high level, how proofs by reduction work.

Proofs by reduction are very common and

we'll see them very frequently, throughout the rest of the course.

Here I'll walk through a high level description of how the proof by

reduction is going to work.

For a specific example,

with the pseudo one time pad based on a pseudorandom generator G.

What we do is we start with the assumption,

that G is a pseudorandom generator.

Then, let's say or

let's assume toward a contradiction, that there's some efficient attacker A,

who breaks the pseudo one time pad scheme, whereby breaks, I mean very specifically,

that it violates the definition of computational security, right?

That means we have an efficient attacker A,

whose success probability in the experiment that we defined,

is not bounded by one half, plus a negligible function.

What we'll then do, is use this algorithm A as a subroutine,

to build an efficient algorithm D.

That breaks the pseudorandomness of G.

And here again, I mean breaks actually in a very formal sense,

in terms of the formal definition of what it means for G to be pseudorandom.

Now we, what we'll do is we'll relate, the probability with which

D can break the pseudorandomness of G, to the probability with which A,

can break the security of the pseudo one time pad encryption scheme.

And show that if A indeed breaks the pseudo one time pad scheme,

then D breaks the pseudorandomness of G.

But we know, by assumption that G is pseudorandom,

that no such distinguisher D can exist.

There cannot be an efficient D that breaks the pseudorandomness of G.

This is again by our assumption, that G is a pseudorandom generator.

And this implies that our initial assumption of A,

must have been false and there could not exist such an A, in the first place.

One important point here and we'll see again in the actual proof,

is that we don't make any assumption whatsoever, about how A works.

The only thing we assume in step two, is that we have some A who somehow or

another, is able to break the pseudo one time pad scheme.

And we show that the existence of such an A,

would imply the existence of a D, that break the pseudorandomness of G.

And again because no such D can exist, that implies that no such A can exist.

[SOUND] An alternate way of viewing what we just said,

is rather than working by a proof towards a proof by contradiction,

as we did on the previous slide we can work in the other direction.

So this is really just a reframing of the, of what we had on a previous slide.

What we can do and

this is actually more along the lines of the proof we're actually going to show.

Again, we'll start with the assumption that G is a pseudorandom generator.

We'll then fix some arbitrary efficient A, attacking the pseudo one time pad scheme.

Here we're not assuming anything about the success probability of A,

in attacking the scheme.

We're just given that at some arbitrary A, who is efficient, i.e,

running in, probabilistic polynomial time.

We then use A as a subroutine, to build an efficient, distinguisher D attacking G.

And as before, were going to relate the distinguishing probability of D,

in attacking the pseudorandom generator, to the success probability of A,

in attacking the pseudo one time pad scheme.

By assumption, right by the assumption that G is a pseudorandom generator and

because D is an efficient algorithm,

we know that the distinguishing probability of D, must be negligible.

All right, the gap, between the probabilities with which D outputs one

in the two cases, must be negligible.

Using our relation between the distinguishing probability of D and

the success probability of A, we will then directly conclude a bound on the success

probability of A, as desired, i.e, would show immediately, directly, that

the success probability of A, can be at most one half plus a negligible function.

This will make more sense after we complete the analysis of the reduction,

in the following few slides.

[SOUND] Let's recall the pseudo one time pad just so

we have it in, in our minds as we go through the proof.

We have the two parties sharing an end bit key that I've denoted here by k.

And to encrypt a message of length 2n,

what they what the sender will do is to, pass k as input to G.

Take the resulting string.

The output of G.

Which is a string of length 2n.

And that with the message.

And this gives the ciphertext.

[SOUND] The theory we're going to prove is that if,

the function G used in the previous slide.

Is a pseudorandom generator, then the pseudo one time pad, IED

encryption scheme in the previous slide, is computationally indistinguishable.

Here's the reduction, so again, we're going to take some arbitrary,

algorithm A, adversary A, who runs in polynomial time.

This A, is attacking our pseudo one time pad encryption scheme.

We know nothing about how it works.

We know nothing about what it does.

We don't even know a priori anything about its success probability.

The only thing we're given, is that it's efficient.

And that it is trying to attack, the pseudo one time pad encryption scheme.

In the sense of our definition of computational secrecy.

Which means that this adversary is going to output a pair of messages,

be given back a ciphertext and then output a bit, with which it's trying to

guess which of those two messages that it output, was the one that was encrypted.

We're going to construct from this A, a distinguisher D,

that uses A as a subroutine.

So I've drawn the picture here as if D is some,

you can think about it as a black box that contains A inside.

Or you can think about D as some piece of code,

that makes subroutine calls out to the function implementing the attacker A.

Either way we imagine in this picture,

that A is being run inside of D as some kind of a subroutine.

D is going to be a distinguisher, trying to distinguish whether it's given

uniform strings, or strings that were output by the pseudorandom generator G.

So the interface of D, is that it's going to accept, strings Y as input.

And then going to output, a bit, b or, or a bit, rather determining whether or not

it thinks that it's input, was uniform or the output of the pseudorandom generator.

D works in the following way, what D is going to do,

is start running A as a subroutine, to obtain two messages in zero and one.

These are the two messages that A, select.

At this point, D is going to simulate the experiment of computational secrecy for A.

So what that means is that D, is going to, on it's own sample uniform bit b,

determining which of those two messages it's going to take.

And it's then going to excor the message m sub b,

that it selected, with its input string Y.

We can call that C, just a variable name.

But it's meant to indicate that we're thinking of this as a ciphertext.

And it gives that ciphertext as input to A.

So, remember A, believes it's attacking the encryption scheme.

So from As point of view, this exactly matches what it expects to see, because A,

indeed output two messages and got back a cipher text.

A will then output some bit, b, which

is supposed to represent it's guess, as to which of the two messages were encrypted.

And what D then does, is to check whether or not b and b prime are equal, right?

D chose b itself, D got b prime as output from the attacker A, so

D can certainly check whether those two bits are equal.

And D, will output the bit one, if and only if b and

b are equal, and zero otherwise.

So this completes our description of D.

D is well defined, given any algorithm A as a subroutine.

The first thing to look at or

to check, is that given that A runs in polynomial time, so does D.

All D is doing is running A once as a sub routine and

then doing some very minimal processing on top of that.

So, if A indeed runs in polynomial time, then so

does D, i.e if A is efficient, then D is also.

[SOUND] In the analysis of the distinguishing probability,

the distinguishing gap, of D it's useful to define as a piece of notation,

the function Mu of n, to be equal to the probability, with which A succeeds,

in the computational secrecy experiment, right?

Remember that we defined this experiment PrivK, in an earlier lecture and

basically this corresponds exactly to the probability, with which b

is equal to b prime, when, using the pseudo one time pad encryption scheme.

So, pi here, refers to the pseudo one time pad encryption scheme.

So first of all we can look at what happens when the input given to D,

is psuedorandom, meaning that we determined the input

to D by choosing a uniform feed giving it to the pseudorandom generator,

calling the result Y and then giving that value as input to D.

If the input Y is generated in that way, then I claim that the view of A,

when it's being run as a subroutine by D,

is exactly identical to the view of A in the experiment PrivKA pi.

And I'll show that pictorially on the next slide.

But assuming that's the case, that means that the probability that D outputs one,

when Y is generated pseudorandomly,

i.e, when we generate the input to D, by choosing a uniform feed X.

And then computing G of x and feeding the result into D.

That probability is then exactly equal to the probability with which b,

is equal to b prime, which is exactly by definition, equal to the probability

that A, succeeds in experiment PrivKey A pi, which we define to be mu of n.

So, let's look at this claim that when the input Y is pseudorandom,

the view of A is exactly the same as an experiment PrivK A pi.

So here's the picture similar to what we had two slides ago,

although now I've changed the way, or

I've explicitly denoted rather the way that Y is being sampled.

So here, we're working under the assumption that we're in the cave,

where Y is sampled by choosing a uniform seed k, running it through G and

letting the output be denoted as Y and feeding that in as input to D.

Well, in that case, if we just draw our box a little bit differently,

we see that inside this top box that, that we just put here

this corresponds exactly to an experiment where A,

outputs two messages, a uniform bit is chosen and then if you look at the what,

what's going on with m sub b, where we have it being exhorted with the string Y.

That is exactly syntactically identical to what we would get if we

chose a uniform key k and then, used the encryption scheme of pi, i.e.,

the encryption scheme of the pseudo one time pad,

to encrypt the message m sub b, right?

And you can take a look at that again.

So here we're we just have the picture where we take key, run it through G.

Get a string Y and then exsore that with m sub b.

But remember, that is exactly what we do in the encryption scheme for

the pseudo 110 pad.

So we can replace that with a box for encryption in the pseudo 110 pad.

And this picture here, is precisely the picture of the experiment prides key A pi.

Right again, A is outputting two messages.

One is uniform only at random.

If they're encrypted using the encryption scheme of pi and

A uniform key, the cypher text is given to A and then we look at whether or

not a at the bit b prime output by A.

And we know that the probability with which b is equal to b prime,

is by definition, the success probability of A in attacking pi.

That's what we said a moment ago.

For the next step, we look at the other case.

We look at what the behavior of D is, when its input Y is chosen uniformly at random.

Well, in this case I claim that A will succeed with probability exactly one half.

So that means the probability with which As prime is equal to b,

is exactly one half because D, outputs one only when b is equal to b prime.

That means the probability with which D of Y outputs one,

when Y is sampled uniformly, is exactly one half.

And we can look at this picture as well, so here I have the same picture but

now sampling Y as a two uniform two end bit string.

And if we draw out picture again a little bit differently and

replace this part here with encryption, using the one time pad scheme

right not the pseudo one time pad scheme, the one time pad scheme.

Because now the key Y, is here uniformly random uniform to n bit string.

So then, this is exactly a picture of the experiment in which A,

is attacking the one time pad encryption scheme.

But we know that the one time pad encryption scheme,

is perfectly secret and that's stronger than being computationally secret.

So we know that the probability with which A can output b prime,

equal to b in this experiment, is precisely one half.

Now we're almost done.

So, we've determined or we've related the probability with which D,

outputs one in each of those two cases.

Two in one case the probability with which A,

succeeds when attacking the pseudo one time pad and

then the other case, we've explicitly calculated it to be equal to one half.

Now by the assumption that G is pseudorandom and because D is efficient,

because D is polynomial time, we know that the difference in probabilities with which

D1 outputs one in those two cases, must be bounded by some negligible function.

Or more exactly,

the absolute value of a difference has to be bounded by some negligible function.

So there exists a negligible function epsilon n,

such that of n minus one half absolute value is at most epsilon n.

And just substituting in terms and rearranging and

doing some algebra, we see that this implies that the success probability of A,

in attacking pi, is bounded by one half plus epsilon N.

For epsilon N, a negligible function.

And that completes the proof, right?

What we want it to show is that, the pseudo one time pad encryption scheme pi,

meets our notion of computational secret, of computational secrecy,

we showed this because we started with an arbitrary efficient algorithm A and

proved that regardless of what A, is doing, as long as its efficient, there's

some negatives where function epsilon, such that the success probability of A,

in attacking pi, is almost one half of epsilon.

So, let's step back a little bit and ask ourselves what this all means.

So importantly, we've now proven that the pseudo one time pad is secure.

The point again being that, we have a provably secure scheme which is

much better than having a heuristic construction that just looks secure,

of one that we don't see any obvious way to attack it.

On the other hand, this proof does come with some caveats and

I don't want to downplay these.

So the proof is under the assumption that G is a pseudorandom generator and

of course, the proof is always relative to our definitions and

what we proved is exactly, what the theorem said,

which is the pseudo one time pad, achieves our notion of computational secrecy.

Now, what this means is that,

on the one hand, we're guaranteed that the only ways to break our scheme or

to break the pseudo one time pad scheme, are either to find a weakness in G, or

if the definition of computational secrecy isn't sufficiently strong, the fir,

the first of these, a weakness being found in G, is a concern in practice.

However, for the most part, what an implementer would do,

is choose some standard algorithm G, which is widely believed to

be a pseudorandom generator and it's therefore, relatively unlikely.

That weaknesses will be found in G.

This is obviously more true when G is something that stood the test of time and

been around and analyzed a lot longer, but nevertheless, its an, relatively speaking

unlikely for weaknesses to be found in G and moreover, if a weakness is

found in some particular function G, then the implementor can always swap out,.

That function G for another function G prime,

that's believed to be more secure as a pseudorandom generator.

More problematic, is the issue of the definition.

So the definition of computational secrecy that we,

that we've been using, in fact isn't really strong enough for

most applications of cryptography, in the real world.

Or most applications of encryption in the real world.

And this is a real issue and

one that we're going to start exploring in the next lecture

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