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

372 ratings

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

From the lesson

Week 6

Key Exchange and Public-Key Encryption

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

Maryland Cybersecurity Center

[SOUND] In this lecture we'll look at public-key encryption schemes,

and we'll start by just showing how public-key encryption

can be used to ensure secrecy in the public-key setting.

So just like in the public-key setting more generally.

We'll begin with a party who locally generates public and private keys.

When another party comes along and wants to communicate with this first party,

the first thing they need to do is to obtain a copy of that user's public key.

In this figure for concreteness we've just assumed that the party is able to

look up the other person's public key in some public directory.

And so now they have an authentic copy of the public key of the person with whom

they wish to communicate.

They can take a message m that they wish to send to the recipient.

And they can then encrypt that message using the public key that

they've just obtained.

This gives a ciphertext c which they can then send onto the recipient.

At the other end the recipient can use the private key to decrypt the ciphertext and

recover the message.

And one thing I want to stress here is that we have asymmetry.

Because the keys being used by the sender and the receiver are different.

And this is contrast to the case of private key encryption

where encryption and decryption both use the same key.

Here encryption uses the public key and decryption uses the private key.

Now from the point of view of an attacker,

note that only does the attacker get to observe the ciphertext, but we'd have to

assume that the attacker is also able to get a copy of the recipient's public key.

After all, if the public key is being stored in some public directory, it's

reasonable to assume that the attacker is able to get its hands on it also.

Nevertheless, even for an attacker who obtains the public-key of

the recipient and can observe the cipher text,

we would like the contents of the message being communicated to remain secret.

More formally a public-key encryption scheme consists of

three probabilistic polynomial time algorithms.

The first algorithm is the key-generation algorithm,

that on input the security parameter outputs the public and private keys.

The encryption algorithm, as we've just seen, takes as input a public key and

a message, and outputs a ciphertext c.

The decryption algorithm takes as input the private key and the cipher text.

And it outputs either a message m or

a special symbol that we use here to denote an error.

And of course we have the standard correctness requirement that for

all messages m and for

all public, private key pairs, output by the key generation algorithm.

If you decrypt using the private key, something that was

encrypted using the public key, you should get back the same results in the end.

We can define CPA security for public encryption scheme's in a way that's very

analogous to the definitions that we've seen already in the private key settings.

So let's fix a public-key encryption scheme Pi and some attacker a.

And then we can define the following experiment.

The first thing we do is to run the key generation algorithm to obtain public and

private keys.

And we give the public key to the attacker.

Right, this just models what we talked about earlier.

Namely that the attacker is assumed to be able to see the public key of

the recipient.

The attacker then outputs two messages, m0 and m1 of the same length.

And the experiment then chooses a uniform bit b and

encrypts the message mb using the given public key to obtain a ciphertext c.

And we give the ciphertext to a.

Finally, a outputs a guess, b prime.

Representing its best guess as to what message was encrypted.

And the attacker succeeds, i.e.

the experiment evaluates to one, if and

only the attackers guess, b-prime, was correct.

In the usual way, we then define that a public encryption scheme is CPA-secure.

If for all probabilistic polynomial time adversaries a, the probability with which

a succeeds in the experiment we just saw is at most one half plus negligible.

Now I want to make a couple of observations about the definition.

One thing you might have been surprised about is the fact that the definition,

although it talked about CPA security.

Did not include an encryption oracle.

But the reason for that is simple.

If the attacker has the public key, it has no need for an encryption oracle.

Given the public key,

the attacker can use the public key to encrypt messages of his choice.

And therefore, unlike the private key setting, the attacker doesn't need access

to an encryption oracle in order to obtain encryptions of messages of his choice.

That means that even if we wanted to define a relatively weak

notion of security against a completely passive attacker,

there's sort of no way to get around automatically including the ability

to mount a chosen plain text attack in the public-key setting.

And that's something that's in contrast to what we've seen as we've

discussed already in the private key setting.

Now this fact has a number of consequences.

The first is that there's no such thing as perfectly secret public-key encryption.

At least not in any of a setting where the attacker's able to get a copy of

the recipient's public key.

And this follows really from the fact that as we've just said given

the public key the attacker effectively has access to an encryption oracle.

Which means that given any ciphertext corresponding to some unknown

method the attacker could always try to encrypt every possible message under

the public key repeatedly until it obtains the same ciphertext.

And therefore, if you allow attackers with unbounded running time, they'll always be

able to figure out the message that corresponds to a given ciphertext.

Alternately, the attacker could also run the key generation algorithm over

and over again.

Until it obtains a private key matching the observed public key.

Another consequence, is that no public encryption scheme

with a deterministic encryption algorithm can possibly be CPA-secure.

And this is exactly like what we've seen already in the setting of

private-key encryption.

If you have a deterministic encryption scheme.

Then given an, given a ciphertext feed,

which is an encryption of one of two possibilities, either of zero or of one.

The attacker that could simply encrypt them zero encrypt in one, and

compare both of those results to the observed ciphertext and

figure out exactly which message was encrypted.

What this means is that we should never use a deterministic public-key

encryption scheme.

They simply won't satisfy even the most basic notion of security.

Finally, if we defined a notion of security for

the encryption of multiple messages.

Then, just as in the private key setting where we observed that

CPA security implies security for the encryption of multiple messages.

The same will hold, will hold true in the public key setting as well.

That is the definition of CPA security that we gave on the previous slide.

We'll also imply the secrecy of encrypting vectors of message as well.

Now we can often define, or

consider, the notion of chosen-ciphertext attacks in the public key setting.

So here we have an attacker who's observed the ciphertext c, and it's implicit even

though I haven't shown it here that the attacker knows the public key as usual.

The attacker might then be able to inject ciphertext c prime,

that is to send the ciphertext to the recipient.

And, receive in return the resulting decryption, m prime,

corresponding to the ciphertext that it sent.

Now, this is so far, just like what we saw in the private-key case.

But, I want to make the point here, that chosen-ciphertext attacks.

Can arguably be even a greater concern in the public key setting than they were in

the private key setting.

And the reason for that fundamentally is that in the private key setting,

the recipient shares the key, shares their key, with one other sender.

And so when they receive a ciphertext, they will assume that it

came from the legitimate sender, the single legitimate sender.

With whom they've shared their key.

In contrast, in the public key setting,

almost by assumption, anybody in the world who's ob, able to obtain a copy of

the public key is a legitimate sender with respect to that receiver.

And so it's not at all unusual for

the receiver to receive ciphertexts from many different senders.

And so it would be much easier in this case number one for an attacker to

send a ciphertext that wouldn't immediately get rejected by the recipient.

And number two it would be easier for the attacker to potentially receive and

return the entire decryption of the ciphertext that it sends to the receiver.

So the point of all of this is that if you thought that chosen ciphertext were

a problem in private key setting, and

indeed they are, well they're even more a concern in the public key setting.

A very related concern that we've spoken about earlier in the private key

setting as well is that of malleability.

And remember that this informally refers to the property that

given the ciphertext c that is the in the encryption of some unknown message m.

It might be possible for an attacker to produce a ciphertext c

prime that decrypts to a related message m prime.

And again this is likely to be even more problematic in the public key

setting than it is in the private key setting.

And, we'll show an example, in fact,

in the next lecture, I, that I think really highlights this point.

Just as in the private-key case, we're not going to define a notion of malleability.

But, I can tell you that malleability and

chosen-ciphertext security are very related.

And, in particular, any scheme which is malleable will not be

secure against chosen-ciphertext attacks.

And conversely, a scheme that is secure against chosen cipher text

attacks will not be malleable.

Now, we can define formally a notion of CCA security for public key encryption.

Again, by analogy to the definition we've seen already for

the case of private encryption.

And I'm going to skip that here for simplicity.

Now one very important paradigm I want to introduce is that of hybrid encryption.

Let's imagine we want to use a public key encryption scheme

to encrypt a very long message m.

Now one thing we can do of course is to simply use the encryption algorithm as is

with the public key.

And the message m, as input to obtain a ciphertext c.

And in this diagram,

I've just indicated that by the triangle, where the key is going into the algorithm.

So this just indicates which input is the key and

which is the message being encrypted.

Now, we can do that, and

that will work, but remember that we said earlier in a previous lecture.

That public key encryption is relatively inefficient,

at least as compared to private key encryption.

So we can use a different approach instead in order to obtain better efficiency.

What we'll do is to select a random key k for some private key encryption scheme.

And, then, rather than encrypting m,

using the public-key scheme, what we'll do is to encrypt k, itself.

And, obtain a ciphertext that we'll call here an encapsulated key.

We can then just use the key that we've just chosen as the key to

a private-key encryption scheme Enc prime.

And use the private key encryption scheme to encrypt our bulk data m.

This will result in a ciphertext for the underlying private key encryption scheme.

Decryption can be done in the obvious way.

So the ciphertext now will consist of both components, both the encapsulated key

that we got by running the public key scheme, as well as the ciphertext that

we got by encrypting the bulk data using the private key encryption scheme.

What the recipient can do is they can use their private key

to decrypt the encapsulated key.

And recover k.

And, then use the decryption algorithm for the private-key encryption scheme

to recover m from the first portion of the ciphertext.

Now, note, that by just putting a box around both of those algorithms together,

and by grouping the two ciphertexts that we obtained, and

referring to those as a single ciphertext.

We obtain something with the functionality of a public key encryption scheme.

We have a public key going in at the bottom, a message coming in at the left,

and a ciphertext coming out at the right.

What this means is that we have something here which is

giving us the functionality of public key encryption.

It's allowing us to transmit a message to a recipient using knowledge only of

their public-key.

But the efficiency here is asymptotically the efficiency of

the private-key encryption scheme, because we're using the private-key encryption

scheme to encrypt the bulk data.

And the public-key scheme is only being used to encrypt a very short key.

What this means also is that it suffices to consider public key

encryption schemes that can encrypt only relatively short values.

Like 128 bit keys.

And we can then take those and bootstrap them into public key

encryption schemes supporting encryption of arbitrary length data.

What can we say about the security of the approach on the previous slide?

Well, let's let Pi denote the public-key component and

Pi prime denote the private-key encryption scheme being used.

And we'll let Pi hybrid, denoted here by Pi sub hy,

denote the combination of the two as on the previous slide.

Well, it's possible to prove that if Pi is a CPA-secure public-key encryption scheme.

And Pi prime is a CPA-secure private-key encryption scheme.

Then the hybrid encryption approach resulting from the combination of the two

is itself a CPA-secure public-key encryption scheme.

And one can show a similar result for CCA security as well.

We've already seen examples of private-key encryption schemes that are both

CPA or CCA-secure.

And what that means is again if we can design public key encryption key

schemes that can encrypt only relatively short values like 128 bit keys.

Then we can couple couples those with the private key encryption schemes we've

seen earlier and obtain efficient public key encryption schemes for

arbitrary length messages.

The hybrid encryption approach is one that is used all the time in practice and you

never want to use a public key encryption natively to encrypt large volumes of data.

In the next lecture we will see our first concrete examples of public key

encryption schemes.

When will, when will we examine public key encryption schemes based on

the discrete-logarithm assumption and the Diffie–Hellman assumption.

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