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

527 ratings

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

From the lesson

Week 1

Introduction to Classical Cryptography

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

Maryland Cybersecurity Center

[SOUND].

In the last lecture, we talked about the importance of definitions in general.

In this and the next lecture we'll look specifically at defining security for

private key encrytion schemes building up to a definition called perfect secrecy.

In this lecture we're going to build up to an informal definition of security.

And we'll make everything more formal in the next lecture.

In general cryptographic definitions have two components.

The first component specifies the threat model which is meant to

capture the real world capabilities that the attacker's assumed to have.

As we'll see, there can be many different threat models.

And the right one to use depends,

in part, on the environment in which the scheme will be used.

The second component of any cryptographic definition is the security guarantee.

You can view this alternately as the goal we're trying to

achieve by using the scheme.

Or is what it is we're trying to prevent the attacker from doing.

Since it's been awhile since we've looked at private key encryption let me

briefly remind you of the setting.

We have two parties, Bob and Alice, who have shared a key k in advance.

When Bob say, has some message m that he wants to send to Alice.

He'll encrypt that message, using the encryption scheme and their shared key K.

This results in a ciphertext that bob sends across the channel to Alice.

Upon receiving this message, Alice will use her key to decrypt the cypher-text and

recover the original message.

At a high level, the parties are trying to ensure secrecy of

their communication against an eavesdropper who can

observe everything being sent across the channel between Alice and Bob.

There are several different threat models we could consider here.

I'll describe them informally for now.

The most basic and the one implicit in the figure on

the previous slide is known as a ciphertext-only attack.

Here the attacker only gets to observe ciphertext being sent by the parties and

nothing else.

Even within this threat model, there are choices we can make.

In particular do we assume the attacker observes only a single ciphertext or

do we assume that the parties encrypt multiple messages using the same key and

the attacker gets to observe multiple ciphertexts.

As we'll see later on, this distinction makes a big difference.

A stronger threat model is the so-called known-plaintext attack.

Here, the attacker will again observe one or

more ciphertext whose underlying plaintext is unknown.

But, in addition to this, the attacker was able to obtain a bunch of

ciphertext encrypted using the same key along with the corresponding plaintext.

This might seem unrealistic, but

there are many real world scenarios in which such an attack is possible.

For a simple example, imagine that every day Alice and

Bob begin by sending encrypted hello messages back and forth.

If the attacker observes those ciphertext, it knows the underlying plain text.

An even stronger threat model is a chosen plaintext attack.

The attacker will again observe one or

more ciphertexts, whose underlying plaintext is unknown.

But in addition, the attacker is now assumed to be able to obtain cipher text,

encrypted using the same key,

corresponding to plaintext of the attacker's choice.

This may really seem unreasonable, but again, there are many natural

scenarios where some form of chosen-plaintext attack is possible.

For one thing actions of an attacker might influence the messages that parties send

even if the attacker can't control them completely.

In other cases,

the attacker might be able to have complete control over what gets encrypted.

For example, imagine an attacker typing at a terminal where anything that's

typed gets encrypted using a key unknown to the attacker.

In that case, the attacker really does have the ability to mount a complete

Chosen-plaintext attack.

The strongest threat model typically considered is a Chosen-ciphertext attack.

Now in addition to having the ability to carry out a Chosen-plaintext attack

like before.

We also assume the attacker is able to get the parties to decrypt certain cipher

texts of that attacker's choice.

This may sound totally unrealistic but

we'll see later on in the course that the ability to carry out some limited form of

chosen cipher text attack is actually very common and must be defended against.

For concreteness let's assume from now on the simplest threat model, a ciphertext

only attack where the attacker only gets to observe a single ciphertext.

Even within this setting, how should we define security?

Before I continue, you may want to pause the video for a few minutes.

To think about how you would define security in this setting.

One suggestion people sometimes come up with is that it should be impossible for

the attacker to determine the key shared by the parties.

A little thought,

however, should convince you that this is not really the right definition.

For starters, the key is just a means to an end.

But protecting the key is not the goal in itself.

In any case, maintaining secrecy of the key is at best necessary, but

not at all sufficient to ensure that the parties communication remains secret.

In particular it's easy to come up with a trivial encryption scheme

that protects the key completely but

doesn't ensure secrecy of the messages being encrypted at all.

How about this possibility?

Say the encryption scheme is secure if and

only if it is impossible for the attacker to learn the plain text.

This is better but still has problems.

For one, what if I come up with a scheme in which the attacker cannot learn

the entire plaintext but is able to learn 90 percent of the plaintext?

Such a scheme would be considered secure by this definition, but hopefully you

would agree that we don't really want to consider such a scheme secure.

This means we have to keep looking for the right definition.

[SOUND] We can follow the problem I just mentioned by the following definition.

Say a scheme is secure if it is impossible for

the attacker to learn any character of the plain text.

This is a step in the right direction but it ignores the possibility that

the attacker might be able to learn other information about the plaintext.

For example, what if I encrypt someone's salary and

the attacker can't figure out any digit in the salary but can tell whether or

not they make more than $60,000.

That would satisfy this definition but,

again we really wouldn't want to consider such a scheme secure.

Furthermore, it's not entirely clear what it means to learn a character.

What if an attacker is able to guess a character correctly,

does that count as learning a character?

It shouldn't, but how do we rule that out?

Cryptographers have thought about the problem of defining secure encryption for

many years.

The definition they have converged upon,

which takes in to account all the previous considerations, is this one.

An encryption scheme is secure if the following is true.

Regardless of any prior information the attacker has

about the plaintext the ciphertext observed by

the attacker should leak no additional information about the plaintext.

Note first of all that this rules out learning 90 percent of the plaintext.

Or characters of the plaintext, or

even any other type of information about the plaintext.

On the other hand, blindly guessing some character of the plaintext is not

considered a violation of security, because the attacker could have

guessed the character of the plaintext without seeing the ciphertext at all.

That is, as long as seeing the ciphertext does not make it any easier for

the attacker to guess a character of the plaintext.

It's not to be considered a violation of security.

This definition was first proposed in the early 1980s.

And by now has become the generally accepted definition of security.

The question we'll turn to next time is how to mathematically formalize

this definition.

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