[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:02.95,Default,,0000,0000,0000,,Before we start with the technical\Nmaterial, I wanna give you a quick
Dialogue: 0,0:00:02.95,0:00:06.49,Default,,0000,0000,0000,,overview of what cryptography is about and\Nthe different areas of cryptography. So
Dialogue: 0,0:00:06.49,0:00:10.49,Default,,0000,0000,0000,,the core of cryptography of course is\Nsecure communication that essentially
Dialogue: 0,0:00:10.49,0:00:14.54,Default,,0000,0000,0000,,consists of two parts. The first is\Nsecured key establishment and then how do
Dialogue: 0,0:00:14.54,0:00:18.70,Default,,0000,0000,0000,,we communicate securely once we have a\Nshared key. We already said that secured
Dialogue: 0,0:00:18.70,0:00:22.85,Default,,0000,0000,0000,,key establishment essentially amounts to\NAlice and Bob sending messages to one
Dialogue: 0,0:00:22.85,0:00:26.91,Default,,0000,0000,0000,,another such that at the end of this\Nprotocol, there's a shared key that they
Dialogue: 0,0:00:26.91,0:00:30.91,Default,,0000,0000,0000,,both agree on, shared key K, and beyond\Nthat, beyond just a shared key, in fact
Dialogue: 0,0:00:30.91,0:00:35.27,Default,,0000,0000,0000,,Alice would know that she's talking to Bob\Nand Bob would know that he's talking to
Dialogue: 0,0:00:35.27,0:00:39.96,Default,,0000,0000,0000,,Alice. But a poor attacker who listens in\Non this conversation has no idea what the
Dialogue: 0,0:00:39.96,0:00:44.01,Default,,0000,0000,0000,,shared key is. And we'll see how to do\Nthat later on in the course. Now once they
Dialogue: 0,0:00:44.01,0:00:47.66,Default,,0000,0000,0000,,have a shared key, they want exchange\Nmessages securely using this key, and
Dialogue: 0,0:00:47.66,0:00:51.70,Default,,0000,0000,0000,,we'll talk about encryption schemes that\Nallow them to do that in such a way that
Dialogue: 0,0:00:51.70,0:00:55.49,Default,,0000,0000,0000,,an attacker can't figure out what messages\Nare being sent back and forth. And
Dialogue: 0,0:00:55.49,0:00:59.63,Default,,0000,0000,0000,,furthermore an attacker cannot even tamper\Nwith this traffic without being detected.
Dialogue: 0,0:00:59.63,0:01:03.23,Default,,0000,0000,0000,,In other words, these encryption schemes\Nprovide both confidentiality and
Dialogue: 0,0:01:03.23,0:01:06.77,Default,,0000,0000,0000,,integrity. But cryptography does much,\Nmuch, much more than just these two
Dialogue: 0,0:01:06.77,0:01:10.52,Default,,0000,0000,0000,,things. And I want to give you a few\Nexamples of that. So the first example I
Dialogue: 0,0:01:10.52,0:01:14.47,Default,,0000,0000,0000,,want to give you is what's called a\Ndigital signature. So a digital signature,
Dialogue: 0,0:01:14.47,0:01:18.89,Default,,0000,0000,0000,,basically, is the analog of the signature\Nin the physical world. In the physical
Dialogue: 0,0:01:18.89,0:01:23.37,Default,,0000,0000,0000,,world, remember when you sign a document,\Nessentially, you write your signature on
Dialogue: 0,0:01:23.37,0:01:27.74,Default,,0000,0000,0000,,that document and your signature is always\Nthe same. You always write the same
Dialogue: 0,0:01:27.74,0:01:32.16,Default,,0000,0000,0000,,signature on all documents that you wanna\Nsign. In the digital world, this can't
Dialogue: 0,0:01:32.16,0:01:36.81,Default,,0000,0000,0000,,possibly work because if the attacker just\Nobtained one signed document from me, he
Dialogue: 0,0:01:36.81,0:01:41.18,Default,,0000,0000,0000,,can cut and paste my signature unto some\Nother document that I might not have
Dialogue: 0,0:01:41.18,0:01:45.25,Default,,0000,0000,0000,,wanted to sign. And so, it's simply not\Npossible in a digital world that my
Dialogue: 0,0:01:45.25,0:01:49.59,Default,,0000,0000,0000,,signature is the same for all documents\Nthat I want to sign. So we're gonna talk
Dialogue: 0,0:01:49.59,0:01:53.83,Default,,0000,0000,0000,,about how to construct digital signatures\Nin the second half of the course. It's
Dialogue: 0,0:01:53.83,0:01:58.12,Default,,0000,0000,0000,,really quite an interesting primitive and\Nwe'll see exactly how to do it. Just to
Dialogue: 0,0:01:58.12,0:02:02.10,Default,,0000,0000,0000,,give you a hint, the way digital\Nsignatures work is basically by making the
Dialogue: 0,0:02:02.10,0:02:06.23,Default,,0000,0000,0000,,digital signature via function of the\Ncontent being signed. So an attacker who
Dialogue: 0,0:02:06.23,0:02:10.31,Default,,0000,0000,0000,,tries to copy my signature from one\Ndocument to another is not gonna succeed
Dialogue: 0,0:02:10.31,0:02:14.54,Default,,0000,0000,0000,,because the signature. On the new document\Nis not gonna be the proper function of the
Dialogue: 0,0:02:14.54,0:02:18.53,Default,,0000,0000,0000,,data in the new document, and as a result,\Nthe signature won't verify. And as I said,
Dialogue: 0,0:02:18.53,0:02:22.61,Default,,0000,0000,0000,,we're gonna see exactly how to construct\Ndigital signatures later on and then we'll
Dialogue: 0,0:02:22.61,0:02:27.19,Default,,0000,0000,0000,,prove that those constructions are secure.\NAnother application of cryptography that I
Dialogue: 0,0:02:27.19,0:02:31.10,Default,,0000,0000,0000,,wanted to mention, is anonymous\Ncommunication. So, here, imagine user
Dialogue: 0,0:02:31.10,0:02:35.83,Default,,0000,0000,0000,,Alice wants to talk to some chat server,\NBob. And, perhaps she wants to talk about
Dialogue: 0,0:02:35.83,0:02:40.38,Default,,0000,0000,0000,,a medical condition, and so she wants to\Ndo that anonymously, so that the chat
Dialogue: 0,0:02:40.38,0:02:45.11,Default,,0000,0000,0000,,server doesn't actually know who she is.\NWell, there's a standard method, called a
Dialogue: 0,0:02:45.11,0:02:49.95,Default,,0000,0000,0000,,mixnet, that allows Alice to communicate\Nover the public internet with Bob through
Dialogue: 0,0:02:49.95,0:02:54.86,Default,,0000,0000,0000,,a sequence of proxies such that at the end\Nof the communication Bob has no idea who he
Dialogue: 0,0:02:54.86,0:02:59.54,Default,,0000,0000,0000,,just talked to. The way mixnets work\Nis basically as Alice sends her messages
Dialogue: 0,0:02:59.54,0:03:03.82,Default,,0000,0000,0000,,to Bob through a sequence of proxies,\Nthese messages get encrypted and
Dialogue: 0,0:03:03.82,0:03:08.27,Default,,0000,0000,0000,,decrypted appropriately so that Bob has no\Nidea who he talked to and the proxies
Dialogue: 0,0:03:08.27,0:03:12.72,Default,,0000,0000,0000,,themselves don't even know that Alice is\Ntalking to Bob, or that actually who is
Dialogue: 0,0:03:12.72,0:03:16.75,Default,,0000,0000,0000,,talking to whom more generally. One\Ninteresting thing about this anonymous
Dialogue: 0,0:03:16.75,0:03:20.50,Default,,0000,0000,0000,,communication channel is, this is\Nbi-directional. In other words, even
Dialogue: 0,0:03:20.50,0:03:24.74,Default,,0000,0000,0000,,though Bob has no idea who he's talking\Nto, he can still respond to Alice and
Dialogue: 0,0:03:24.74,0:03:29.15,Default,,0000,0000,0000,,Alice will get those messages. Once we\Nhave anonymous communication, we can build
Dialogue: 0,0:03:29.15,0:03:33.78,Default,,0000,0000,0000,,other privacy mechanisms. And I wanna give\Nyou one example which is called anonymous
Dialogue: 0,0:03:33.78,0:03:37.64,Default,,0000,0000,0000,,digital cash. Remember that in the\Nphysical world if I have a physical
Dialogue: 0,0:03:37.64,0:03:42.11,Default,,0000,0000,0000,,dollar, I can walk into a bookstore and\Nbuy a book and the merchant would have no
Dialogue: 0,0:03:42.11,0:03:46.88,Default,,0000,0000,0000,,idea who I am. The question is whether we\Ncan do the exact same thing in the digital
Dialogue: 0,0:03:46.88,0:03:50.96,Default,,0000,0000,0000,,world. In the digital world, basically,\NAlice might have a digital dollar,
Dialogue: 0,0:03:50.96,0:03:55.98,Default,,0000,0000,0000,,a digital dollar coin. And she might wanna\Nspend that digital dollar at some online
Dialogue: 0,0:03:55.98,0:04:00.76,Default,,0000,0000,0000,,merchants, perhaps some online bookstore.\NNow, what we'd like to do is make it so
Dialogue: 0,0:04:00.76,0:04:05.54,Default,,0000,0000,0000,,that when Alice spends her coin at the\Nbookstore, the bookstore would have no
Dialogue: 0,0:04:05.54,0:04:10.63,Default,,0000,0000,0000,,idea who Alice is. So we provide the same\Nanonymity that we get from physical cash.
Dialogue: 0,0:04:10.63,0:04:15.47,Default,,0000,0000,0000,,Now the problem is that in the digital\Nworld, Alice can take the coin that she
Dialogue: 0,0:04:15.47,0:04:20.25,Default,,0000,0000,0000,,had, this one dollar coin, and before she spent\Nit, she can actually make copies of it.
Dialogue: 0,0:04:20.25,0:04:24.09,Default,,0000,0000,0000,,And then all of a sudden instead of just\Nhaving just one dollar coin now all
Dialogue: 0,0:04:24.09,0:04:27.94,Default,,0000,0000,0000,,of a sudden she has three dollar coins and\Nthey're all the same of course, and
Dialogue: 0,0:04:27.94,0:04:31.83,Default,,0000,0000,0000,,there's nothing preventing her from taking\Nthose replicas of a dollar coin and
Dialogue: 0,0:04:31.83,0:04:35.82,Default,,0000,0000,0000,,spending it at other merchants. And so the\Nquestion is how do we provide anonymous
Dialogue: 0,0:04:35.82,0:04:39.85,Default,,0000,0000,0000,,digital cash? But at the same time, also\Nprevent Alice from double spending the
Dialogue: 0,0:04:39.85,0:04:43.76,Default,,0000,0000,0000,,dollar coin at different merchants. In\Nsome sense there's a paradox here where
Dialogue: 0,0:04:43.76,0:04:47.88,Default,,0000,0000,0000,,anonymity is in conflict with security\Nbecause if we have anonymous cash there's
Dialogue: 0,0:04:47.88,0:04:51.100,Default,,0000,0000,0000,,nothing to prevent Alice from double\Nspending the coin and because the coin is
Dialogue: 0,0:04:51.100,0:04:56.24,Default,,0000,0000,0000,,anonymous we have no way of telling who\Ncommitted this fraud. And so the question
Dialogue: 0,0:04:56.24,0:05:00.39,Default,,0000,0000,0000,,is how do we resolve this tension. And it\Nturns out, it's completely doable. And
Dialogue: 0,0:05:00.39,0:05:04.76,Default,,0000,0000,0000,,we'll talk about anonymous digital cash\Nlater on. Just to give you a hint, I'll
Dialogue: 0,0:05:04.76,0:05:09.17,Default,,0000,0000,0000,,say that the way we do it is basically by\Nmaking sure that if Alice spends the coin
Dialogue: 0,0:05:09.17,0:05:13.76,Default,,0000,0000,0000,,once then no one knows who she is, but if\Nshe spends the coin more than once, all of
Dialogue: 0,0:05:13.76,0:05:17.88,Default,,0000,0000,0000,,a sudden, her identity is completely\Nexposed and then she could be subject to
Dialogue: 0,0:05:17.88,0:05:22.10,Default,,0000,0000,0000,,all sorts of legal problems. And so that's\Nhow anonymous digital cash would
Dialogue: 0,0:05:22.10,0:05:26.16,Default,,0000,0000,0000,,work at a high level and we'll see how to\Nimplement it later on in the course.
Dialogue: 0,0:05:26.16,0:05:30.22,Default,,0000,0000,0000,,Another application of cryptography has to\Ndo with more abstract protocols, but
Dialogue: 0,0:05:30.22,0:05:34.33,Default,,0000,0000,0000,,before I speak the general result, I\Nwant to give you two examples. So the
Dialogue: 0,0:05:34.33,0:05:38.34,Default,,0000,0000,0000,,first example has to do with election\Nsystems. So here's the election problem.
Dialogue: 0,0:05:38.34,0:05:42.66,Default,,0000,0000,0000,,Suppose ... we have two parties, party zero\Nand party one. And voters vote for these
Dialogue: 0,0:05:42.66,0:05:47.10,Default,,0000,0000,0000,,parties. So for example, this voter could\Nhave voted for party zero, this voter voted for
Dialogue: 0,0:05:47.10,0:05:52.31,Default,,0000,0000,0000,,party one. And so on. So in this election,\Nparty zero got three votes and party two
Dialogue: 0,0:05:52.31,0:05:56.59,Default,,0000,0000,0000,,got two votes. So the winner of the\Nelection, of course, is party zero. But
Dialogue: 0,0:05:56.59,0:06:01.58,Default,,0000,0000,0000,,more generally, the winner of the election\Nis the party who receives the majority of
Dialogue: 0,0:06:01.58,0:06:06.45,Default,,0000,0000,0000,,the votes. Now, the voting problem is the\Nfollowing. The voters would somehow like
Dialogue: 0,0:06:06.45,0:06:11.72,Default,,0000,0000,0000,,to compute the majority of the votes, but\Ndo it in such a way such that nothing else
Dialogue: 0,0:06:11.72,0:06:16.80,Default,,0000,0000,0000,,is revealed about their individual votes.\NOkay? So the question is how to do that?
Dialogue: 0,0:06:16.80,0:06:21.49,Default,,0000,0000,0000,,And to do so, we're gonna introduce an\Nelection center who's gonna help us
Dialogue: 0,0:06:21.49,0:06:26.63,Default,,0000,0000,0000,,compute the majority, but keep the votes\Notherwise secret. And what the parties
Dialogue: 0,0:06:26.63,0:06:32.03,Default,,0000,0000,0000,,will do is they will each send the funny\Nencryption of their votes to the election
Dialogue: 0,0:06:32.03,0:06:36.95,Default,,0000,0000,0000,,center in such a way that at the end of\Nthe election, the election center is able
Dialogue: 0,0:06:36.95,0:06:41.62,Default,,0000,0000,0000,,to compute and output the winner of the\Nelection. However, other than the winner
Dialogue: 0,0:06:41.62,0:06:46.58,Default,,0000,0000,0000,,of the election, nothing else is revealed\Nabout the individual votes. The individual
Dialogue: 0,0:06:46.58,0:06:51.37,Default,,0000,0000,0000,,votes otherwise remain completely private.\NOf course the election center is also
Dialogue: 0,0:06:51.37,0:06:56.33,Default,,0000,0000,0000,,gonna verify that this voter for example\Nis allowed to vote and that the voter has
Dialogue: 0,0:06:56.33,0:07:00.82,Default,,0000,0000,0000,,only voted once. But other than that\Ninformation the election center and the
Dialogue: 0,0:07:00.82,0:07:05.48,Default,,0000,0000,0000,,rest of the world learned nothing else\Nabout that voter's vote other than the
Dialogue: 0,0:07:05.48,0:07:10.10,Default,,0000,0000,0000,,result of the election. So this is an\Nexample of a protocol that involves six
Dialogue: 0,0:07:10.10,0:07:14.43,Default,,0000,0000,0000,,parties. In this case, there are five\Nvoters in one election center. These
Dialogue: 0,0:07:14.43,0:07:19.42,Default,,0000,0000,0000,,parties compute amongst themselves. And at\Nthe end of the computation, the result of
Dialogue: 0,0:07:19.42,0:07:24.40,Default,,0000,0000,0000,,the election is known but nothing else is\Nrevealed about the individual inputs. Now
Dialogue: 0,0:07:24.40,0:07:29.16,Default,,0000,0000,0000,,a similar problem comes up in the context\Nof private auctions. So in a private
Dialogue: 0,0:07:29.16,0:07:34.16,Default,,0000,0000,0000,,auction every bidder has his own bid that\Nhe wants to bid. And now suppose the
Dialogue: 0,0:07:34.16,0:07:39.36,Default,,0000,0000,0000,,auction mechanism that's being used is\Nwhat's called a Vickrey auction where the
Dialogue: 0,0:07:39.36,0:07:45.29,Default,,0000,0000,0000,,definition of a Vickrey auction is that\Nthe winner is the highest bidder. But the
Dialogue: 0,0:07:45.29,0:07:50.10,Default,,0000,0000,0000,,amounts that the winner pays is actually\Nthe second highest bid. So he pays the
Dialogue: 0,0:07:50.10,0:07:54.85,Default,,0000,0000,0000,,second highest bid. Okay, so this is a\Nstandard auction mechanism called the
Dialogue: 0,0:07:54.85,0:08:00.03,Default,,0000,0000,0000,,Vickrey auction. And now what we'd like to\Ndo is basically enable the participants to
Dialogue: 0,0:08:00.03,0:08:04.78,Default,,0000,0000,0000,,compute, to figure out who the highest\Nbidder is and how much he's supposed to
Dialogue: 0,0:08:04.78,0:08:09.16,Default,,0000,0000,0000,,pay, but other than that, all other\Ninformation about the individual bids
Dialogue: 0,0:08:09.16,0:08:14.16,Default,,0000,0000,0000,,should remain secret. So for example, the\Nactual amount that the highest bidder bid
Dialogue: 0,0:08:14.16,0:08:19.22,Default,,0000,0000,0000,,should remain secret. The only thing that\Nshould become public is the second highest
Dialogue: 0,0:08:19.22,0:08:23.53,Default,,0000,0000,0000,,bid and the identity of the highest\Nbidder. So again now, the way we will do
Dialogue: 0,0:08:23.53,0:08:28.17,Default,,0000,0000,0000,,that is we'll introduce an auction center, and\Nin a similar way, essentially, everybody
Dialogue: 0,0:08:28.17,0:08:32.59,Default,,0000,0000,0000,,will send their encrypted bids to the\Nauction center. The auction center will
Dialogue: 0,0:08:32.59,0:08:37.12,Default,,0000,0000,0000,,compute the identity of the winner and in\Nfact he will also compute the second
Dialogue: 0,0:08:37.12,0:08:41.82,Default,,0000,0000,0000,,highest bid but other than these two\Nvalues, nothing else is revealed about the
Dialogue: 0,0:08:41.82,0:08:46.13,Default,,0000,0000,0000,,individual bids. Now, this is actually an\Nexample of a much more general problem
Dialogue: 0,0:08:46.13,0:08:50.26,Default,,0000,0000,0000,,called secure multi-party computation. Let\Nme explain what secure multi-party
Dialogue: 0,0:08:50.26,0:08:54.62,Default,,0000,0000,0000,,computation is about. So here, basically\Nabstractly, the participants have a secret
Dialogue: 0,0:08:54.62,0:08:58.65,Default,,0000,0000,0000,,inputs to themselves. So, in the case of\Nan election, the inputs would be the
Dialogue: 0,0:08:58.65,0:09:02.79,Default,,0000,0000,0000,,votes. In the case of an auction, the\Ninputs would be the secret bids. And then
Dialogue: 0,0:09:02.79,0:09:06.96,Default,,0000,0000,0000,,what they would like to do is compute some\Nsort of a function of their inputs.
Dialogue: 0,0:09:06.96,0:09:10.84,Default,,0000,0000,0000,,Again, in the case of an election, the\Nfunction's a majority. In the case of
Dialogue: 0,0:09:10.84,0:09:15.09,Default,,0000,0000,0000,,auction, the function happens to be the\Nsecond highest, largest number among x one
Dialogue: 0,0:09:15.09,0:09:19.18,Default,,0000,0000,0000,,to x four. And the question is, how can\Nthey do that, such that the value of the
Dialogue: 0,0:09:19.18,0:09:23.38,Default,,0000,0000,0000,,function is revealed, but nothing else is\Nrevealed about the individual votes? So
Dialogue: 0,0:09:23.38,0:09:27.68,Default,,0000,0000,0000,,let me show you kind of a dumb, insecure\Nway of doing it. What we do is introduce a
Dialogue: 0,0:09:27.68,0:09:31.77,Default,,0000,0000,0000,,trusted party. And then, this trusted\Nauthority basically collects individual
Dialogue: 0,0:09:31.77,0:09:36.22,Default,,0000,0000,0000,,inputs. And it kinda promises to keep the\Nindividual inputs secret, so that only it
Dialogue: 0,0:09:36.22,0:09:40.51,Default,,0000,0000,0000,,would know what they are. And then, it\Npublishes the value of the function, to
Dialogue: 0,0:09:40.51,0:09:44.74,Default,,0000,0000,0000,,the world. So, the idea is now that the\Nvalue of the function became public, but
Dialogue: 0,0:09:44.74,0:09:48.81,Default,,0000,0000,0000,,nothing else is revealed about the\Nindividual inputs. But, of course, you got
Dialogue: 0,0:09:48.81,0:09:52.99,Default,,0000,0000,0000,,this trusted authority that you got to\Ntrust, and if for some reason it's not
Dialogue: 0,0:09:52.99,0:09:57.17,Default,,0000,0000,0000,,trustworthy, then you have a problem. And\Nso, there's a very central theorem in
Dialogue: 0,0:09:57.17,0:10:01.00,Default,,0000,0000,0000,,crypto and it really is quite a\Nsurprising fact. That says that any
Dialogue: 0,0:10:01.00,0:10:05.20,Default,,0000,0000,0000,,computation you'd like to do, any function\NF you'd like to compute, that you can
Dialogue: 0,0:10:05.20,0:10:09.30,Default,,0000,0000,0000,,compute with a trusted authority, you can\Nalso do without a trusted authority.
Dialogue: 0,0:10:09.30,0:10:13.56,Default,,0000,0000,0000,,Let me at a high level explain what this\Nmeans. Basically, what we're gonna do, is
Dialogue: 0,0:10:13.56,0:10:17.82,Default,,0000,0000,0000,,we're gonna get rid of the authority. So\Nthe parties are actually not gonna send
Dialogue: 0,0:10:17.82,0:10:21.81,Default,,0000,0000,0000,,their inputs to the authority. And, in\Nfact, there's no longer going to be an
Dialogue: 0,0:10:21.81,0:10:26.01,Default,,0000,0000,0000,,authority in the system. Instead, what the\Nparties are gonna do, is they're gonna
Dialogue: 0,0:10:26.01,0:10:30.57,Default,,0000,0000,0000,,talk to one another using some protocol.\NSuch that at the end of the protocol all
Dialogue: 0,0:10:30.57,0:10:34.89,Default,,0000,0000,0000,,of a sudden the value of the function\Nbecomes known to everybody. And yet
Dialogue: 0,0:10:34.89,0:10:39.39,Default,,0000,0000,0000,,nothing other than the value of the\Nfunction is revealed. In other words, the
Dialogue: 0,0:10:39.39,0:10:43.64,Default,,0000,0000,0000,,individual inputs is still kept secret.\NBut again there's no authority, there's
Dialogue: 0,0:10:43.64,0:10:47.87,Default,,0000,0000,0000,,just a way for them to talk to one another\Nsuch that the final output is revealed. So
Dialogue: 0,0:10:47.87,0:10:51.85,Default,,0000,0000,0000,,this is a fairly general result, it's kind\Nof a surprising fact that is at all
Dialogue: 0,0:10:51.85,0:10:56.02,Default,,0000,0000,0000,,doable. And in fact it is and towards the\Nend of the class we'll actually see how to
Dialogue: 0,0:10:56.02,0:11:00.58,Default,,0000,0000,0000,,make this happen. Now, there are some\Napplications of cryptography that I can't
Dialogue: 0,0:11:00.58,0:11:05.56,Default,,0000,0000,0000,,classify any other way other than to say\Nthat they are purely magical. Let me give
Dialogue: 0,0:11:05.56,0:11:10.24,Default,,0000,0000,0000,,you two examples of that. So the first is\Nwhat's called privately outsourcing
Dialogue: 0,0:11:10.24,0:11:15.22,Default,,0000,0000,0000,,computation. So I'll give you an example\Nof a Google search just to illustrate the
Dialogue: 0,0:11:15.22,0:11:20.33,Default,,0000,0000,0000,,point. So imagine Alice has a search query\Nthat she wants to issue. It turns out that
Dialogue: 0,0:11:20.33,0:11:25.43,Default,,0000,0000,0000,,there are very special encryption schemes\Nsuch that Alice can send an encryption of
Dialogue: 0,0:11:25.43,0:11:30.37,Default,,0000,0000,0000,,her query to Google. And then because of\Nthe property of the encryption scheme
Dialogue: 0,0:11:30.37,0:11:35.30,Default,,0000,0000,0000,,Google can actually compute on the\Nencrypted values without knowing what the
Dialogue: 0,0:11:35.30,0:11:40.37,Default,,0000,0000,0000,,plain texts are. So Google can actually\Nrun its massive search algorithm on the
Dialogue: 0,0:11:40.37,0:11:44.90,Default,,0000,0000,0000,,encrypted query and recover in encrypted\Nresults. Okay. Google will send the
Dialogue: 0,0:11:44.90,0:11:49.24,Default,,0000,0000,0000,,encrypted results back to Alice. Alice\Nwill decrypt and then she will receive the
Dialogue: 0,0:11:49.24,0:11:53.69,Default,,0000,0000,0000,,results. But the magic here is all Google\Nsaw was just encryptions of her queries
Dialogue: 0,0:11:53.69,0:11:57.49,Default,,0000,0000,0000,,and nothing else. And so, Google as a\Nresult has no idea what Alice just
Dialogue: 0,0:11:57.49,0:12:01.67,Default,,0000,0000,0000,,searched for and nevertheless Alice\Nactually learned exactly what she
Dialogue: 0,0:12:01.67,0:12:05.81,Default,,0000,0000,0000,,wanted to learn. Okay so, these are\Nmagical kind of encryption schemes. They're
Dialogue: 0,0:12:05.81,0:12:09.98,Default,,0000,0000,0000,,fairly recent, this is only a new\Ndevelopment from about two or three years
Dialogue: 0,0:12:09.98,0:12:14.44,Default,,0000,0000,0000,,ago, that allows us to compute on encrypted\Ndata, even though we don't really know
Dialogue: 0,0:12:14.44,0:12:18.67,Default,,0000,0000,0000,,what's inside the encryption. Now, before\Nyou rush off and think about implementing
Dialogue: 0,0:12:18.67,0:12:22.47,Default,,0000,0000,0000,,this, I should warn you that this is\Nreally at this point just theoretical, in
Dialogue: 0,0:12:22.47,0:12:26.42,Default,,0000,0000,0000,,the sense that running a Google search on\Nencryption data probably would take a
Dialogue: 0,0:12:26.42,0:12:30.52,Default,,0000,0000,0000,,billion years. But nevertheless, just the\Nfact that this is doable is already really
Dialogue: 0,0:12:30.52,0:12:34.47,Default,,0000,0000,0000,,surprising, and is already quite useful\Nfor relatively simple computations. So in
Dialogue: 0,0:12:34.47,0:12:38.67,Default,,0000,0000,0000,,fact, we'll see some applications of this\Nlater on. The other magical application I
Dialogue: 0,0:12:38.67,0:12:42.47,Default,,0000,0000,0000,,want to show you is what's called zero\Nknowledge. And in particular, I'll tell
Dialogue: 0,0:12:42.47,0:12:46.08,Default,,0000,0000,0000,,you about something called the zero\Nknowledge proof of knowledge. So here ...
Dialogue: 0,0:12:46.08,0:12:50.18,Default,,0000,0000,0000,,what happens is there's a certain\Nnumber N, which Alice knows. And the way
Dialogue: 0,0:12:50.18,0:12:54.17,Default,,0000,0000,0000,,the number N was constructed is as a\Nproduct of two large primes. So, imagine
Dialogue: 0,0:12:54.17,0:12:58.84,Default,,0000,0000,0000,,here we have two primes, P and Q. Each one\Nyou can think of it as like 1000 digits.
Dialogue: 0,0:12:58.84,0:13:03.89,Default,,0000,0000,0000,,And you probably know that multiplying\Ntwo 1000-digit numbers is fairly easy. But if
Dialogue: 0,0:13:03.89,0:13:08.24,Default,,0000,0000,0000,,I just give you their product, figuring\Nout their factorization into primes is
Dialogue: 0,0:13:08.24,0:13:12.43,Default,,0000,0000,0000,,actually quite difficult. And, in fact,\Nwe're gonna use the fact that factoring is
Dialogue: 0,0:13:12.43,0:13:16.57,Default,,0000,0000,0000,,difficult to build public key cryptosystems\Nin the second half of the course.
Dialogue: 0,0:13:16.57,0:13:20.97,Default,,0000,0000,0000,,Okay, so Alice happens to have this number\NN, and she also knows the factorization of
Dialogue: 0,0:13:20.97,0:13:24.90,Default,,0000,0000,0000,,N. Now Bob just has the number N. He\Ndoesn't actually know the factorization.
Dialogue: 0,0:13:24.90,0:13:28.72,Default,,0000,0000,0000,,Now, the magical fact about the zero\Nknowledge proof of knowledge, is that
Dialogue: 0,0:13:28.72,0:13:33.14,Default,,0000,0000,0000,,Alice can prove to Bob that she knows the\Nfactorization of N. Yes, you can actually
Dialogue: 0,0:13:33.14,0:13:37.46,Default,,0000,0000,0000,,give this proof to Bob, that Bob can\Ncheck, and become convinced that Alice
Dialogue: 0,0:13:37.46,0:13:42.39,Default,,0000,0000,0000,,knows the factorization of N, however Bob\Nlearns nothing at all. About the factors P
Dialogue: 0,0:13:42.39,0:13:47.03,Default,,0000,0000,0000,,and Q, and this is provable. Bob\Nabsolutely learns nothing at all about the
Dialogue: 0,0:13:47.03,0:13:50.100,Default,,0000,0000,0000,,factors P and Q. And the statement\Nactually is very, very general. This is
Dialogue: 0,0:13:50.100,0:13:55.28,Default,,0000,0000,0000,,not just about proving the factorization\Nof N. In fact, almost any puzzle that you
Dialogue: 0,0:13:55.28,0:13:59.61,Default,,0000,0000,0000,,want to prove that you know an answer to,\Nyou can prove it is your knowledge. So if
Dialogue: 0,0:13:59.61,0:14:03.83,Default,,0000,0000,0000,,you have a crossword puzzle that you've\Nsolved. Well, maybe crosswords is not the
Dialogue: 0,0:14:03.83,0:14:07.84,Default,,0000,0000,0000,,best example. But if you have like a\NSudoku puzzle, for example, that you want
Dialogue: 0,0:14:07.84,0:14:12.28,Default,,0000,0000,0000,,to prove that you've solved, you can prove\Nit to Bob in a way that Bob would learn
Dialogue: 0,0:14:12.28,0:14:16.72,Default,,0000,0000,0000,,nothing at all about the solution, and yet\NBob would be convinced that you really do
Dialogue: 0,0:14:16.72,0:14:20.93,Default,,0000,0000,0000,,have a solution to this puzzle. Okay. So\Nthose are kind of magical applications.
Dialogue: 0,0:14:20.93,0:14:25.00,Default,,0000,0000,0000,,And so the last thing I want to say is\Nthat modern cryptography is a very
Dialogue: 0,0:14:25.00,0:14:29.02,Default,,0000,0000,0000,,rigorous science. And in fact, every\Nconcept we're gonna describe is gonna
Dialogue: 0,0:14:29.02,0:14:33.13,Default,,0000,0000,0000,,follow three very rigorous steps, okay,\Nand we're gonna see these three steps
Dialogue: 0,0:14:33.13,0:14:37.34,Default,,0000,0000,0000,,again and again and again so I wanna\Nexplain what they are. So the first thing
Dialogue: 0,0:14:37.34,0:14:41.49,Default,,0000,0000,0000,,we're gonna do when we introduce a new\Nprimitive like a digital signature is
Dialogue: 0,0:14:41.49,0:14:45.54,Default,,0000,0000,0000,,we're gonna specify precisely what the\Nthreat model is. That is, what can an
Dialogue: 0,0:14:45.54,0:14:49.53,Default,,0000,0000,0000,,attacker do to attack a digital signature\Nand what is his goal in forging
Dialogue: 0,0:14:49.53,0:14:53.85,Default,,0000,0000,0000,,signatures? Okay, so we're gonna define\Nexactly what does it mean for a signature
Dialogue: 0,0:14:53.85,0:14:57.76,Default,,0000,0000,0000,,for example to be unforgeable.\NUnforgeable. Okay and I'm giving digital
Dialogue: 0,0:14:57.76,0:15:01.100,Default,,0000,0000,0000,,signatures just as an example. For every\Nprimitive we describe we're gonna
Dialogue: 0,0:15:01.100,0:15:06.46,Default,,0000,0000,0000,,precisely define what the threat model is.\NThen we're gonna propose a construction
Dialogue: 0,0:15:06.46,0:15:10.93,Default,,0000,0000,0000,,and then we're gonna give a proof that any\Nattacker that's able to attack the
Dialogue: 0,0:15:10.93,0:15:15.96,Default,,0000,0000,0000,,construction under this threat model. That\Nattacker can also be used to solve some
Dialogue: 0,0:15:15.96,0:15:20.15,Default,,0000,0000,0000,,underlying hard problem. And as a result,\Nif the problem really is hard, that
Dialogue: 0,0:15:20.15,0:15:24.35,Default,,0000,0000,0000,,actually proves that no attacker can break\Nthe construction under the threat model.
Dialogue: 0,0:15:24.35,0:15:27.84,Default,,0000,0000,0000,,Okay. But these three steps are actually\Nquite important. In the case of
Dialogue: 0,0:15:27.84,0:15:31.93,Default,,0000,0000,0000,,signatures, we'll define what it means for\Na signature to be, forgeable, then we'll
Dialogue: 0,0:15:31.93,0:15:35.91,Default,,0000,0000,0000,,give a construction, and then for example\Nwe'll say that anyone who can break our
Dialogue: 0,0:15:35.91,0:15:39.80,Default,,0000,0000,0000,,construction can then be used to say\Nfactor integers, which is believed to be a
Dialogue: 0,0:15:39.80,0:15:43.54,Default,,0000,0000,0000,,hard problem. Okay, so we're going to\Nfollow these three steps throughout, and
Dialogue: 0,0:15:43.54,0:15:47.33,Default,,0000,0000,0000,,then you'll see how this actually comes\Nabout. Okay, so this is the end of the
Dialogue: 0,0:15:47.33,0:15:51.22,Default,,0000,0000,0000,,segment. And then in the next segment\Nwe'll talk a little bit about the history
Dialogue: 0,0:15:51.22,0:15:52.01,Default,,0000,0000,0000,,of cryptography.