Good morning, ladies and gentlemen.
I'd like, today, to speak about zero-knowledge.
Or, I'd like to speak about nothing but the truth.
So let me ask the question that you may already
wondering about, namely, what is zero-knowledge?
Well, zero-knowledge is a new and powerful theory
of both correctness and privacy of information
with big impact both from a theoretical point of view,
and a practical point of view.
And this theory has been developed quite quickly
in recent years.
And now has already a very rich history.
These are, according to me, really the papers that made it.
And if you knew already that MIT was a center of knowledge,
you'd be happy to know that MIT is also
center of zero knowledge.
Not only the starred people here all belong to our lab,
but also most of the other ones were associated to our lab
at one point or another.
Well, we were saying correctness and privacy of information.
Now traditionally, checking the correctness of some information
is the domain of proofs.
So the first thing that we are going to ask today
is, what is a proof?
And once we have answered this big question
with a sufficient level of generality,
we will proceed to tackle more ambitious questions.
Such as, how much knowledge should the proof contain?
Let me start with the first question.
What is a proof?
No matter how you put it, a pool is an interaction
between two parties.
One party better works hard, and we'll call him the prover.
And the other party better be lazy.
And we call him the verifier.
Should the time necessary to find the proof of theorem
roughly coincide with the time necessary to check
whether the proof is correct?
Then all mathematicians would be out of jobs.
So that is what a proof is.
And let me give you a simple example, which technically,
within a framework called NP on which
Mike Sipser spoke about today.
So here we have our input statement the theorem
we would like to prove.
We have two graphs, A and B. And they are the same graphs,
except they are drawn differently,
and they changed the names of their nodes.
One has numbers.
One has letters.
Mathematically, when this is the case,
you just say that A and B are isomorphic graphs.
The same graph but drawn differently.
Now, in this case, it is immediate
that these two graphs are the same.
But should this graph have had thousands of nodes,
we wouldn't be able to distinguish
or to detect this fact at all.
Therefore, this is a plausible hard theorem.
But the prover can't convince us that the two graphs are
the same in this simple case, like in a very complicated
case, by just sending over the correspondence, a 1 to 1
correspondence between the vertices of A
and the vertices of B that preserve the edges.
That is to say, A over here, really is vertex 5 over there.
B is free, and so on.
And the verifier has a very easy job.
Only to detect that each vertex, each edge in the first graph,
is also an edge in the second graph.
For instance, 1, 2 is an edge in A, But 1 is d, and 2 is c.
So vertice d be an edge of it in the second graph.
And indeed, there it is.
And also should check with vise versa, but every edge over here
is an edge over there.
And you can see this may be important, because if these
are the graphs of two large molecules,
and one has been discovered in Europe and one
in the United States, and they want
to know if the two molecules are the same.
Each researcher constructs the molecule the way he wants,
and cannot by eye inspection find that out.
But once that you look at this, which is a specific example,
but is a canonical way in which proofs are given.
There is a statement and somebody writes the proof,
publishes in a book, namely, in our case, The Correspondence,
and then the verifier reads the paper.
It will be immediate that this way of proving things
betrays much more knowledge than we are asking for.
Here we are asking about the single bit question,
are A and B the same graph?
Yes or no?
But the only way for a prover to publish it on a piece of paper
with proof, is to give away the entire correspondence.
Not only the single bit we are asking for,
but the entire thing.
And that is intuitively the case with this.
Proofs betray much more knowledge than necessary,
perhaps.
But this raises a very good question.
Namely, what is knowledge?
And that raises even a better question.
Is there life--
[LAUGHING]
So today, we want to answer this question,
but from a computer science point of view.
[LAUGHING]
So let me to refine our intuition, [INAUDIBLE] all
can be made [INAUDIBLE] given more time.
Let me tell you what knowledge is by just giving what I'd
like to call the Knowledge Act.
The Knowledge Act is composed if you want, by 2 axioms.
First axiom says, efficient computation is for free.
What does that mean?
Let me tell you in a day--
everyday example.
You are walking on the street with an integer
on your left hand and an integer on your right hand.
And all of a sudden you meet some guy who says,
hey, hey you with a two integers.
$1,000 and I will sell you the product of these two integers.
Then I don't know what you are going to answer him.
But what I will say is you must be crazy,
because multiplication is easy.
I know how to multiply and adjust and I'll keep the $1,000
and get the product by myself.
So we don't pay for efficient computation.
The second axiom, random strings for free too.
What does that mean?
You usually, before you are walking on the street
and some other crazy-- the same crazy guy stops you
again and says, hey $1,000 and I'm
going to give you 100 random bit string.
He says, look.
You must be crazy.
I have a coin the same way that you do.
And I can flip coins as well as you do.
So I flip 100 times my coin and I save $1,000.
So in such a case, what does convey knowledge instead?
Well, let's assume now that you are again
walking on the street with a graph on your left hand
and a graph on your right hand.
And the same guys asks you, George, you
are having to isomorphic graphs.
$1,000 and I sell you the correspondence.
Then you bargain for price.
Because essentially, that information has knowledge.
And what is knowledge?
What has a chance to convey knowledge
is the output of an feasible computation.
A computation that would require me too long, because the chance
of conveying knowledge.
But once you define knowledge of a sway,
you immediately see the traditional proofs
is an overkill.
It's not only the problem of the graph
I saw my face on problem like we saw before, is always the case.
For the proofs that you publish regularly,
the proof-- the good old proofs, they convey too much knowledge
when they need.
It's like shooting at the fly with a gun.
Now, given this is a problem, a traditional proofs,
well, let's see.
These proofs are a mental construct
roughly 2,500 years ago, which started in ancient Greece.
And we have been living very happily in the house
with Euclid and others built for us,
except that in recent years, this house is becoming
a little bit small for us.
So when you tackle questions about knowledge,
we don't quite fit in there anymore.
And we want to build a new house,
retaining a wave of the flavor of the old one.
So we don't want any more to deal with traditional proofs,
but a different type of object, which
I'm going to present right now.
And hopefully you'll be convinced
of it is enough for the same thing but we can be happy.
So I'd like therefore, to give you
a flavor of these new proofs via an abridged example.
And you should notice that these new proofs differ
from the classical notion of a proof in two
important respects.
First, they are probabilistic.
Prover and verifier flip coins doing the proofing process.
Second, they are instructed.
They cannot be published in a book,
but the prover and the verifier will talk back and forth,
very much like in classroom teaching.
Let's have a look at the example.
Here is the proof of graph isomorphism.
Input, we have two graphs, A and B.
And one way as we said to prove A and B on the same graph
is ship over to the verifier, the correspondence.
The prover and the verifier instead
will be engaging in a somewhat more complicated game.
They are going to repeat K times the following instructions.
First, the prover flips coins to generate C, a fared graph,
which is a scramble version of A and B. So C is a graph
and is isomorphic to A and isomorphic to B,
because A and B are isomorphic between what each other.
The only point is really to prove it.
So takes this random graph isomorphic to both,
and sends it over.
Claiming C is isomorphic to both A and B.
Now, that the verifier doesn't want to listen to anything.
He flips a coin to decide at random between A and B.
And let us assume he has the going
has come up A. Therefore he will send A request to the prover.
And the prover will satisfy this request
by sending pi, a correspondence between the nodes of A
and the nodes of C with Cervantes,
thereby proving with A and C aren't missing graph.
And verify it given the correspondence, he says,
that's true.
A and C are the same graph.
He says OK.
So much fun, we'll do it over and over again, K times.
And even verifier said OK K times in a row,
then they will say fine, I'm convinced,
A and B are the same graph.
Why is this a proof?
That's an interaction, but way of proof?
Well, first of all, let me tell you that if the film is true,
the verify and will be convinced.
It goes the prover does what I said,
but verifier does what I said and they
will be convinced that at the time, all of it at the end
all the time.
Let's now argue over whether this
is a proof by contradiction as we
prove almost anything anyway.
So let us assume that the film is false.
Can we convince somebody over a false film?
So let's assume now with A and B are different graphs
but we assume you can figure it out.
Then they claim that no matter how the prover choose
a C, if a C is not the same as A or C is not the same as C
or is neither.
So when C is shipped over no matter
how it's chosen, when re-verify a flips a coin between A and B,
he has at least a chance one half
of catching the prover in the wrong.
Because even prover construct C by scrambling A say,
and even verifier asks for A, he can ship over
the correspondence between A and C.
But if a prover constructed C by scrambling B,
and the verifier asks for A, he has nothing to send here.
So then the verifier would say no,
this is not the correspondence because there's an A.
So we chance a half, whatever graph you send here the prover
cannot satisfy the verifier's request.
And if they do this 2 times, the prover has only a chance
1 and 1/4 of satisfying to verifier.
And if you do it the K times, its chances are 1 and 2
to the K. And that's a very small number.
If K is 300 2 to the 300 is larger than the number
of electrons in our universe.
OK.
And now they say, why do we go to the trouble of such
a complicated truth?
But not too complicated, but nonetheless is not
a stretch for understanding the correspondence.
Because the proof I just talk about is a zero knowledge
proof.
And why is it zero knowledge?
Well, because at the end of the proof,
the verifier knows that A and B are the same graph.
That's what the proof want to give it away.
But what else does he know at the end?
He also knows which words he and the prover
exchange with one another.
He was there.
Listen, now I claim but from these words,
you can retrieve that A and B are the same graph but you
cannot retrieve anything else.
And how am I going to say that?
Actually, how am I going to prove that?
Well, here it is how.
Let's assume now that the verifier
knows priori with A and B are isomorphic graphs.
This is single beat.
He only knows that A and B are missing graph.
Now, he claimed that the proof is relevant for him
because he can come up with the proof himself.
Here is how.
So the verifier now first flips a coin
to decide between A or B. And let's assume that the coin has
come up A. Therefore, given the coin has come up A,
he scrambles by some correspondence
pi, the vertices of A and creates a graph C.
So he comes up with a renaming of the vertices of A,
renames the vertices and comes up with a graph C.
Then is going to lay down with the following words.
C with an arrow from left to right.
A with an arrow from right to left.
And pi with an arrow from left to right.
End of the quotes.
Now, I claim that this conversation
is equally likely is essentially the same
with this conversation.
Why?
Well, the first entry, the first message here,
is a randomly scrambled version of A and B. And so is here.
The second message here is the result of a coin toss.
And so is here.
Here, we noticed that the coin we flipped after seeing C,
and here we flipped up before.
But none of it is a random coin toss.
And finally, what is here?
Here is a correspondence between vertices of A and vertices of C
that preserve the edges.
And so is here.
So you see why this mechanism proves to you that A and B are
isomorphic graphs, if you knew this beforehand,
this mechanism doesn't add anything else.
Because you could reconstruct the conversations yourself
and whatever you can do by yourself is your knowledge.
So this proof is a zero knowledge on top of the fact
that A and B are the same graph.
So I've showed you basically a way for the graph isomorphism
problem that convinces you that the proof exists
even though you don't even know how the proof starts.
And this is just a small piece of this theory
of zero knowledge which goes on to answer
many other questions not fundamental to our mathematical
thinking.
Namely, what does it mean to prove something.
What does it mean that something is false?
What does it mean to convey knowledge?
What does it mean to be totally unintelligible?
Now, a lot of leverage that you can
do if you answer correctly such a question.
And in fact, look, you don't go to bovver the classical notion
of a proof which has been there for 500 years from nothing.
Because once you are large such powerful notions
but very powerful.
You just walk outside even crazier
because it was built using mathematical formulas
and prove that it stood before people really put together.
So once if you tackle this notion of proofs,
you gain power.
And in fact, this theory has applications in practice.
And these applications are nothing less
of privacy of communication.
Ability of checking programs, checking program or designing
programs so that they are much more reliable than we
could do before.
And I don't have the time.
So if it's a question that lies at the heart of our computer
age, but I don't have a question to illustrate this.
But in the last two minutes left to me,
I'm going perhaps to take just a small piece and one
small piece.
I chose is the problem of passwords.
Passwords is an ancient problem.
Or rather a problem is an ancient tool.
And I was rereading to see it is a while ago
and with the continuous source of inspiration for me.
And he was describing a famous battle between the Athenians
and the Syracusans, roughly around 400 BC.
And what is strange about this battle,
the battle was a nighttime.
So they couldn't-- the two armies couldn't see each other
and they couldn't recognize each other.
Therefore, the Athenians had the password.
But they were shouting with passwords back and forth
so much that the Syracusans got hold of the password
and they started shouting also, and they
passed through their lines and then attacked them on the back
and defeated them.
Now, this problem does not arise just
because we are so back in time.
This is a problem and today's also.
If you use passwords for instance
to login in the morning from your home terminal
to the mainframe, how does this work?
It's the same thing.
Well, the mainframe has a list of users and their passwords
in my case, for president.
Now, which my friends do guests but they
don't guess the number of exclamative points.
So if the right password is introduced,
then the mainframe says, yes this
must be Silvio lets this guy have access to my files.
But what is the problem with this scheme?
Well, the problem is that listening on that
may be a bad guy.
Therefore he captures my passwords very much
like this occlusions.
And he's going next today to impersonate me.
And that is intrinsic in the nature of a password.
If somebody figures out your password, you're dead.
From 400 we see up to now but not anymore.
Let me tell you why.
And here is our zero knowledge comes to the rescue.
You see in the mainframe, just to keep
it simple for the sake of example
I'm going to store close to my name a pair of graphs,
say files on the vertices.
And they're copies, different copies,
scrambled copies of the same graph.
So A and B are isomorphic.
But I do not store in the mainframe the isomorphism so
as the parentheses indicate.
I do not store the correspondence.
I will keep the correspondence.
And now I tell the mainframe who proves
to you that A is the same graph and B, that's me.
Let him have access to my files.
And now, in the morning, which will take a while but not.
I'm going to wake up, scramble--
give a random scramble version C of A and B
and ship it over to the mainframe.
The mainframe flips a coin to decide between A and B,
say he decides A. And therefore he
request the correspondence between A and C,
and they give him the response.
And the mainframe says, OK, so far so good.
This is a correspondence between A and C.
And now, we are going to do it 20 times.
It will take a while.
But what do I gain by this?
You see what I gain is, if somebody now
is listening to these conversations
he is rather confused.
Why?
Because this proof I already argued
before is a zero knowledge proof.
So only it betrays is the fact that A and B are the same,
but not to what the correspondence is.
So even though somebody is listening
to this identification process, he
has no way to impersonate me.
And just to give you just a simple example,
assume this guy records what graph C I send over.
And then in the previous conversation
the mainframe has asked me for A. So he sends over the same C,
assume that the computer chooses at random between A and B
and he's lucky.
He chooses the same A. Therefore,
he can send the same pi that I sent.
But for the second graph, the computer originally
say you ask me for A. But now, he's asking him for B,
then he doesn't know what cosponsorship say.
You see what it is?
Essentially this is a trick to shrink down
an exponential number of questions to very very few.
Good.
Now, this is not practical by any stretch of imagination.
However, this does not bother us as theoreticians.
But let me tell you why he does not bother us as theoreticians.
Because now, once you know what you are shooting for,
and this is the last slide of my talk,
then you can make it efficient later.
And in fact, not using graph isomorphism
but using number theory, the same identification process
much more efficient has been devised
by Gold Wasser and myself and Rackoff
and then improved by Fiat, Feige and Shamir.
And finally, Shamir and I have a zero knowledge identification
scheme by which in the morning to identify yourself,
all you need to have is two multiplications, which
I consider it practical.
Now, for the future.
Well, we have only explored the tip of the iceberg
and there is a lot of other things
that needs to be discovered in really farther down,
and we want to bring it to light.
Let me tell you a waiver of it, thanks to zero knowledge,
cryptography is undergoing a transition
from an art to a science.
Thank you.
[APPLAUSE]
[MUSIC PLAYING]