Last week, we learned a number theory that's needed for public key encryption.
This week we're gonna put this knowledge to work, and we're gonna construct a
number of secure public key encryption schemes. But first, we need to define what
is public key encryption, and what does it mean for public key encryption to be
secure? So let me remind you that in a public key encryption scheme, there is an
encryption algorithm which is usually denoted by E, and there's a decryption
algorithm which we denote by D. However here, the encryption algorithm takes a
public key, while the decryption algorithm takes a secret key. This pair is called a
key pair. And the public key is used for encrypting messages while the secret key
is used for decrypting messages. So in this case a message m is encrypting using
the public key and what comes out of that is the ciphertext c. And similarly the
ciphertext is fed into the decryption algorithm and using the secret key, what
comes out of the decryption algorithm is the original message m. Now public key
encryption has many applications. Last week we saw the classic application which
is session setup, namely, key exchange and for now we're just looking at key exchange
that is secure against eavesdropping only. And if you remember the way the protocol
works, basically Alice, what she would do is she would generate a public key secret
pair. She would send the public key to Bob. Bob will generate a random X, which
is gonna serve as their shared secret, and then he sends X encrypted to Alice,
encrypted under her public key. Alice can decrypt, recover X and now both of them
have this shared secret X which they can use to communicate securely with one
another. The attacker, of course, all he gets to see is just the public key, the
encryption of X under the public key, from which he should not be able to get any
information about X. And we are going to define that more precisely to understand
what it means to not be able to learn anything about X. Public key encryption
actually has many other applications. For example, it's very useful in
non-interactive applications. So think of an email system for example. So here, Bob
wants to send mail to Alice, and as Bob sends the email, the email passes from
mail relay to mail relay until finally it reaches Alice, at which point Alice should
decrypt. The way the email system is set up, is designed for kind of
non-interactive settings where Bob sends the email. And then Alice is supposed to
receive it. And Alice should not be to communicate with Bob in order to decrypt
the email. So in this case, because of the non-interactivity, there's no opportunity
for setting up a shared secret between Alice and Bob. So in this case, what would
happen is, Bob basically would, would send the email encrypted, using Alice's, public
key. So he sends the email. Anyone in the world can send the email encrypted to
Alice, encrypted using her public key. When Alice receives this email, she uses
her secret key to decrypt the ciphertext and recover the plain text message.
Of course the one caveat in a system like this is that in fact Bob needs to somehow
obtain Alice's public key So for now we are just going to assume Bob already has
Alice's public key, but later on, actually, when we talk about digital
signatures we're gonna see how, this can actually be done very efficiently using what's
called public key management and as I said we'll actually get back to that at a later
time. But the main thing I want you to remember, is that public key encryption is
used for session setup. This is very common on the web, where public key
encryption is used to set up a secure key between a web browser and, and web server.
And public key encryption is also very useful for non-interactive applications,
where anyone in the world, non-interactively, needs to send a message
to Alice, they can encrypt the message using Alice's public key, and Alice can decrypt
and recover the plain text. So let me remind you in a bit more detail what a
public key encryption system is. Well, it's made up of three algorithms G, E, and
D. G is called the key generation algorithm. Basically what it will do is it will
generate this key pair, the public key and the secret key. As written here, G takes
no arguments, but in real life, G actually does take an argument called the security
parameter which specifies the size of the keys that are generated by this key
generation algorithm. Then there are these encryption algorithms as usual that take a
public key and a message and produce a ciphertext in a decryption algorithm that
takes the corresponding secret key and a ciphertext and it produces a corresponding
message. And as usual for consistency we say that if we encrypt a message under a
given public key and then decrypt with a corresponding secret key we should get the
original message back. Now what does it mean for a public key encryption to be
secure? I'm going to start off by defining, security against eavesdropping.
And then we're going to define security against active attacks. So the way to
define security against eavesdropping is very similar to the symmetric case we've
already this last week so we're gonna go through this quickly just as a review.
Basically the attack game is defined as follows. We defined these two experiments,
experiment zero and experiment one. At in either experiment the challenger is gonna
generate a public and a secret key pair. He's gonna give the public
key to the adversary. The adversary's gonna output two messages m0 and m1 of
equal length and then what he gets back is either the encryption of m0 or the
encryption of m1. In experiment zero he gets the encryption of m0. In experiment
one he gets the encryption of m1. And then the adversary is supposed to say which one
did he get. Did he get the encryption of m0 or did he get the encryption of m1? So
in this game, the attacker only gets one ciphertext. This corresponds to an
eavesdropping attack where he simply eavesdropped on that ciphertext C. And now
his goal is to tell whether the ciphertext C i s the encryption of M0 or M1. No
tampering on the ciphertext C is allowed just yet. And as usual we say that the
public key encryption scheme is semantically secure if the attacker cannot
distinguish experiment zero from experiment one. In other words he cannot
tell whether he got the encryption of M0, or the encryption of M1. Before we move on
to active attacks, I want to mention a quick relation between the definition we
just saw, And the definition of, of eavesdropping security for symmetric
ciphers. If you remember, when we talked about eavesdropping security for symmetric
ciphers, we distinguished between the case where the key is used once, and the case
where the key is used multiple times. And, in fact we saw that, there's a clear
separation. For example, the onetime pad. Is secure if the key is used to encrypt a
single message, but is completely insecure if the key is used to encrypt multiple
messages. And in fact we had two different definitions if you remember we had a
definition for one-time security, and then we had a separate definition, which was
stronger, when the key was used multiple times. The definition that I showed you on
the previous slide's very similar to the definition of one time security for
symmetric ciphers. And in fact, it turns out that for public key encryption, if a
system is secure under a onetime key, in a sense, it's also secure for a many time
key. So in other words, we don't have to explicitly give the attacker the ability
to, request encryptions of messages of his choice. Because he could just create those
encryptions all by himself. He is given the public key, and therefore he can by
himself encrypt any message he likes. As a result any public key secret pair in some
sense inherently is used to encrypt multiple messages because the attacker
could have just encrypted many, many messages of his choice using the given
public key that we just gave him in the first step. And so, as a result in fact,
the definition of one time security is enough to imply many time security and
that's why we refer to the concept as indistinguishability under a chosen plain
text attach. So this is just a minor point to explain why the settings of public
encryption, we don't need a more complicated definition to capture
eavesdropping security. Now that we understand eavesdropping security, let's
look at more powerful adversaries that can actually mount active attacks. So, in
particular, let's look at the email example. So here, we have our friend Bob
who wants to send mail to his friend Caroline. And Caroline happens to have, an
account at Gmail. And the way this works is basically, the email is sent to the
Gmail server, encrypted. The Gmail server decrypts the email, looks at the, intended
recipients. And then, if it's, the intended recipient is Caroline, it
forwards the email to Caroline. If the intended recipient is the attacker, it
forwards the email to the attacker. This is similar to how Gmail actually works
because the sender would send the email encrypted over SSL to the Gmail server.
The Gmail server would terminate the SSL and then forward the email to the
appropriate recipients. Now suppose Bob encrypts the email using a system that
allows the adversary to tamper with the ciphertext without being detected. For
example, imagine this email is encrypted using Counter Mode, or something like
that. Then when the attacker intercepts this email, he can change the recipient,
so that now the recipient says attacker@gmail.com, and we know that for
Counter Mode, for example, this is quite easy to do. The attacker knows that the
email is intended for Caroline, he is just interested in the email body. So he can
easily change the email recipient to attacker@gmail.com and now when the server
receives the email, he will decrypt it, see that the recipient is supposed to be
attacker, and forward the body to the attacker. And now the attacker was able to
read the body of the email that was intended for Caroline. So this is a
classic example of an active attack, and you notice what the attacker could do
here, is it could decrypt any ciphertext where the intended recipient is to:
attacker. So any ciphertext where the plain text begins with the words "to: attacker". So our goal is
to design public key systems that are secure, even if the attacker can tamper
with ciphertext and possibly decrypt certain cyphertexts. And again, I want to
emphasize that here the attacker's goal was to get the message body. The attacker
already knew that the email is intended for Caroline. And all he had to do was
just change the, intended recipient. So this tampering attack motivates the
definition of chosen ciphertext security. And in fact this is the standard notion of
security for public key encryption. So let me explain how the attack [here procedes] and as I
said our goal is to build systems that are secure under this very, very conservative
notion of encryption. So we have an encryption scheme (G, E, D). And let's say
that's defined over a message space and a ciphertext (M, C) and as usual we're
gonna define two experiments, experiment zero, and experiment one. So 'b' here
says whether the challenger is implementing experiment zero or experiment
one. The challenger begins by generating a public key and a secret key, and then gives
the public key to the adversary. Now the adversary can say, "Well, here are a bunch
of ciphertexts, please decrypt them for me." So here the adversary submits
ciphertext C1 and he gets the decryption of ciphertext C1, namely M1. And he gets
to do this again and again, so he submits ciphertext C2, and he gets the decryption,
which is M2, ciphertext C3, and he gets the decryption M3, and so on and so forth.
Finally, the adversary says, "This squaring phase is over," and now he
submits basically two equal length messages, M0 and M1 as normal, and he
receives in response the challenge ciphertext C, Which is the encryption of M
zero or the encryption of M one. Depending on whether we're in experiment zero or
experiment one. Now, the adversary can continue to issue these ciphertext
queries. So he can continue to issue, decryption requests. So he submits a
ciphertext, and he gets a decryption of that ciphertext, but of course, now, there
has to be a caveat. If the attacker could submit arbitrary ciphertext of his choice,
of course, he could break the challenge. What he would do is he would submit the
challenge ciphertext C as a decryption query. And then he would be told whether
in the challenge phase he was given the encryption of M0 or the encryption of M1.
As a result we put this limitation here, that says that he can in fact submit any
ciphertext of his choice except. For the challenge ciphertext. So the attacker
could ask for the decryption of any ciphertext of his choice other than the
challenge ciphertext. And even though he was given all these decryptions, he still
shouldn't be able to tell whether he was given the encryption of M0 or the
encryption of M1. So you notice this is a very conservative definition. It gives the
attacker more power than what we saw in the previous slide. On the previous slide,
the attacker could only decrypt messages where the plain text began with the words
"to: attacker". Here, we're saying the attacker can decrypt any ciphertext of his choice,
as long as it's different from the challenge ciphertext C. Okay? And then his
goal is to say whether the challenge ciphertext is the encryption of M0 or the
encryption of M1. And as usual, if he can't do that, in other words, his
behavior in experiment zero is basically the same as his behavior in experiment
one, so he wasn't able to distinguish the encryption of M0 from the encryption of
M1, even though he had all this power Then we say that the system is chosen
ciphertext secure, CCA secure. And sometimes there is an acronym, the acronym
for this is indistinguishability under a chosen ciphertext attack, but I'm just
gonna say CCA secured. So let's see how this captures, the email example we saw
before. So suppose the encryption system being used is such that just given the
encryption of a message the attacker can change the intended recipient from to
Alice say to, to Charlie. Then here's how we would win the CCA game. Well in the
first step he's given the public key of course. And then what the attacker will do
is he would issue two equal length messages, namely in the first message, the
body is zero. In the second message the body is one. But both messages are
intended for Alice. And in response, he would be given the challenge ciphertext C.
Okay, so now here we have our challenge ciphertext C. Now what the attacker is
gonna do is he's gonna use his, his ability here to modify the intended
recipient. And he's gonna send back a ciphertext C', where C' is the encryption
of the message to Charlie with body being the challenge body b. So if you remember is
either zero or one. Now, because the plain text is different, we know that the
ciphertext must also be different. So in particular, C prime must be different from
the challenge ciphertext C, yeah? So the C prime here must be different from C. And
as a result, the poor challenger now has to decrypt by definition of the CCA game.
The challenger must decrypt any ciphertext that's not equal to a challenge
ciphertext. So the challenger decrypts give the adversary M prime. Basically he
gave the adversary B, and now the adversary can output the challenge B and
he wins the game with advantage one. So he's advantage with this particular scheme
is one. So, simply because the attacker was able to change the challenge ciphertext
from one recipient to another that allows him to, to win the CCA game with
advantage one. So as I said, chosen ciphertext security turns out actually is
the correct notion of security for public key encryption systems. And it's a very,
very interesting concept, right? Basically, somehow even though the attacker has this ability
to decrypt anything he wants. Other than the challenge ciphertext, still he can't
learn what the challenge ciphertext is. And so the goal for the remainder of this module
and actually the next module as well, is to construct CCA secure systems. It's
actually quite remarkable that this is achievable and I'm going to show you
exactly how to do it. And in fact those CCA secure systems that we build are the
ones that are used in the real world. And every time a system has tried to deploy
a public key encryption mechanism that's not CCA secure someone has come up with an
attack and was able to break it. And we're going to see some of these example attacks
actually in the next few segments.