0:00

Before we start with the technical material, I wanna give you a quick

overview of what cryptography is about and the different areas of cryptography. So

the core of cryptography of course is secure communication that essentially

consists of two parts. The first is secured key establishment and then how do

we communicate securely once we have a shared key. We already said that secured

key establishment essentially amounts to Alice and Bob sending messages to one

another such that at the end of this protocol, there's a shared key that they

both agree on, shared key K, and beyond that, beyond just a shared key, in fact

Alice would know that she's talking to Bob and Bob would know that he's talking to

Alice. But a poor attacker who listens in on this conversation has no idea what the

shared key is. And we'll see how to do that later on in the course. Now once they

have a shared key, they want exchange messages securely using this key, and

we'll talk about encryption schemes that allow them to do that in such a way that

an attacker can't figure out what messages are being sent back and forth. And

furthermore an attacker cannot even tamper with this traffic without being detected.

In other words, these encryption schemes provide both confidentiality and

integrity. But cryptography does much, much, much more than just these two

things. And I want to give you a few examples of that. So the first example I

want to give you is what's called a digital signature. So a digital signature,

basically, is the analog of the signature in the physical world. In the physical

world, remember when you sign a document, essentially, you write your signature on

that document and your signature is always the same. You always write the same

signature on all documents that you wanna sign. In the digital world, this can't

possibly work because if the attacker just obtained one signed document from me, he

can cut and paste my signature unto some other document that I might not have

wanted to sign. And so, it's simply not possible in a digital world that my

signature is the same for all documents that I want to sign. So we're gonna talk

about how to construct digital signatures in the second half of the course. It's

really quite an interesting primitive and we'll see exactly how to do it. Just to

give you a hint, the way digital signatures work is basically by making the

digital signature via function of the content being signed. So an attacker who

tries to copy my signature from one document to another is not gonna succeed

because the signature. On the new document is not gonna be the proper function of the

data in the new document, and as a result, the signature won't verify. And as I said,

we're gonna see exactly how to construct digital signatures later on and then we'll

prove that those constructions are secure. Another application of cryptography that I

wanted to mention, is anonymous communication. So, here, imagine user

Alice wants to talk to some chat server, Bob. And, perhaps she wants to talk about

a medical condition, and so she wants to do that anonymously, so that the chat

server doesn't actually know who she is. Well, there's a standard method, called a

mixnet, that allows Alice to communicate over the public internet with Bob through

a sequence of proxies such that at the end of the communication Bob has no idea who he

just talked to. The way mixnets work is basically as Alice sends her messages

to Bob through a sequence of proxies, these messages get encrypted and

decrypted appropriately so that Bob has no idea who he talked to and the proxies

themselves don't even know that Alice is talking to Bob, or that actually who is

talking to whom more generally. One interesting thing about this anonymous

communication channel is, this is bi-directional. In other words, even

though Bob has no idea who he's talking to, he can still respond to Alice and

Alice will get those messages. Once we have anonymous communication, we can build

other privacy mechanisms. And I wanna give you one example which is called anonymous

digital cash. Remember that in the physical world if I have a physical

dollar, I can walk into a bookstore and buy a book and the merchant would have no

idea who I am. The question is whether we can do the exact same thing in the digital

world. In the digital world, basically, Alice might have a digital dollar,

a digital dollar coin. And she might wanna spend that digital dollar at some online

merchants, perhaps some online bookstore. Now, what we'd like to do is make it so

that when Alice spends her coin at the bookstore, the bookstore would have no

idea who Alice is. So we provide the same anonymity that we get from physical cash.

Now the problem is that in the digital world, Alice can take the coin that she

had, this one dollar coin, and before she spent it, she can actually make copies of it.

And then all of a sudden instead of just having just one dollar coin now all

of a sudden she has three dollar coins and they're all the same of course, and

there's nothing preventing her from taking those replicas of a dollar coin and

spending it at other merchants. And so the question is how do we provide anonymous

digital cash? But at the same time, also prevent Alice from double spending the

dollar coin at different merchants. In some sense there's a paradox here where

anonymity is in conflict with security because if we have anonymous cash there's

nothing to prevent Alice from double spending the coin and because the coin is

anonymous we have no way of telling who committed this fraud. And so the question

is how do we resolve this tension. And it turns out, it's completely doable. And

we'll talk about anonymous digital cash later on. Just to give you a hint, I'll

say that the way we do it is basically by making sure that if Alice spends the coin

once then no one knows who she is, but if she spends the coin more than once, all of

a sudden, her identity is completely exposed and then she could be subject to

all sorts of legal problems. And so that's how anonymous digital cash would

work at a high level and we'll see how to implement it later on in the course.

Another application of cryptography has to do with more abstract protocols, but

before I speak the general result, I want to give you two examples. So the

first example has to do with election systems. So here's the election problem.

Suppose ... we have two parties, party zero and party one. And voters vote for these

parties. So for example, this voter could have voted for party zero, this voter voted for

party one. And so on. So in this election, party zero got three votes and party two

got two votes. So the winner of the election, of course, is party zero. But

more generally, the winner of the election is the party who receives the majority of

the votes. Now, the voting problem is the following. The voters would somehow like

to compute the majority of the votes, but do it in such a way such that nothing else

is revealed about their individual votes. Okay? So the question is how to do that?

And to do so, we're gonna introduce an election center who's gonna help us

compute the majority, but keep the votes otherwise secret. And what the parties

will do is they will each send the funny encryption of their votes to the election

center in such a way that at the end of the election, the election center is able

to compute and output the winner of the election. However, other than the winner

of the election, nothing else is revealed about the individual votes. The individual

votes otherwise remain completely private. Of course the election center is also

gonna verify that this voter for example is allowed to vote and that the voter has

only voted once. But other than that information the election center and the

rest of the world learned nothing else about that voter's vote other than the

result of the election. So this is an example of a protocol that involves six

parties. In this case, there are five voters in one election center. These

parties compute amongst themselves. And at the end of the computation, the result of

the election is known but nothing else is revealed about the individual inputs. Now

a similar problem comes up in the context of private auctions. So in a private

auction every bidder has his own bid that he wants to bid. And now suppose the

auction mechanism that's being used is what's called a Vickrey auction where the

definition of a Vickrey auction is that the winner is the highest bidder. But the

amounts that the winner pays is actually the second highest bid. So he pays the

second highest bid. Okay, so this is a standard auction mechanism called the

Vickrey auction. And now what we'd like to do is basically enable the participants to

compute, to figure out who the highest bidder is and how much he's supposed to

pay, but other than that, all other information about the individual bids

should remain secret. So for example, the actual amount that the highest bidder bid

should remain secret. The only thing that should become public is the second highest

bid and the identity of the highest bidder. So again now, the way we will do

that is we'll introduce an auction center, and in a similar way, essentially, everybody

will send their encrypted bids to the auction center. The auction center will

compute the identity of the winner and in fact he will also compute the second

highest bid but other than these two values, nothing else is revealed about the

individual bids. Now, this is actually an example of a much more general problem

called secure multi-party computation. Let me explain what secure multi-party

computation is about. So here, basically abstractly, the participants have a secret

inputs to themselves. So, in the case of an election, the inputs would be the

votes. In the case of an auction, the inputs would be the secret bids. And then

what they would like to do is compute some sort of a function of their inputs.

Again, in the case of an election, the function's a majority. In the case of

auction, the function happens to be the second highest, largest number among x one

to x four. And the question is, how can they do that, such that the value of the

function is revealed, but nothing else is revealed about the individual votes? So

let me show you kind of a dumb, insecure way of doing it. What we do is introduce a

trusted party. And then, this trusted authority basically collects individual

inputs. And it kinda promises to keep the individual inputs secret, so that only it

would know what they are. And then, it publishes the value of the function, to

the world. So, the idea is now that the value of the function became public, but

nothing else is revealed about the individual inputs. But, of course, you got

this trusted authority that you got to trust, and if for some reason it's not

trustworthy, then you have a problem. And so, there's a very central theorem in

crypto and it really is quite a surprising fact. That says that any

computation you'd like to do, any function F you'd like to compute, that you can

compute with a trusted authority, you can also do without a trusted authority.

Let me at a high level explain what this means. Basically, what we're gonna do, is

we're gonna get rid of the authority. So the parties are actually not gonna send

their inputs to the authority. And, in fact, there's no longer going to be an

authority in the system. Instead, what the parties are gonna do, is they're gonna

talk to one another using some protocol. Such that at the end of the protocol all

of a sudden the value of the function becomes known to everybody. And yet

nothing other than the value of the function is revealed. In other words, the

individual inputs is still kept secret. But again there's no authority, there's

just a way for them to talk to one another such that the final output is revealed. So

this is a fairly general result, it's kind of a surprising fact that is at all

doable. And in fact it is and towards the end of the class we'll actually see how to

make this happen. Now, there are some applications of cryptography that I can't

classify any other way other than to say that they are purely magical. Let me give

you two examples of that. So the first is what's called privately outsourcing

computation. So I'll give you an example of a Google search just to illustrate the

point. So imagine Alice has a search query that she wants to issue. It turns out that

there are very special encryption schemes such that Alice can send an encryption of

her query to Google. And then because of the property of the encryption scheme

Google can actually compute on the encrypted values without knowing what the

plain texts are. So Google can actually run its massive search algorithm on the

encrypted query and recover in encrypted results. Okay. Google will send the

encrypted results back to Alice. Alice will decrypt and then she will receive the

results. But the magic here is all Google saw was just encryptions of her queries

and nothing else. And so, Google as a result has no idea what Alice just

searched for and nevertheless Alice actually learned exactly what she

wanted to learn. Okay so, these are magical kind of encryption schemes. They're

fairly recent, this is only a new development from about two or three years

ago, that allows us to compute on encrypted data, even though we don't really know

what's inside the encryption. Now, before you rush off and think about implementing

this, I should warn you that this is really at this point just theoretical, in

the sense that running a Google search on encryption data probably would take a

billion years. But nevertheless, just the fact that this is doable is already really

surprising, and is already quite useful for relatively simple computations. So in

fact, we'll see some applications of this later on. The other magical application I

want to show you is what's called zero knowledge. And in particular, I'll tell

you about something called the zero knowledge proof of knowledge. So here ...

what happens is there's a certain number N, which Alice knows. And the way

the number N was constructed is as a product of two large primes. So, imagine

here we have two primes, P and Q. Each one you can think of it as like 1000 digits.

And you probably know that multiplying two 1000-digit numbers is fairly easy. But if

I just give you their product, figuring out their factorization into primes is

actually quite difficult. And, in fact, we're gonna use the fact that factoring is

difficult to build public key cryptosystems in the second half of the course.

Okay, so Alice happens to have this number N, and she also knows the factorization of

N. Now Bob just has the number N. He doesn't actually know the factorization.

Now, the magical fact about the zero knowledge proof of knowledge, is that

Alice can prove to Bob that she knows the factorization of N. Yes, you can actually

give this proof to Bob, that Bob can check, and become convinced that Alice

knows the factorization of N, however Bob learns nothing at all. About the factors P

and Q, and this is provable. Bob absolutely learns nothing at all about the

factors P and Q. And the statement actually is very, very general. This is

not just about proving the factorization of N. In fact, almost any puzzle that you

want to prove that you know an answer to, you can prove it is your knowledge. So if

you have a crossword puzzle that you've solved. Well, maybe crosswords is not the

best example. But if you have like a Sudoku puzzle, for example, that you want

to prove that you've solved, you can prove it to Bob in a way that Bob would learn

nothing at all about the solution, and yet Bob would be convinced that you really do

have a solution to this puzzle. Okay. So those are kind of magical applications.

And so the last thing I want to say is that modern cryptography is a very

rigorous science. And in fact, every concept we're gonna describe is gonna

follow three very rigorous steps, okay, and we're gonna see these three steps

again and again and again so I wanna explain what they are. So the first thing

we're gonna do when we introduce a new primitive like a digital signature is

we're gonna specify precisely what the threat model is. That is, what can an

attacker do to attack a digital signature and what is his goal in forging

signatures? Okay, so we're gonna define exactly what does it mean for a signature

for example to be unforgeable. Unforgeable. Okay and I'm giving digital

signatures just as an example. For every primitive we describe we're gonna

precisely define what the threat model is. Then we're gonna propose a construction

and then we're gonna give a proof that any attacker that's able to attack the

construction under this threat model. That attacker can also be used to solve some

underlying hard problem. And as a result, if the problem really is hard, that

actually proves that no attacker can break the construction under the threat model.

Okay. But these three steps are actually quite important. In the case of

signatures, we'll define what it means for a signature to be, forgeable, then we'll

give a construction, and then for example we'll say that anyone who can break our

construction can then be used to say factor integers, which is believed to be a

hard problem. Okay, so we're going to follow these three steps throughout, and

then you'll see how this actually comes about. Okay, so this is the end of the

segment. And then in the next segment we'll talk a little bit about the history

of cryptography.