Cryptography is an indispensable tool for protecting information in computer systems. In this course you will learn the inner workings of cryptographic systems and how to correctly use them in real-world applications. The course begins with a detailed discussion of how two parties who have a shared secret key can communicate securely when a powerful adversary eavesdrops and tampers with traffic. We will examine many deployed protocols and analyze mistakes in existing systems. The second half of the course discusses public-key techniques that let two parties generate a shared secret key. Throughout the course participants will be exposed to many exciting open problems in the field and work on fun (optional) programming projects. In a second course (Crypto II) we will cover more advanced cryptographic tasks such as zero-knowledge, privacy mechanisms, and other forms of encryption.
Semantic Security
Loading...
Из курса от партнера Stanford University
Cryptography I
2503 оценки
Из урока
Course overview and stream ciphers
Week 1. This week's topic is an overview of what cryptography is about as well as our first example ciphers. You will learn about pseudo-randomness and how to use it for encryption. We will also look at a few basic definitions of secure encryption.
Познакомьтесь с преподавателями
Dan BonehProfessor
Computer Science
My goal for the next few segments is to show you that if we use a secure PRG We'll
get a secure stream safer. The first thing we have to do is define is, what does it
mean for a stream safer to be secure? So whenever we define security we always
define it in terms of what can the attacker do? And what is the attacker
trying to do? In the context of stream ciphers remember these are only used
with a onetime key, and as a result the most the attacker is ever going to see is
just one cypher text encrypted using the key that we're using. And so we're gonna
limit the attackers? ability to basically obtain just one cypher text. And in
fact later on we're going to allow the attacker to do much, much, much more, but
for now we're just gonna give him one cypher text. And we wanted to find,
what does it mean for the cypher to be secure? So the first definition that
comes to mind is basically to say, well maybe we wanna require that the attacker
can't actually recover the secret key. Okay so given ciphertext you
shouldn't be able to recover the secret key. But that's a terrible definition
because think about the falling brilliant cipher but the way we encrypt the
message using a key K is basically we just output the message. Okay this
is a brilliant cipher yeah of course it doesn't do anything given a message just
output a message as the cipher text. This is not a particularly good encryption
scheme; however, given the cipher text, mainly the message the poor attacker
cannot recover the key because he doesn't know what the key is. And so as a result
this cipher which clearly is insecure, would be considered secure under this
requirement for security. So this definition will be no good. Okay so it's
recovering the secret key is the wrong way to define security. So the next thing we
can kinda attempt is basically just say, well maybe the attacker doesn't care about
the secret key, what he really cares about are the plain text. So maybe it should be
hard for the attacker to recover the entire plain text. But even that doesn't
work because let's think about the following encryption scheme. So suppose
what this encryption scheme does is it takes two messages, so I'm gonna use two
lines to denote concatenation of two messages M0 line, line M1 means
concatenate M0 and M1. And imagine what the scheme does is really it outputs
M0 in the clear and concatenate to that the encryption of M1. Perhaps even
using the One Time Pad okay? And so here the attacker is gonna be given one
cipher text. And his goal would be to recover the entire plain texts. But the
poor attacker can't do that because here maybe we've encrypted M1 using the One
Time Pad so the attacker can't actually recover M1 because we know the
One Time Pad is secure given just one cipher text. So this construction
would satisfy the definition but unfortunately clearly this is not a secure
encryption scheme because we just leaked half of the plain text. M0 is
completely available to the attacker so even though he can't recover all of the
plain text he might be able to recover most of the plain text, and that's clearly
unsecured. So of course we already know the solution to this and we talked about
Shanon definition of security perfect secrecy where Shannon's idea was that in
fact when the attacker intercepts a cipher text he should learn absolutely no
information about the plain texts. He shouldn't even learn one bit about the
plain text or even he shouldn't learn, he shouldn't even be able to predict a little
bit about a bid of the plain text. Absolutely no information about the plain text.
So let's recall very briefly Shannon's concept of perfect secrecy
basically we said that you know given a cipher We said the cipher has perfect
secrecy if given two messages of the same length it so happens that the distribution
of cipher texts. Yet if we pick a random key and we look into distribution of
cipher texts we encrypt M0 we get exactly the same distribution as when we
encrypt M1. The intuition here was that if the advisory observes the cipher texts
then he doesn't know whether it came from the distribution the result of encrypting
M0 or it came from the distribution as the result of encrypting M1. And as a
result he can't tell whether we encrypted M0 or M1. And that's true for all
messages of the same length and as a result a poor attacker doesn't really know
what message was encrypted. Of course we already said that this definition is too
strong in the sense that it requires really long keys if cipher has short
keys can't possibly satisfy this definition in a particular stream ciphers
can satisfy this definition. Okay so let's try to weaken the definition a little bit
and let's think to the previous segment, and we can say that instead of requiring
the two distributions to be absolutely identical what we can require is, is that
two distributions just be computationally indistinguishable. In other words a poor,
efficient attacker cannot distinguish the two distributions even though the
distributions might be very, very, very different. That just given a sample for
one distribution and a sample for another distribution the attacker can't tell which
distribution he was given a sample from. It turns out this definition is actually
almost right, but it's still a little too strong, that still cannot be satisfied, so
we have to add one more constraint, and that is that instead of saying that this
definition should have hold for all M0 and M1. It is to hold for only pairs M0 M1
that the attackers could actually exhibit. Okay so this actually
leads us to the definition of semantics security. And so, again this is semantics
security for one time key in other words when the attacker is only given one cipher
text. And so the way we define semantic security is by defining two experiments,
okay we'll define experiment 0 and experiment 1. And more generally we will
think of these as experiments parentheses B, where B can be zero or one. Okay so the
way the experiment is defined is as follows, we have an adversary that's
trying to break the system. An adversary A, that's kinda the analog of statistical
tests in the world of pseudo random generators. And then the challenger does
the following, so really we have two challengers, but the challengers are so
similar that we can just describe them as a single challenger that in one case takes
his inputs bits set to zero, and the other case takes his inputs bits set to
one. And let me show you what these challengers do. The first thing the
challenger is gonna do is it's gonna pick a random key and then the adversary
basically is going to output two messages M0 and M1. Okay so this is an explicit
pair of messages that the attacker wants to be challenged on and as usual we're not
trying to hide the length of the messages, we require that the messages be equal
length. And then the challenger basically will output either the encryption of M0
or the encryption of M1, okay so in experiment 0 the challenger will output
the encryption of M0. In experiment 1 the challenger will output the encryption
of M1. Okay so that the difference between the two experiments. And then the
adversary is trying to guess basically whether he was given the encryption of M0
or given the encryption of M1. Okay so here's a little bit of notation let's
define the events Wb to be the events that an experiment B the adversary output one.
Okay so that is just an event that basically in experiment zero W0 means that
the adversary output one and in experiment one W1 means the adversary output one. And
now we can define the advantage of this adversary, basically to say that this is
called the semantics security advantage of the adversary A against the scheme E,
to be the difference of the probability of these two events. In other words we are
looking at whether the adversary behaves differently when he was given the
encryption of M0 from when he was given the encryption of M1. And I wanna make
sure this is clear so I'm gonna say it one more time. So in experiment zero he was
given the encryption of M0 and in experiment one he was given the encryption
of M1. Now we're just interested in whether the adversary output 1 or not.
... In these experiments. If in both experiments the adversary output 1 with
the same probability that means the adversary wasn't able to distinguish the
two experiments. Experiments zero basically looks to the adversary the same
as experiment one because in both cases upload one with the same probability.
However if the adversary is able to output 1 in one experiment with significantly
different probability than in the other experiment, then the adversary was
actually able to distinguish the two experiments. Okay so... To say this more
formally, essentially the advantage again because it's the difference of two
probabilities the advantage is a number between zero and one. If the advantage is
close to zero that means that the adversary was not able to distinguish
experiment zero from experiment one. However if the advantage is close to one,
that means the adversary was very well able to distinguish experiment zero from
experiment one and that really means that he was able to distinguish an encryption
of M0 from an encryption of M1, okay?So that's out definition. Actually
that is just the definition of the advantage and the definition is just what
you would expect basically we'll say that a symmetric encryption scheme is
semantically secure if for all efficient adversaries here I'll put these in quotes
again, "For all efficient adversaries the advantage is negligible." In other words,
no efficient adversary can distinguish the encryption of M0 from the encryption
of M1 and basically this is what it says repeatedly that for these two
messages that the adversary was able to exhibit he wasn't able to distinguish
these two distributions. Now I want to show you this, this is actually a very
elegant definition. It might not seem so right away, but I want to show you some
implications of this definition and you'll see exactly why the definition is the way
it is. Okay so let's look at some examples. So the first example is suppose
we have a broken encryption scheme, in other words suppose we have an adversary A
that somehow given the cipher text he is always able to deduce the least
significant bit of the plain text. Okay so given the encryption of M0, this adversary
is able to deduce the least significant bit of M0. So that is a terrible
encryption scheme because it basically leaks the least significant bit of the
plain text just given the cipher text. So I want to show you that this scheme is
therefore semantically secure so that kind of shows that if a system is semantically
secure than there is no attacker of this type. Okay so let's see why is the system
not semantically secure well so what we are gonna do is we're gonna basically use
our adversary who is able to learn our most insignificant bits, we're going to
use him to break semantic security so we're going to use him to distinguish
experiment zero from experiment one Okay so here is what we are going to do. We are
algorithm B, we are going to be algorithm B and this algorithm B is going to use
algorithm A in its belly. Okay so the first thing that is going to happen is of
course the challenger is going to choose a random key. The first thing that is going
to happen is that we need to output two messages. The messages that we are going
to output basically are going to have differently significant bits. So one
message is going to end with zero and one message is going to end with one. Now what
is the challenger going to do? The challenger is going to give us the
encryption of either M0 or M1, depending on whether in experiment 0 or
in experiment 1. And then we just forward this cipher text to the adversary
okay so the adversary A. Now what is the property of adversary A? Given the cipher
text, adversary A can tell us what the least significant bits of the plain text is.
In other words the adversary is going to output the least significant bits of M0 or M1
but low and behold that's basically the bit B. And then we're just
going to output that as our guest so let?s call this thing B prime Okay so now this
describes the semantic security adversary. And now you tell me what is the semantic
security advantage of this adversary? Well so let's see. In experiment zero, what is
the probability that adversary B outputs one? Well in experiment zero it is always
given the encryption of M zero and therefore adversary A is always output the
least significant bit of M zero which always happens to be zero. In experiment
zero, B always outputs zero. So the probability that outputs one is zero.
However in experiment one, we're given the encryption of M1. So how likely is
adversary B to output one in experiment one well it always outputs one, again by
the properties of algorithm A and therefore the advantage basically is one.
So this is a huge advantage, it's as big as it's gonna get. Which means that this
adversary completely broke the system. Okay so we consider, so under semantic
security basically just deducing the least significant bits is enough to completely
break the system under a semantic security definition. Okay, now the interesting
thing here of course is that this is not just about the least significant bit, in
fact of the message for example the most significant bit, you know
bit number seven Maybe the XOR of all the bits in the message and so on
and so forth any kind of information, any bit about the plain text they can be
learned basically would mean that the system is not semantically secure. So
basically all the adversary would have to do would be to come up with two messages
M0 and M1 such that under one thing that they learned it's the value zero and then
the other thing, the value, is one. So for example if A was able to learn the XOR
bits of the message then M0 and M1 would just have different
XOR for all the bits of their messages and then this adversary A would
also be sufficient to break semantic security. Okay so, basically for cipher
is semantically secure then no bit of information is revealed to an
efficient adversary. Okay so this is exactly a concept of perfect secrecy only
applied just efficient adversaries rather than all adversaries. So the next
thing I wanna show you is that in fact the one time pad in fact is
semantically secure, they better be semantically secure because it's in fact,
it's more than that it's perfectly secure. So let's see why that's true. Well so
again it's one of these experiments, so suppose we have an adversary that claims
to break semantic security of the one time pad. The first the adversary is gonna do
is he's gonna output two messages M0 and M1 of the same length.
Now what does he get back as a challenge? As a challenge, he gets either the encryption
of M0 or the encryption of M1 under the one time pad.
And he's trying to distinguish between those two possible cipher texts that he gets, right?
In experiment zero, he gets the encryption of M0 and in experiment one, he gets the
encryption of M1. Well so let me ask you, so what is the advantage of adversary
A against the one time patent? So I remember that the property of the ones I
had is that, that K, XOR M0 is distributed identically to K, XOR M1.
In other words, these distributions are absolutely identical distribution,
distributions, identical. This is a property of XOR. If we XOR the random pad
K with anything, either M0 or M1, we get uniform distribution. So in both
cases, algorithm A is given as in input exactly the same distribution. Maybe the
uniform distribution on cipher texts. And therefore it's gonna behave exactly the
same in both cases because it was given the exact distribution as input. And as a
result, its advantage is zero, which means that the onetime pad is semantically
secure. Now the interesting thing here is not only is it semantically secure, it's
semantically secure for all adversaries. We don't even have to restrict the
adversaries to be efficient. No adversary, doesn't matter how smart you are, no
adversary will be able to distinguish K XOR M0 from K XOR M1 because the two
distributions are identical. Okay, so the one time pad is semantically secure. Okay,
so that completes our definition of semantic security so the next thing we're
going to do is prove to the secure PRG, in fact implies that the stream cipher is
semantically secure.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2019 Все права защищены.
