[MUSIC PLAYING]
So actually, before I start the topic of my talk I want to--
I'd like to acknowledge two MIT graduates who
are co-authors on some of the work
that Mike Dertouzos mentioned yesterday in the banquet.
One of them is a great PhD student, Joe Kilian--
still in the lab.
And the other one is Charles Rackoff--
was joint on the work on zero-knowledge proofs
with Silvio Micali and myself.
So now let's go on to the search for provably
secure cryptosystems.
So cryptography in its simplest form
is simply the problem of exchanging secure messages
over an insecure channel.
Alice wants to send Bob a message so
that the listener on the line has no way to figure out
what the message is.
And traditionally this was achieved by Alice and Bob
meeting a priori and agreeing on some secret code
to use in order to communicate, hoping that the listener will
have no way to figure out what the message is.
And they also traditionally-- it has been somewhat
of an equal fight between the code makers, Alice
and Bob, and the code breaker, who is the listener.
In the sense that all codes were broken
and it was just a matter of time when that will happen.
In fact, when Alice and Bob made up their code
they basically tried to break it themselves.
And when they failed, they decided
that it was a pretty good code.
They're going to use it.
So they had no guarantee that the code that they are using
will actually be secure.
Well, in the last 10 years, there's
been a tremendous progress on the theoretical front
toward actually designing codes which
are provably hard to break.
Where you, Alice and Bob were given the guarantee that no
matter what the listener does he cannot figure out what is
the message sent across.
And this progress has gone really hand-in-hand
with the increasing use of, or need for,
cryptography in the commercial sector.
And what I'll do in this talk basically are two things.
First of all, I'll try to give you
an idea of what is in the heart of these modern cryptographic
systems.
And in the second part, I'll sort of
turn to a more futuristic setting
where we have a distributed network of computers.
And discuss what is the role of cryptography,
in this future setting, with many computers hooked up
together.
But let's begin in the beginning.
And the beginning really starts with a very important paper
by Diffie Hellman in '76, where they put forth the goal.
OK, so they put forth the idea that what
we should be looking for are codes,
such that we can prove that breaking the code
is a hard, impossible, computational problem.
And by impossible, I mean that Alice and Bob
will have the guarantee that as they're communicating
across the line there was just no time, simply not
enough time in the universe for the listener to crack the code.
That's an incredibly ambitious goal
if you went to the talk of Mike Sipser.
Because there are no natural examples,
that we know of, for which we can actually
prove to be that difficult. But Diffie and Hellman do
more than just propose this goal,
they actually give us an idea of how
to proceed toward achieving it.
And this idea is best illustrated
by its first implementation, which
was proposed in this laboratory by Rivest, Shamir, and Adleman,
and is known as the RSA scheme.
By the way, I think that Diffie is also a graduate of MIT.
But the work was done at Stanford.
So this is the idea of Rivest, Shamir, and Adleman,
abbreviated by RSA.
Consider the problem of factoring integers.
So you're given a composite number, n, a large number, much
larger than this, and you're trying
to find out its prime factors.
That is a hard problem.
Again, in spite of what you may have read in The New York Times
recently.
And what RSA says is the following,
take this function f of x.
What does this function do to x?
It takes x to the power alpha mod n.
So regardless of what this really means
it has the following three properties.
First of all, given x, it's very easy to compute f of x.
Second of all, given f of x, it is extremely hard
computationally to find out what x is.
And third, if you happen to know some extra information,
if you happen to know the factors of n,
then it is extremely easy to figure out what x is,
starting from f of x.
These three properties is what gives this function
its name, which is a one-way trapdoor function.
One-way, because it's easy in one way,
but hard the other way.
And trapdoor, because if you happen
to know some extra trapdoor information,
the function is actually easy to invert.
Now, what does this have to do with secure communication?
Well, it has everything to do with it.
In particular, what Alice and Bob can now do
is the following.
If Alice now wants to send Bob a secure message, all he does
is the following.
He takes f and computes f of the message
and sends it to Bob across the line.
She can do that because that's an easy transformation.
Now, the listener, who's trying to figure out
what the message is, would like to invert f.
But he cannot do that since that's a hard transformation.
And finally, Bob, the legal recipient,
should be able to figure out what the message is.
So we will give him the extra trapdoor information,
so he will be able to invert the function
and figure out what the message is.
So this is really an incredibly beautiful idea
which manages to break the symmetry between the code
makers, Alice and Bob, and the listener.
Alice and Bob can perform an easy computation
and communicate securely.
The listener is confronted with an impossible computation
and is not able to break the system.
Now, let's recall our goal.
Our goal was to come up with codes where we can actually
prove mathematically that breaking the code
is as hard as solving a computationally
infeasible problem, let's say, like factoring integers.
So if we sit down to actually prove this
we have to sort of sit back and think.
All right, so we want to prove that
what does it really mean that it's
impossible to break the code?
OK, we have not defined yet precisely what
it means for the listener to break the code.
And here's one possible meaning that you can give.
In fact, it's extremely strong, meaning
suppose we could really do what we wanted.
What we would want, would be for an encryption algorithm
to be the same as taking x and putting it inside
of an opaque envelope, and sending it across the line.
So that the listener now, looking at the line,
just sees an envelope and has no idea of what the contents are.
So if this is really what we're shooting for,
is it what we are getting?
The answer is not quite.
Because if you look at a function applied to an x
It's an algebraic function or a function.
Then it is not quite as good as putting
x inside of an envelope.
For example, suppose x was just 0,
or 1 It turns out that by looking at f of 0,
you can tell that this is f of 0.
Or, by looking at f of 1, you can tell that this is f of 1.
Another example is that f of x doesn't hide all information
or partial information about x that you may want to hide.
The same way that you do when you
put x inside of an envelope.
A third possibility is that you would want to make sure that
the listener cannot detect that you've sent the same message
twice.
Or the relations between messages
that you have been sending.
That will be captured by envelopes,
but it will not be captured by f of x.
Because f of x, sent twice, is always the same.
So you may be thinking, well, I'm setting my goals too high.
We cannot achieve envelopes.
But the answer is actually that you
can achieve envelopes and let me give you an idea how.
But again, before we show how we have to define mathematically,
what do we mean by an envelope?
We can't just say that we mean a physical envelope.
And this is the definition.
Our definition is as follows.
We'll say that a cryptosystem is secure if, for all message
pairs m1 and 2, the blue message and the red message,
which you may think of for convenient is 0 and 1,
the listener cannot distinguish between an encryption of m1,
an encryption of m2, better than 50-50.
In other words, take m1 and encrypt it.
Take m2 and encrypt it.
Put it in those two encryptions, in front of the listener,
and ask him to guess which is which.
What we want is that for the listener
to have no better chance than just flip a coin and say,
well, I think this must be m1.
Or, I think this must be m2.
Notice that that is exactly what happens.
If you put m1 in an envelope and m2 in an envelope,
scramble them up, and put them in front of the listener.
He will have no idea where m1 is.
The best he can do is guess at random.
And in particular, this definition,
if you can find a cryptosystem satisfying it,
will solve all the problems of the previous slide.
So no partial information will leak.
You cannot detect the two messages are sent,
the same messages sent twice and you can send all possible
messages this way.
Note also, that I've changed the notation on this slide.
So here I'm using "E", for envelope,
or for encryption, while before we're using a function, "f".
And the reason is that there really
is no way that we can achieve this sort of security
using one single function, one deterministic function.
The simplest way to see that is that, if we
send the same message twice, using f,
you will tell that the same message is sent twice.
And that is something that I want to outrule
with this definition.
So this gives you an idea of where the solution and what
the solution will be like.
The solution is probabilistic encryption by Micali
and myself in '82.
And if the solution has the following property,
that every message is going to have many possible encryptions.
So it's not going to be true anymore
that when we send the same message twice,
we necessarily are sending the same encryption.
So every m will have many possible encryptions
associated with it.
But we will still keep the trapdoor function flavor
so that it's going to be still hard for the listener,
starting with one of these encryptions,
to figure out the original message.
And finally, if you knew some extra information,
if you did know the trap door, then you
can figure out what the message is.
So suppose we could construct such a primitive.
Then all Alice has to do is to pick one of these encodings
at random--
and at random here is very important--
and to send this encoding across to Bob.
Bob figures out what the message is since he has the trap door,
and the listener is stuck.
And notice here that in fact, if we send the same message twice
here, then what's the probability that Alice will
pick the same encoding twice?
Well, if there's lots of encodings to choose from that
will be very small.
So it's a fine goal and it is achievable.
And now, I will get to the most technical slide in my talk,
actually trying to give you an idea of how it is achievable.
So bear with me.
It will get better.
I hope.
All right, so forget sending arbitrary messages.
Suppose that all we want to send is either a 0 or a 1,
how do we do that?
Well, I pointed out earlier that if you apply f to x,
and f is this trapdoor function, then f doesn't necessarily
hide all information about x.
But what you should observe is that f must
hide some information about x.
So if f really is trap door, there
must be something that it's hiding about x.
And in particular, there was a single bit of information
about x that f is hiding.
So for example, to make this more concrete
for the case of the RSA function,
if you just look at f of x, one can
prove that there's no way that you
can tell whether x is an even number, or x is an odd number.
So f of x hides very well, whether x is even, or x is odd.
In the risk of being redundant, basically, what we
realize is the following picture.
That the listener, when he looks at the purple f of x's--
which are x's applied to even numbers--
and we looked at the green f of x's--
x is applied to odd numbers--
has no way to tell these two spaces apart.
To him they look identical.
And once that is real-- and once we realize that,
our encryption scheme follows.
Now, in order to send an encryption of a zero,
all we do is pick a purple f of x, and send it to Bob.
And if we wanted to send a one, all we
do is pick a green f of x, and send it to Bob.
Now Bob is able to invert this function
so he can tell whether our x is purple,
or whether our x is green.
Namely whether our x is even, or whether our x is odd.
And the listener has no way to distinguish between those even
purple x's and the green odd x's.
Our slide is completed and you must be thinking two things.
First of all, you want to send more than just zeros and ones.
And to that my answer is, OK, write your message
as a sequence of zeros and ones and send each bit individually.
And the second thing you must be thinking
is, wow, this might be nice theoretically,
but it's extremely expensive.
So for every bit you've got to do a tremendous amount of work
and send a tremendous amount of information across the line.
So, you know, don't be of little faith.
Basically, with more theory and more ideas
you can actually get the same security level proposed
by this scheme, and do it as efficiently
as the original trapdoor function schemes--
almost as efficiently.
Pretty close.
OK, so just to summarize this, if we put all this together,
Diffie and Hellman, and RSA, and probablistic encryption,
and ideas by Blum, Blum, and Shub, what we can show now
is a cryptosystem, which is secure, if and only
if, factoring in integers is a hard problem.
That is, we've managed to achieve our original goal that
making a code, where breaking the code,
is as hard as solving a hard computational problem.
Notice that this theorem is basically a double edged sword.
Either you've realized an incredibly secure cryptosystem.
Or, the crypto analyst has managed to factor integers,
has managed to solve a problem, which has been defying
mathematicians for centuries.
And that's a risk you may want to take.
OK, so this wraps up the story of encryption,
but it does not wrap up my talk.
And it actually doesn't wrap up the story
of modern cryptography.
There's a lot more that we can do
and I will only mention one other result in cryptography.
Basically, we're going to go from the most basic problem
to the current issues that people are working on.
So we're going to leave behind Alice
and Bob and their communication problems.
And we're going to go into a distributed environment where
we don't only have Alice and Bob.
But we have a whole bunch of processors hooked up together,
in some arbitrary fashion.
And each has some, let's say, some local state
which I'll just denote by this processors
has x1, x2, x3, x4, xn.
And what they'd like to do is not only
communicate in pairs in privacy.
But what they'd like to do is to compute some global computation
with respect to these private inputs.
So generally they want to compute a function, "g",
defined on their local states.
This computation should be correct.
OK, so they want to be guaranteed that in the end
they have the right result. And it should be private.
What do we mean by private?
That in the end, after the computation is completed
and they have received the outcome--
receive the outcome of the function--
we want to give them the guarantee that other processors
don't find out more than the function gives them
about the local state.
And to make life even worse, some of these processors
maybe faulty.
So they could either be benign faults, like--
their eyes aren't aligned here--
OK, they can either be benign faults,
that is they just crash.
Or we could consider the worst type of faults,
they be-- they may maliciously be cooperating
to sabotage a computation, and to find out
information about each other.
What is an example of such a computational goal?
I mean, are there examples or is this just a paranoiac setting?
I mean, we are cryptographers, so we are somewhat paranoid.
So what are some examples?
So one example is that this network
would like to elect a president, let's say.
So you think about each one of these processors
as having a vote.
And they would like to compute the tally.
They want two properties out of this computation.
First they want to be able to verify that a tally was
computed correctly.
And second, they want to make sure
that their vote has kept private.
And perhaps, even third, they would
like to ensure that the vote of one processor
was selected independently of the vote of another processor.
This is one example where it's fairly clear that you would
like to get the correct answer.
And you want to keep your private state private.
What's another example?
So another example is, suppose that these processors are
all databases containing lists of names.
These are the employees of the CIA, NSA, FBI,
DARPA, and Project MAC.
And they would like to find out who is employed
by all of these agencies.
But none of them, except Project MAC, of course,
would like to expose their employees.
So how can they do it?
This is a global computation.
They would like to find out who is in all the lists
without telling who is in any of the list.
Something like that.
Good, so how can they achieve this?
Or, if we wanted to be archaic, they could just send everything
to a trusted center and he would compute that for them
and give them the results.
But that's really going back to the centralized world.
And, not only that, as we said, we are paranoid.
We do not trust the center.
So what we can do is actually achieve
this in a distributed manner and the theorem is as follows.
If the processers can compute securely between themselves
in pairs, and we're guaranteed that less than a third of them
collaborate maliciously to sabotage a computation,
then give me any function you like,
let's say, like voting, or database intersection,
or whatever you may be interested in.
Just give me the input/output specification
of the function and we can give you--
or it can be given--
a protocol for these impostors to follow
so as to compute the function, both correctly and privately.
I haven't defined what a protocol means.
But you can keep in mind following intuitive definition.
We will tell processor, "i", what to tell processor,
"j", at time, "t", so that in the end of this protocol
the function is actually being realized.
And we have a guarantee that it's been realized correctly
while keeping privacy intact.
And that is really the end.
A natural question is, what's for the future?
And the answer is that we've actually
have an incredibly developed theory of cryptography now.
And it's all developed, really based on, these very simple,
nice assumptions that there exist trapdoor functions.
And it is the most interesting goal right now
is to actually figure out whether these assumptions are
minimal assumptions or can you somehow shrink them
down to the point where we can prove that they hold.
Thank you.
[MUSIC PLAYING]