[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:03.58,Default,,0000,0000,0000,,Last week, we learned a number theory\Nthat's needed for public key encryption.
Dialogue: 0,0:00:03.58,0:00:07.17,Default,,0000,0000,0000,,This week we're gonna put this knowledge\Nto work, and we're gonna construct a
Dialogue: 0,0:00:07.17,0:00:10.89,Default,,0000,0000,0000,,number of secure public key encryption\Nschemes. But first, we need to define what
Dialogue: 0,0:00:10.89,0:00:14.56,Default,,0000,0000,0000,,is public key encryption, and what does it\Nmean for public key encryption to be
Dialogue: 0,0:00:14.56,0:00:18.24,Default,,0000,0000,0000,,secure? So let me remind you that in a\Npublic key encryption scheme, there is an
Dialogue: 0,0:00:18.24,0:00:21.78,Default,,0000,0000,0000,,encryption algorithm which is usually\Ndenoted by E, and there's a decryption
Dialogue: 0,0:00:21.78,0:00:25.36,Default,,0000,0000,0000,,algorithm which we denote by D. However\Nhere, the encryption algorithm takes a
Dialogue: 0,0:00:25.36,0:00:29.48,Default,,0000,0000,0000,,public key, while the decryption algorithm\Ntakes a secret key. This pair is called a
Dialogue: 0,0:00:29.48,0:00:34.36,Default,,0000,0000,0000,,key pair. And the public key is used for\Nencrypting messages while the secret key
Dialogue: 0,0:00:34.36,0:00:39.00,Default,,0000,0000,0000,,is used for decrypting messages. So in\Nthis case a message m is encrypting using
Dialogue: 0,0:00:39.00,0:00:43.88,Default,,0000,0000,0000,,the public key and what comes out of that\Nis the ciphertext c. And similarly the
Dialogue: 0,0:00:43.88,0:00:48.64,Default,,0000,0000,0000,,ciphertext is fed into the decryption\Nalgorithm and using the secret key, what
Dialogue: 0,0:00:48.64,0:00:53.58,Default,,0000,0000,0000,,comes out of the decryption algorithm is\Nthe original message m. Now public key
Dialogue: 0,0:00:53.58,0:00:57.99,Default,,0000,0000,0000,,encryption has many applications. Last\Nweek we saw the classic application which
Dialogue: 0,0:00:57.99,0:01:02.46,Default,,0000,0000,0000,,is session setup, namely, key exchange and\Nfor now we're just looking at key exchange
Dialogue: 0,0:01:02.46,0:01:06.87,Default,,0000,0000,0000,,that is secure against eavesdropping only.\NAnd if you remember the way the protocol
Dialogue: 0,0:01:06.87,0:01:11.23,Default,,0000,0000,0000,,works, basically Alice, what she would do\Nis she would generate a public key secret
Dialogue: 0,0:01:11.23,0:01:15.55,Default,,0000,0000,0000,,pair. She would send the public key to\NBob. Bob will generate a random X, which
Dialogue: 0,0:01:15.55,0:01:20.14,Default,,0000,0000,0000,,is gonna serve as their shared secret, and\Nthen he sends X encrypted to Alice,
Dialogue: 0,0:01:20.14,0:01:24.90,Default,,0000,0000,0000,,encrypted under her public key. Alice can\Ndecrypt, recover X and now both of them
Dialogue: 0,0:01:24.90,0:01:29.55,Default,,0000,0000,0000,,have this shared secret X which they can\Nuse to communicate securely with one
Dialogue: 0,0:01:29.55,0:01:34.14,Default,,0000,0000,0000,,another. The attacker, of course, all he\Ngets to see is just the public key, the
Dialogue: 0,0:01:34.14,0:01:38.97,Default,,0000,0000,0000,,encryption of X under the public key, from\Nwhich he should not be able to get any
Dialogue: 0,0:01:38.97,0:01:43.80,Default,,0000,0000,0000,,information about X. And we are going to\Ndefine that more precisely to understand
Dialogue: 0,0:01:43.80,0:01:48.51,Default,,0000,0000,0000,,what it means to not be able to learn\Nanything about X. Public key encryption
Dialogue: 0,0:01:48.51,0:01:52.52,Default,,0000,0000,0000,,actually has many other applications. For\Nexample, it's very useful in
Dialogue: 0,0:01:52.52,0:01:57.24,Default,,0000,0000,0000,,non-interactive applications. So think of\Nan email system for example. So here, Bob
Dialogue: 0,0:01:57.24,0:02:01.72,Default,,0000,0000,0000,,wants to send mail to Alice, and as Bob\Nsends the email, the email passes from
Dialogue: 0,0:02:01.72,0:02:06.60,Default,,0000,0000,0000,,mail relay to mail relay until finally it\Nreaches Alice, at which point Alice should
Dialogue: 0,0:02:06.60,0:02:10.50,Default,,0000,0000,0000,,decrypt. The way the email system is set\Nup, is designed for kind of
Dialogue: 0,0:02:10.50,0:02:15.04,Default,,0000,0000,0000,,non-interactive settings where Bob sends\Nthe email. And then Alice is supposed to
Dialogue: 0,0:02:15.04,0:02:19.20,Default,,0000,0000,0000,,receive it. And Alice should not be to\Ncommunicate with Bob in order to decrypt
Dialogue: 0,0:02:19.20,0:02:23.50,Default,,0000,0000,0000,,the email. So in this case, because of the\Nnon-interactivity, there's no opportunity
Dialogue: 0,0:02:23.50,0:02:27.70,Default,,0000,0000,0000,,for setting up a shared secret between\NAlice and Bob. So in this case, what would
Dialogue: 0,0:02:27.70,0:02:32.17,Default,,0000,0000,0000,,happen is, Bob basically would, would send\Nthe email encrypted, using Alice's, public
Dialogue: 0,0:02:32.17,0:02:36.57,Default,,0000,0000,0000,,key. So he sends the email. Anyone in the\Nworld can send the email encrypted to
Dialogue: 0,0:02:36.57,0:02:41.10,Default,,0000,0000,0000,,Alice, encrypted using her public key.\NWhen Alice receives this email, she uses
Dialogue: 0,0:02:41.10,0:02:45.75,Default,,0000,0000,0000,,her secret key to decrypt the ciphertext and recover the plain text message.
Dialogue: 0,0:02:45.75,0:02:50.51,Default,,0000,0000,0000,,Of course the one caveat in a system like\Nthis is that in fact Bob needs to somehow
Dialogue: 0,0:02:50.51,0:02:54.80,Default,,0000,0000,0000,,obtain Alice's public key So for now we\Nare just going to assume Bob already has
Dialogue: 0,0:02:54.80,0:02:58.30,Default,,0000,0000,0000,,Alice's public key, but later on,\Nactually, when we talk about digital
Dialogue: 0,0:02:58.30,0:03:02.46,Default,,0000,0000,0000,,signatures we're gonna see how, this can\Nactually be done very efficiently using what's
Dialogue: 0,0:03:02.46,0:03:06.82,Default,,0000,0000,0000,,called public key management and as I said\Nwe'll actually get back to that at a later
Dialogue: 0,0:03:06.82,0:03:10.93,Default,,0000,0000,0000,,time. But the main thing I want you to\Nremember, is that public key encryption is
Dialogue: 0,0:03:10.93,0:03:14.58,Default,,0000,0000,0000,,used for session setup. This is very\Ncommon on the web, where public key
Dialogue: 0,0:03:14.58,0:03:18.84,Default,,0000,0000,0000,,encryption is used to set up a secure key\Nbetween a web browser and, and web server.
Dialogue: 0,0:03:18.84,0:03:22.90,Default,,0000,0000,0000,,And public key encryption is also very\Nuseful for non-interactive applications,
Dialogue: 0,0:03:22.90,0:03:26.39,Default,,0000,0000,0000,,where anyone in the world,\Nnon-interactively, needs to send a message
Dialogue: 0,0:03:26.39,0:03:30.65,Default,,0000,0000,0000,,to Alice, they can encrypt the message using\NAlice's public key, and Alice can decrypt
Dialogue: 0,0:03:30.65,0:03:36.10,Default,,0000,0000,0000,,and recover the plain text. So let me\Nremind you in a bit more detail what a
Dialogue: 0,0:03:36.10,0:03:40.35,Default,,0000,0000,0000,,public key encryption system is. Well,\Nit's made up of three algorithms G, E, and
Dialogue: 0,0:03:40.35,0:03:44.43,Default,,0000,0000,0000,,D. G is called the key generation algorithm.\NBasically what it will do is it will
Dialogue: 0,0:03:44.43,0:03:48.67,Default,,0000,0000,0000,,generate this key pair, the public key and\Nthe secret key. As written here, G takes
Dialogue: 0,0:03:48.67,0:03:53.02,Default,,0000,0000,0000,,no arguments, but in real life, G actually\Ndoes take an argument called the security
Dialogue: 0,0:03:53.02,0:03:57.26,Default,,0000,0000,0000,,parameter which specifies the size of the\Nkeys that are generated by this key
Dialogue: 0,0:03:57.26,0:04:01.73,Default,,0000,0000,0000,,generation algorithm. Then there are these\Nencryption algorithms as usual that take a
Dialogue: 0,0:04:01.73,0:04:06.05,Default,,0000,0000,0000,,public key and a message and produce a\Nciphertext in a decryption algorithm that
Dialogue: 0,0:04:06.05,0:04:10.53,Default,,0000,0000,0000,,takes the corresponding secret key and a\Nciphertext and it produces a corresponding
Dialogue: 0,0:04:10.53,0:04:14.96,Default,,0000,0000,0000,,message. And as usual for consistency we\Nsay that if we encrypt a message under a
Dialogue: 0,0:04:14.96,0:04:19.38,Default,,0000,0000,0000,,given public key and then decrypt with a\Ncorresponding secret key we should get the
Dialogue: 0,0:04:19.38,0:04:23.85,Default,,0000,0000,0000,,original message back. Now what does it\Nmean for a public key encryption to be
Dialogue: 0,0:04:23.85,0:04:27.91,Default,,0000,0000,0000,,secure? I'm going to start off by\Ndefining, security against eavesdropping.
Dialogue: 0,0:04:27.91,0:04:32.00,Default,,0000,0000,0000,,And then we're going to define security\Nagainst active attacks. So the way to
Dialogue: 0,0:04:32.00,0:04:36.24,Default,,0000,0000,0000,,define security against eavesdropping is\Nvery similar to the symmetric case we've
Dialogue: 0,0:04:36.24,0:04:40.63,Default,,0000,0000,0000,,already this last week so we're gonna go\Nthrough this quickly just as a review.
Dialogue: 0,0:04:40.63,0:04:44.81,Default,,0000,0000,0000,,Basically the attack game is defined as\Nfollows. We defined these two experiments,
Dialogue: 0,0:04:44.81,0:04:49.25,Default,,0000,0000,0000,,experiment zero and experiment one. At in\Neither experiment the challenger is gonna
Dialogue: 0,0:04:49.25,0:04:52.96,Default,,0000,0000,0000,,generate a public and a secret key pair. He's gonna give the public
Dialogue: 0,0:04:52.96,0:04:57.34,Default,,0000,0000,0000,,key to the adversary. The adversary's\Ngonna output two messages m0 and m1 of
Dialogue: 0,0:04:57.34,0:05:01.66,Default,,0000,0000,0000,,equal length and then what he gets back is\Neither the encryption of m0 or the
Dialogue: 0,0:05:01.66,0:05:06.04,Default,,0000,0000,0000,,encryption of m1. In experiment zero he\Ngets the encryption of m0. In experiment
Dialogue: 0,0:05:06.04,0:05:10.75,Default,,0000,0000,0000,,one he gets the encryption of m1. And then\Nthe adversary is supposed to say which one
Dialogue: 0,0:05:10.75,0:05:15.24,Default,,0000,0000,0000,,did he get. Did he get the encryption of\Nm0 or did he get the encryption of m1? So
Dialogue: 0,0:05:15.24,0:05:19.68,Default,,0000,0000,0000,,in this game, the attacker only gets one\Nciphertext. This corresponds to an
Dialogue: 0,0:05:19.68,0:05:24.23,Default,,0000,0000,0000,,eavesdropping attack where he simply\Neavesdropped on that ciphertext C. And now
Dialogue: 0,0:05:24.23,0:05:28.72,Default,,0000,0000,0000,,his goal is to tell whether the ciphertext\NC i s the encryption of M0 or M1. No
Dialogue: 0,0:05:28.72,0:05:34.22,Default,,0000,0000,0000,,tampering on the ciphertext C is allowed\Njust yet. And as usual we say that the
Dialogue: 0,0:05:34.22,0:05:38.21,Default,,0000,0000,0000,,public key encryption scheme is\Nsemantically secure if the attacker cannot
Dialogue: 0,0:05:38.21,0:05:42.08,Default,,0000,0000,0000,,distinguish experiment zero from\Nexperiment one. In other words he cannot
Dialogue: 0,0:05:42.08,0:05:47.76,Default,,0000,0000,0000,,tell whether he got the encryption of M0,\Nor the encryption of M1. Before we move on
Dialogue: 0,0:05:47.76,0:05:52.31,Default,,0000,0000,0000,,to active attacks, I want to mention a\Nquick relation between the definition we
Dialogue: 0,0:05:52.31,0:05:56.10,Default,,0000,0000,0000,,just saw, And the definition of, of\Neavesdropping security for symmetric
Dialogue: 0,0:05:56.10,0:06:00.44,Default,,0000,0000,0000,,ciphers. If you remember, when we talked\Nabout eavesdropping security for symmetric
Dialogue: 0,0:06:00.44,0:06:04.77,Default,,0000,0000,0000,,ciphers, we distinguished between the case\Nwhere the key is used once, and the case
Dialogue: 0,0:06:04.77,0:06:08.100,Default,,0000,0000,0000,,where the key is used multiple times. And,\Nin fact we saw that, there's a clear
Dialogue: 0,0:06:08.100,0:06:13.36,Default,,0000,0000,0000,,separation. For example, the onetime pad.\NIs secure if the key is used to encrypt a
Dialogue: 0,0:06:13.36,0:06:17.38,Default,,0000,0000,0000,,single message, but is completely insecure\Nif the key is used to encrypt multiple
Dialogue: 0,0:06:17.38,0:06:21.36,Default,,0000,0000,0000,,messages. And in fact we had two different\Ndefinitions if you remember we had a
Dialogue: 0,0:06:21.36,0:06:25.38,Default,,0000,0000,0000,,definition for one-time security, and then\Nwe had a separate definition, which was
Dialogue: 0,0:06:25.38,0:06:29.70,Default,,0000,0000,0000,,stronger, when the key was used multiple\Ntimes. The definition that I showed you on
Dialogue: 0,0:06:29.70,0:06:34.04,Default,,0000,0000,0000,,the previous slide's very similar to the\Ndefinition of one time security for
Dialogue: 0,0:06:34.04,0:06:38.50,Default,,0000,0000,0000,,symmetric ciphers. And in fact, it turns\Nout that for public key encryption, if a
Dialogue: 0,0:06:38.50,0:06:43.12,Default,,0000,0000,0000,,system is secure under a onetime key, in a\Nsense, it's also secure for a many time
Dialogue: 0,0:06:43.12,0:06:47.93,Default,,0000,0000,0000,,key. So in other words, we don't have to\Nexplicitly give the attacker the ability
Dialogue: 0,0:06:47.93,0:06:53.17,Default,,0000,0000,0000,,to, request encryptions of messages of his\Nchoice. Because he could just create those
Dialogue: 0,0:06:53.17,0:06:57.87,Default,,0000,0000,0000,,encryptions all by himself. He is given\Nthe public key, and therefore he can by
Dialogue: 0,0:06:57.87,0:07:04.67,Default,,0000,0000,0000,,himself encrypt any message he likes. As a\Nresult any public key secret pair in some
Dialogue: 0,0:07:04.67,0:07:09.29,Default,,0000,0000,0000,,sense inherently is used to encrypt\Nmultiple messages because the attacker
Dialogue: 0,0:07:09.29,0:07:13.90,Default,,0000,0000,0000,,could have just encrypted many, many\Nmessages of his choice using the given
Dialogue: 0,0:07:13.90,0:07:18.89,Default,,0000,0000,0000,,public key that we just gave him in the\Nfirst step. And so, as a result in fact,
Dialogue: 0,0:07:18.89,0:07:23.69,Default,,0000,0000,0000,,the definition of one time security is\Nenough to imply many time security and
Dialogue: 0,0:07:23.69,0:07:28.80,Default,,0000,0000,0000,,that's why we refer to the concept as\Nindistinguishability under a chosen plain
Dialogue: 0,0:07:28.80,0:07:34.01,Default,,0000,0000,0000,,text attach. So this is just a minor point\Nto explain why the settings of public
Dialogue: 0,0:07:34.01,0:07:37.77,Default,,0000,0000,0000,,encryption, we don't need a more\Ncomplicated definition to capture
Dialogue: 0,0:07:37.77,0:07:42.52,Default,,0000,0000,0000,,eavesdropping security. Now that we\Nunderstand eavesdropping security, let's
Dialogue: 0,0:07:42.52,0:07:47.34,Default,,0000,0000,0000,,look at more powerful adversaries that can\Nactually mount active attacks. So, in
Dialogue: 0,0:07:47.34,0:07:51.58,Default,,0000,0000,0000,,particular, let's look at the email\Nexample. So here, we have our friend Bob
Dialogue: 0,0:07:51.58,0:07:56.23,Default,,0000,0000,0000,,who wants to send mail to his friend\NCaroline. And Caroline happens to have, an
Dialogue: 0,0:07:56.23,0:08:00.70,Default,,0000,0000,0000,,account at Gmail. And the way this works\Nis basically, the email is sent to the
Dialogue: 0,0:08:00.70,0:08:05.51,Default,,0000,0000,0000,,Gmail server, encrypted. The Gmail server\Ndecrypts the email, looks at the, intended
Dialogue: 0,0:08:05.51,0:08:09.30,Default,,0000,0000,0000,,recipients. And then, if it's, the\Nintended recipient is Caroline, it
Dialogue: 0,0:08:09.30,0:08:13.65,Default,,0000,0000,0000,,forwards the email to Caroline. If the\Nintended recipient is the attacker, it
Dialogue: 0,0:08:13.65,0:08:18.57,Default,,0000,0000,0000,,forwards the email to the attacker. This\Nis similar to how Gmail actually works
Dialogue: 0,0:08:18.57,0:08:23.44,Default,,0000,0000,0000,,because the sender would send the email\Nencrypted over SSL to the Gmail server.
Dialogue: 0,0:08:23.44,0:08:28.09,Default,,0000,0000,0000,,The Gmail server would terminate the SSL\Nand then forward the email to the
Dialogue: 0,0:08:28.09,0:08:33.08,Default,,0000,0000,0000,,appropriate recipients. Now suppose Bob\Nencrypts the email using a system that
Dialogue: 0,0:08:33.08,0:08:37.76,Default,,0000,0000,0000,,allows the adversary to tamper with the\Nciphertext without being detected. For
Dialogue: 0,0:08:37.76,0:08:42.39,Default,,0000,0000,0000,,example, imagine this email is encrypted\Nusing Counter Mode, or something like
Dialogue: 0,0:08:42.39,0:08:47.07,Default,,0000,0000,0000,,that. Then when the attacker intercepts\Nthis email, he can change the recipient,
Dialogue: 0,0:08:47.07,0:08:50.73,Default,,0000,0000,0000,,so that now the recipient says\Nattacker@gmail.com, and we know that for
Dialogue: 0,0:08:50.73,0:08:55.42,Default,,0000,0000,0000,,Counter Mode, for example, this is quite\Neasy to do. The attacker knows that the
Dialogue: 0,0:08:55.42,0:09:00.28,Default,,0000,0000,0000,,email is intended for Caroline, he is just\Ninterested in the email body. So he can
Dialogue: 0,0:09:00.28,0:09:04.23,Default,,0000,0000,0000,,easily change the email recipient to\Nattacker@gmail.com and now when the server
Dialogue: 0,0:09:04.23,0:09:08.13,Default,,0000,0000,0000,,receives the email, he will decrypt it,\Nsee that the recipient is supposed to be
Dialogue: 0,0:09:08.13,0:09:12.03,Default,,0000,0000,0000,,attacker, and forward the body to the\Nattacker. And now the attacker was able to
Dialogue: 0,0:09:12.03,0:09:16.02,Default,,0000,0000,0000,,read the body of the email that was\Nintended for Caroline. So this is a
Dialogue: 0,0:09:16.02,0:09:21.20,Default,,0000,0000,0000,,classic example of an active attack, and\Nyou notice what the attacker could do
Dialogue: 0,0:09:21.20,0:09:26.17,Default,,0000,0000,0000,,here, is it could decrypt any ciphertext\Nwhere the intended recipient is to:
Dialogue: 0,0:09:26.17,0:09:31.55,Default,,0000,0000,0000,,attacker. So any ciphertext where the plain\Ntext begins with the words "to: attacker". So our goal is
Dialogue: 0,0:09:31.55,0:09:36.66,Default,,0000,0000,0000,,to design public key systems that are\Nsecure, even if the attacker can tamper
Dialogue: 0,0:09:36.66,0:09:42.100,Default,,0000,0000,0000,,with ciphertext and possibly decrypt\Ncertain cyphertexts. And again, I want to
Dialogue: 0,0:09:42.100,0:09:47.61,Default,,0000,0000,0000,,emphasize that here the attacker's goal\Nwas to get the message body. The attacker
Dialogue: 0,0:09:47.61,0:09:52.06,Default,,0000,0000,0000,,already knew that the email is intended\Nfor Caroline. And all he had to do was
Dialogue: 0,0:09:52.06,0:09:56.86,Default,,0000,0000,0000,,just change the, intended recipient. So\Nthis tampering attack motivates the
Dialogue: 0,0:09:56.86,0:10:01.62,Default,,0000,0000,0000,,definition of chosen ciphertext security.\NAnd in fact this is the standard notion of
Dialogue: 0,0:10:01.62,0:10:07.46,Default,,0000,0000,0000,,security for public key encryption. So let\Nme explain how the attack [here procedes] and as I
Dialogue: 0,0:10:07.46,0:10:11.90,Default,,0000,0000,0000,,said our goal is to build systems that are\Nsecure under this very, very conservative
Dialogue: 0,0:10:11.90,0:10:15.76,Default,,0000,0000,0000,,notion of encryption. So we have an\Nencryption scheme (G, E, D). And let's say
Dialogue: 0,0:10:15.76,0:10:20.14,Default,,0000,0000,0000,,that's defined over a message space and\Na ciphertext (M, C) and as usual we're
Dialogue: 0,0:10:20.14,0:10:24.31,Default,,0000,0000,0000,,gonna define two experiments, experiment\Nzero, and experiment one. So 'b' here
Dialogue: 0,0:10:24.31,0:10:28.22,Default,,0000,0000,0000,,says whether the challenger is\Nimplementing experiment zero or experiment
Dialogue: 0,0:10:28.22,0:10:32.66,Default,,0000,0000,0000,,one. The challenger begins by generating a\Npublic key and a secret key, and then gives
Dialogue: 0,0:10:32.66,0:10:37.25,Default,,0000,0000,0000,,the public key to the adversary. Now the\Nadversary can say, "Well, here are a bunch
Dialogue: 0,0:10:37.25,0:10:41.61,Default,,0000,0000,0000,,of ciphertexts, please decrypt them for\Nme." So here the adversary submits
Dialogue: 0,0:10:41.61,0:10:46.45,Default,,0000,0000,0000,,ciphertext C1 and he gets the decryption\Nof ciphertext C1, namely M1. And he gets
Dialogue: 0,0:10:46.45,0:10:51.41,Default,,0000,0000,0000,,to do this again and again, so he submits\Nciphertext C2, and he gets the decryption,
Dialogue: 0,0:10:51.41,0:10:56.20,Default,,0000,0000,0000,,which is M2, ciphertext C3, and he gets\Nthe decryption M3, and so on and so forth.
Dialogue: 0,0:10:56.20,0:11:00.19,Default,,0000,0000,0000,,Finally, the adversary says, "This\Nsquaring phase is over," and now he
Dialogue: 0,0:11:00.19,0:11:04.48,Default,,0000,0000,0000,,submits basically two equal length\Nmessages, M0 and M1 as normal, and he
Dialogue: 0,0:11:04.48,0:11:08.82,Default,,0000,0000,0000,,receives in response the challenge\Nciphertext C, Which is the encryption of M
Dialogue: 0,0:11:08.82,0:11:13.05,Default,,0000,0000,0000,,zero or the encryption of M one. Depending\Non whether we're in experiment zero or
Dialogue: 0,0:11:13.05,0:11:17.00,Default,,0000,0000,0000,,experiment one. Now, the adversary can\Ncontinue to issue these ciphertext
Dialogue: 0,0:11:17.00,0:11:21.06,Default,,0000,0000,0000,,queries. So he can continue to issue,\Ndecryption requests. So he submits a
Dialogue: 0,0:11:21.06,0:11:25.45,Default,,0000,0000,0000,,ciphertext, and he gets a decryption of\Nthat ciphertext, but of course, now, there
Dialogue: 0,0:11:25.45,0:11:29.99,Default,,0000,0000,0000,,has to be a caveat. If the attacker could\Nsubmit arbitrary ciphertext of his choice,
Dialogue: 0,0:11:29.99,0:11:34.27,Default,,0000,0000,0000,,of course, he could break the challenge.\NWhat he would do is he would submit the
Dialogue: 0,0:11:34.27,0:11:38.51,Default,,0000,0000,0000,,challenge ciphertext C as a decryption\Nquery. And then he would be told whether
Dialogue: 0,0:11:38.51,0:11:42.66,Default,,0000,0000,0000,,in the challenge phase he was given the\Nencryption of M0 or the encryption of M1.
Dialogue: 0,0:11:42.66,0:11:46.82,Default,,0000,0000,0000,,As a result we put this limitation here,\Nthat says that he can in fact submit any
Dialogue: 0,0:11:46.82,0:11:51.03,Default,,0000,0000,0000,,ciphertext of his choice except. For the\Nchallenge ciphertext. So the attacker
Dialogue: 0,0:11:51.03,0:11:55.03,Default,,0000,0000,0000,,could ask for the decryption of any\Nciphertext of his choice other than the
Dialogue: 0,0:11:55.03,0:11:59.30,Default,,0000,0000,0000,,challenge ciphertext. And even though he\Nwas given all these decryptions, he still
Dialogue: 0,0:11:59.30,0:12:03.20,Default,,0000,0000,0000,,shouldn't be able to tell whether he was\Ngiven the encryption of M0 or the
Dialogue: 0,0:12:03.20,0:12:09.21,Default,,0000,0000,0000,,encryption of M1. So you notice this is a\Nvery conservative definition. It gives the
Dialogue: 0,0:12:09.21,0:12:14.11,Default,,0000,0000,0000,,attacker more power than what we saw in\Nthe previous slide. On the previous slide,
Dialogue: 0,0:12:14.11,0:12:18.71,Default,,0000,0000,0000,,the attacker could only decrypt messages\Nwhere the plain text began with the words
Dialogue: 0,0:12:18.71,0:12:23.61,Default,,0000,0000,0000,,"to: attacker". Here, we're saying the attacker\Ncan decrypt any ciphertext of his choice,
Dialogue: 0,0:12:23.61,0:12:29.72,Default,,0000,0000,0000,,as long as it's different from the\Nchallenge ciphertext C. Okay? And then his
Dialogue: 0,0:12:29.72,0:12:34.09,Default,,0000,0000,0000,,goal is to say whether the challenge\Nciphertext is the encryption of M0 or the
Dialogue: 0,0:12:34.09,0:12:37.92,Default,,0000,0000,0000,,encryption of M1. And as usual, if he\Ncan't do that, in other words, his
Dialogue: 0,0:12:37.92,0:12:42.35,Default,,0000,0000,0000,,behavior in experiment zero is basically\Nthe same as his behavior in experiment
Dialogue: 0,0:12:42.35,0:12:46.84,Default,,0000,0000,0000,,one, so he wasn't able to distinguish the\Nencryption of M0 from the encryption of
Dialogue: 0,0:12:46.84,0:12:51.22,Default,,0000,0000,0000,,M1, even though he had all this power Then\Nwe say that the system is chosen
Dialogue: 0,0:12:51.22,0:12:55.88,Default,,0000,0000,0000,,ciphertext secure, CCA secure. And\Nsometimes there is an acronym, the acronym
Dialogue: 0,0:12:55.88,0:13:00.60,Default,,0000,0000,0000,,for this is indistinguishability under a\Nchosen ciphertext attack, but I'm just
Dialogue: 0,0:13:00.60,0:13:05.74,Default,,0000,0000,0000,,gonna say CCA secured. So let's see how\Nthis captures, the email example we saw
Dialogue: 0,0:13:05.74,0:13:10.59,Default,,0000,0000,0000,,before. So suppose the encryption system\Nbeing used is such that just given the
Dialogue: 0,0:13:10.59,0:13:15.43,Default,,0000,0000,0000,,encryption of a message the attacker can\Nchange the intended recipient from to
Dialogue: 0,0:13:15.43,0:13:20.13,Default,,0000,0000,0000,,Alice say to, to Charlie. Then here's how\Nwe would win the CCA game. Well in the
Dialogue: 0,0:13:20.13,0:13:25.03,Default,,0000,0000,0000,,first step he's given the public key of\Ncourse. And then what the attacker will do
Dialogue: 0,0:13:25.03,0:13:29.58,Default,,0000,0000,0000,,is he would issue two equal length\Nmessages, namely in the first message, the
Dialogue: 0,0:13:29.58,0:13:33.94,Default,,0000,0000,0000,,body is zero. In the second message the\Nbody is one. But both messages are
Dialogue: 0,0:13:33.94,0:13:39.89,Default,,0000,0000,0000,,intended for Alice. And in response, he\Nwould be given the challenge ciphertext C.
Dialogue: 0,0:13:39.89,0:13:45.13,Default,,0000,0000,0000,,Okay, so now here we have our challenge\Nciphertext C. Now what the attacker is
Dialogue: 0,0:13:45.13,0:13:49.96,Default,,0000,0000,0000,,gonna do is he's gonna use his, his\Nability here to modify the intended
Dialogue: 0,0:13:49.96,0:13:55.27,Default,,0000,0000,0000,,recipient. And he's gonna send back a\Nciphertext C', where C' is the encryption
Dialogue: 0,0:13:55.27,0:14:01.76,Default,,0000,0000,0000,,of the message to Charlie with body being\Nthe challenge body b. So if you remember is
Dialogue: 0,0:14:01.76,0:14:07.82,Default,,0000,0000,0000,,either zero or one. Now, because the plain\Ntext is different, we know that the
Dialogue: 0,0:14:07.82,0:14:12.49,Default,,0000,0000,0000,,ciphertext must also be different. So in\Nparticular, C prime must be different from
Dialogue: 0,0:14:12.49,0:14:17.21,Default,,0000,0000,0000,,the challenge ciphertext C, yeah? So the\NC prime here must be different from C. And
Dialogue: 0,0:14:17.21,0:14:21.76,Default,,0000,0000,0000,,as a result, the poor challenger now has\Nto decrypt by definition of the CCA game.
Dialogue: 0,0:14:21.76,0:14:26.14,Default,,0000,0000,0000,,The challenger must decrypt any ciphertext\Nthat's not equal to a challenge
Dialogue: 0,0:14:26.14,0:14:30.65,Default,,0000,0000,0000,,ciphertext. So the challenger decrypts\Ngive the adversary M prime. Basically he
Dialogue: 0,0:14:30.65,0:14:35.26,Default,,0000,0000,0000,,gave the adversary B, and now the\Nadversary can output the challenge B and
Dialogue: 0,0:14:35.26,0:14:40.29,Default,,0000,0000,0000,,he wins the game with advantage one. So\Nhe's advantage with this particular scheme
Dialogue: 0,0:14:40.29,0:14:45.14,Default,,0000,0000,0000,,is one. So, simply because the attacker\Nwas able to change the challenge ciphertext
Dialogue: 0,0:14:45.15,0:14:49.100,Default,,0000,0000,0000,,from one recipient to another that\Nallows him to, to win the CCA game with
Dialogue: 0,0:14:49.100,0:14:55.00,Default,,0000,0000,0000,,advantage one. So as I said, chosen\Nciphertext security turns out actually is
Dialogue: 0,0:14:55.00,0:14:59.33,Default,,0000,0000,0000,,the correct notion of security for public\Nkey encryption systems. And it's a very,
Dialogue: 0,0:14:59.33,0:15:03.65,Default,,0000,0000,0000,,very interesting concept, right? Basically, somehow\Neven though the attacker has this ability
Dialogue: 0,0:15:03.65,0:15:07.84,Default,,0000,0000,0000,,to decrypt anything he wants. Other than\Nthe challenge ciphertext, still he can't
Dialogue: 0,0:15:07.84,0:15:12.03,Default,,0000,0000,0000,,learn what the challenge ciphertext is.\NAnd so the goal for the remainder of this module
Dialogue: 0,0:15:12.03,0:15:16.28,Default,,0000,0000,0000,,and actually the next module as well, is\Nto construct CCA secure systems. It's
Dialogue: 0,0:15:16.28,0:15:20.09,Default,,0000,0000,0000,,actually quite remarkable that this is\Nachievable and I'm going to show you
Dialogue: 0,0:15:20.09,0:15:24.31,Default,,0000,0000,0000,,exactly how to do it. And in fact those\NCCA secure systems that we build are the
Dialogue: 0,0:15:24.31,0:15:28.58,Default,,0000,0000,0000,,ones that are used in the real world. And\Nevery time a system has tried to deploy
Dialogue: 0,0:15:28.74,0:15:33.01,Default,,0000,0000,0000,,a public key encryption mechanism that's not\NCCA secure someone has come up with an
Dialogue: 0,0:15:33.01,0:15:37.49,Default,,0000,0000,0000,,attack and was able to break it. And we're\Ngoing to see some of these example attacks
Dialogue: 0,0:15:37.49,0:15:39.28,Default,,0000,0000,0000,,actually in the next few segments.