What is cryptography? (15 min)

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.