This course will introduce you to the foundations of modern cryptography, with an eye toward practical applications.
Perfect Secrecy
Loading...
En provenance du cours de University of Maryland, College Park
Cryptography
511 notes
Explore Related Videos
At Coursera, you will find the best lectures in the world. Here are some of our personalized recommendations for you
À partir de la leçon
Week 1
Introduction to Classical Cryptography
Rencontrer les enseignants
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.
Explorer notre catalogue
Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.
Coursera propose un accès universel à la meilleure formation au monde,
en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.
© 2019 Coursera Inc. Tous droits réservés.
