So what is cryptography?
Cryptography is a field that deals with securing
communication and computation.
We want to ensure both confidentiality and integrity.
Today cryptography is used all over the place.
The users often don't even know they're using cryptography,
your cellphone uses it all the time.
Anything you do online has cryptography in it.
In cryptography, what motivates us is the real world problems.
So what do we study?
Whatever the world
kind of throws at us.
My name is Yael Tauman Kalai
I'm a researcher at Microsoft
and an adjunct professor at M.I.T.
My research focuses on theoretical cryptography in particular.
But more largely
I'm interested in theoretical computer science.
So people use cryptography for thousands of years
and they often just came up with schemes and hope
they were secure and everything was secret about them.
One key takeaway
about modern cryptography, as opposed to like
the classical cryptography that was used thousands of years ago,
Is that today, actually, all our algorithms are public.
The way I think of it, whereas cryptography used to be an art,
now it became a science.
When modern cryptography started,
the emphasis was on securing communication.
You know, a message was sent. you want to make sure it's secret.
You want to make sure it's not tampered with. You want to make sure it's authentic.
So our goal is to kind of encrypt this message.
So we nailed that part that's, that's working well.
Now we're dealing a lot with securing computation.
There was time where smartphones started to come out.
And later smartwatches came out.
All of a sudden we had a lot of little devices
that interact with the real world and need to do computations.
But they're very weak devices.
So a natural way to think about is,
okay, they'll ask some, the desktop
or some cloud computing or whatever,
a stronger computation device to do the work for it.
So now with abundance of weak devices
delegating computations off to a cloud computer,
there's two main challenges that come about.
First, maybe I want privacy.
I don't want to let the server know what I'm doing,
Another question, which is kind of very, very dear to my heart,
and I spent a lot of time working on it,
is exactly ensuring the integrity of the result.
How do we ensure that the result we get is actually correct?
How can we do that in a verifiable way?
So the computational heavy device that generates this computation,
we want that device not only to give the output, but also
to give kind of a succinct certificate that certifies the correctness
of this output.
In cryptography, or in computer science in general,
the way we think about proofs really evolved.
There is work from the 80s where the goal was to come up with proofs
that reveal no information beyond the validity of the statement.
And the first step to that is the definition of what's
called 'interactive proofs'.
We have a user.
He has a, like, a little smartphone. And then we have, like, a powerful server,
think of it as the cloud.
This is your prover and this is your verifier.
He's weak.
He's strong.
You want the strong cloud to do a computation for you.
So what interactive proofs gives us is two things.
First, It allows us to prove things without giving out information
beyond the validity of the statement.
How to do this with interaction?
Here's like message one, he asks question and so on, so forth.
So the power of interactive proofs comes from the fact that
these questions have..are randomized.
But the other thing interactive proofs give us
is it gives us a way to prove a statement,
in a very succinct way,
using much less communication, or much less bits.
So while interactive proofs are very advantageous
in that they allow you to hide information and they allow
for much more succinct proofs,
there are inherent disadvantages.
The main disadvantage is that an interactive proof is
not transferable.
Once you eliminate interaction, there is no real proof
that you still have the security guarantee that the interactive protocol had.
Let's say we only care about the succinctness,
the fact that the proof is short and can be efficiently verified.
You really want to have a certificate saying that this,
that, you know, indeed this is a valid transaction,
assuming you can't check it on your own.
So how do we go from here to a actual certificate?
What do we do?
We apply what's called Fiat-Shamir paradigm
or also known as Fiat-Shamir heuristic.
You can take any interactive proof
in which the verifier's messages are just random
and convert them into not interactive ones.
Ao they can essentially eliminate interactions using cryptography.
What we get by applying Fiat-Shamir
is what's called a succinct, because it's short...
non-interactive... because we eliminate interaction...
argument.
And the the acronym for this is SNARG, succint non-interactive argument.
One main place where SNARGs,
or in other words, a certificate that
certifies the correctness of the computation,
are used a lot is in the blockchain.
Today, Etherium are using SNARGS
as a way
to certify the validity
of the transactions
We're trying to simulate this arbitrarily complicated function.
G and fool distinguishers in this class F.
Therefore you need a SNARG
so that, exactly, exactly.
So, what are the biggest problems in cryptography today?
If I had to think of the new biggest problem,
one of them has to do with quantum computers.
So cryptography is based
on computational assumptions.
The security of our schemes are based
on some hardness assumptions.
We believe that it's hard, for example, to factor very, very large numbers.
These assumptions often no longer hold
once we have large scale quantum computers,
they could break our assumptions
And hence render our schemes completely insecure.
However, contrary to the narrative
about doom, I actually feel a narrative of excitement!
Of, oh, let's see what a quantum computer brings, like what capability.
We can upgrade most of our schemes to be
post-quantum secure.
We're still working on it
but you know, we've made a very large
advancement on this front.
And that's pretty exciting.