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.