Why there is no risk because.
The city has also come and
buys from research on the campus.
You're probably right you know
it's a leadership position.
Not the right.
Rather than the American Association.
Or a very few of the women in my book.
About the record or about other research.
Of our group one.
Of the country.
The president left America
about logical society.
And other owners here's
what I posted on all the.
Number of Americans who are.
Giving up my dreams of this news lectures
and living a life of an awful Congress.
Like.
Trying to do research.
Feel.
Well known to work and want to know
the birth of the worth of Quezon is that's
part of what we'll hear
about tomorrow why don't.
You also research.
Number theory.
Would work.
For five.
Years one of three founders.
Robert.
Thank you Michael.
Thank you everyone can also
Mike can you can hear me.
OK.
So it's it's a tremendous honor
it's a real thrill to be here I'm
very pleased to to come and tell you
a little bit about some modern work and
some ancient work in cryptography so
in this talk I'm not assuming that
you know much about cryptography.
OK so.
Let me start with an ancient story so
people have been thinking about
cryptography for a long time perhaps
not squid since the Stone Age but
there are some ancient ciphers the Caesar
cipher which I'll be telling you a little
bit about in a moment and the plan for
this lecture then is to start with
some of the history of the subject and
then you know moved to this big
breakthrough in the seventy's that
introduced an entirely new field of
cryptography and public key cryptography
and so when I started thinking about
cryptography was to colleagues
in the mid ninety's this field
was only twenty years old so
it was possible to learn everything about
it in a very short period of time and
then I want to tell you a little bit about
where modern efforts are focused in this
in this field so what are the questions
that come up in cryptography so
the first is so how do I send
an encrypted message to a friend so
that implies that you have other
means of communication with
your friend you can get together by
phone in person and share a secret and
that secret is the secret to coding
in decoding and that's different
from the question of how does one send
an encrypted message to a stranger
someone with whom you have never before
had some kind of private communication
that would enable you to share some
secret piece of information how do
you prove identity without revealing
without revealing private information
and what's all this fuss about quantum
crip time quantum computers and
cryptographic products so that's some of
the things I'll end with in this lecture
OK So that is a that's an I.B.M.
fifty cubit quantum computer.
So you know the threshold for
quantum computing to start doing
computations that that can't be
done on an ordinary classical
computer is about fifty cubits So
these are exciting times and
if you go if you Google you know
quantum computer I.B.M. you'll see that
they have a whole platform devoted to
this next generation of computing.
Why is it interesting for
cryptography that that that will come.
And then so so
again when when I start started thinking
about cryptography there were many issues
that came to the fore that to some
extent are not there anymore but.
Still are to and others so first of all
you know modern public key crypto is
essential for online commerce it's what
allows you to attend your identity to
create digital signatures and you know
this all sort of took off in the early
ninety's when online commerce and the
Internet came became widely available but
when public key cryptography was
invented in the mid seventy's it
was you know it was a solution in search
of a problem it was a classic case of
fundamentals research doing something
groundbreaking before its time
so the other issues in cryptography that
were very much you know that were very
relevant to our efforts because what we
were trying to do in the mid ninety's
was was to do something practical to
invent a cryptosystem that could be read
on an eight bit processor and that did not
require the cumbersome computations that
others did but you know at that
time you know government or
government controls of
cryptography were rather extreme.
And this was a very controlled
technology and when we wanted to go and
talk to somebody in the U.K.
about this we were we were you know
talking to lawyers in advance.
So let me tell tell you a little
bit about the Caesar cipher so
this is the next this is the simplest
example of a share of a private key
cryptosystem this I don't know
do they still have secret
decoding rings they lease to be
the used to be able to send away for
something in the cereal box and
get a secret decoding ring was based on
the Caesar Safer So OK so
in this see the simple say for
you you number the letters right you're
going to work with numbers as one B.
as two etc and
you're going to shift every letter by
two So let's say that they decoding K.
that's also the coding in the decoding
key so it goes to see in B.
goes to D.
at the end Y.
goes back to aid so forth OK so
there is an example of something that's
been of a phrase that's been encrypted
with this simple shift by to Caesar cipher
you got it yet
we come back then Prime a key crypto.
We will come back from a key crypt so
this is the secret to decoding is shared
in advance right you tell your friend
the the secret decoding key is to and
she knows how to decode now.
Well so then the second question
is how secure is this a for.
Well suppose you don't suppose you know it
was the seas are safer but you don't know
how many possibilities are there really
to try how do you how many do you
have to try before you can before you can
be certain they've got twenty five right.
So we know that there's only
twenty five possibilities but
that one you know has been has been
decoded by by two I'll give you a hint.
No no and Jovis please OK.
All right let's get more complicated
more complex alphabet savors I so
we don't want to be so easy to guess
that he writes so if you've got twenty
five things to try you can try them
all and then that's it if found it so
in a poly alphabetic cipher you're going
to scramble the alphabet randomly so
you know now you make
an assignment of a letter to A and
another assignment of a letter to be and
so forth and
the secret decoding key is how long will
now you can't just say the number two
you have to make a list of
twenty five letters in order and
twenty five numbers in order to say which
one went to one and which one went to two
and now the question is well is
that easy or hard to search for so
how many possibilities would
there be well let's get some big
numbers on the screen that's about
the number of different alphabetic
scrambling that are possible to choose so
so that looks that's a lot.
Let's compare that to the age of
the universe in seconds that takes about
seventeen zero as the number of atoms
in the universe is about eighty.
And current computational security
means you've got about twenty five to
thirty two zeros after that one so
that's kind of comparison.
OK So so
let's go a little further a little deeper
into the security analysis of
these poly alphabetic ciphers.
The question that you want to ask is
instead of how many possibilities do you
have to search for is there a smarter way
is there a faster way to break this key so
here's an example of a simple
substitution cipher and an inelegant.
Transformation from
Keynote to Power Point.
So let's take a look at this we're so
your task is to decode this but
you've got going to search through all the
possibilities to do this so you're going
to try to use context and you're going to
try to use clues right you see this and
you say well this looks like it from
contacts it looks like a poem and
so that means that some of these
these these some of these.
Rows my rhyme and some of the number
the words are short and now you want to
think well if you have a very short word
what many what are the possibilities for
that short word and so this because
this leads to the frequency analysis
of letters in the English language so
if we for example still
the letter even is the most frequently
used letter and if you have a transcript
of a code you know something decoded that
sufficiently long you might go back and
say let's let's take out the letter
that occurs most frequently colony and
then start making some guesses but
you can get even more refined than that
you can look at the most frequent Di
graphs are the most frequent trigraphs and
now you can do a much more subtle
frequency letter frequency analysis and
this is a much smarter way of going
about this this this code breaking.
OK So technology advance so this is
the sort of state of the art and now we're
moving into the say twentieth century
technology advances in the question now
becomes how do you construct a
cryptosystem that simple enough to use but
complicated enough so
that it's hard to find the secret key so
if you're using an alpha poly alphabetic
cipher then you're going to have to be
careful about context and
about analysis and
about how long it really takes
to do that kind of analysis so
you use computing machines so
the first example of a computing machine
that produced cryptographic ciphers that
was widely used was the Enigma machine
which was of used in World War two and
this produced a poly alphabetic cipher and
the key was the mechanical settings
of the machine itself so the first
commercial Enigma was built in the one
nine hundred twenty so it was a commercial
machine before it was a before it was
used by the Germans in World War two.
And in the 1930's.
A less well known part of the story is
that Sri Polish cryptologist actually
reverse and
reverse engineer the Enigma machine and
represented the encryption as
a sequence of permutations so
this was the sort of starting point for
the cryptanalysis of this machine so
the key in and then Mish machine
as a starting position and
the order of the roaders and plug
positions and so there's really too many
settings to search them all
at least at that time and so.
And so this was what the famous team
in blushingly park that did the code
breaking analysis involved cryptanalysis
involved in the Enigma Machine headed by
Alan Turing did which was
to to to build a sort of
prototype of an enigma machine to
be able to set these rotors and
and keys to different positions and
they had twenty four hours to do
this because the settings would
change every twenty four hours and
this is a secret key system meaning
that these secrets are shared so
the key to the decryption was written
down in books and physically handed
from one person to another sometimes sent
by boats an intercept or whatever but.
The code breaking team blessedly part
a centrally reduced the search size
by exploiting things like I was talking
about before human error operational
shortcuts it turns out that a lot of the
messages began with nothing to report so
that was that was a good way to start so
you know if the messages are very very
short the frequency analysis of letters is
not going to do much for you so it is so
there in working with basically short
coded messages where frequency analysis
is not going to come into play they've got
to find other they've got to find other
context Laden cues and exploit the air
you know certain arrows errors and
there were certain some of the messages
began with three keys with you know
the one key types three times and so on
exploiting things like that that that and
the so this British version of this pope
Polish cryptologic bomb reduced the search
size by exploiting characteristics of the
keys and so that gives you a flavor for
what is behind some cryptanalysis
which applies much more broadly
you know you want to try to find
that back door way of getting
at what's going on without doing the brute
force search to find to find the key
OK so now we come to the mid seventy's and
picture in the upper end
corner is with defeat and
our characters now are these classic
characters in cryptography Alice Bob and
our eavesdropper Eve.
Allison Bob need to exchange a key
securely in order to encrypt and
decrypt it so they want to set up
a system where they can communicate and
coded messages and
they need to exchange a secret and
what would defeat asked was Can we
leave out the part where Alice and
Bob meet in private to exchange
the secret key that was they wanted to
create that possibility and this is
what required a fundamentally new idea
so this was the result of this was
what what we what is now known
as defeat Helman key exchange so our
public information is a prime number P.
and some other number G.
So a prime number as you recall is
a number divisible by itself and
one and we you know and so
we can so we have this so
here's the mathematical protocol for
this we're going to secretly pick another
number Alice secretly picks another
number A and then writes down G.
today maad meaning that she takes G.
to the egg and divides by P.
as many times as she can and
then gives out the remainder that's G.
to the a mud P.
Bob secretly picks another number B.
and gives out to the B.
my P.
to Alice but both of them and
so and so this and
both of them can can compute the same
quantity because Alice can take Bob G.
to the be maad P.
and raise it to the eighth
power because she knows a.
But it can take you to A and raise it
in the B.'s power because he knows B.
nobody else can compute
quantity except ours and by.
The quantity that they can compute
from looking at those two things is G.
to that A plus B.
the product of those so this is like the
equivalent of walking into a room rate and
shouting something and somebody else and
somebody else shouting it semed
sending back to you and each of you
walking away with a cigarette that nobody
else knows that's that's key exchange
So what if you know how men were actually
interested in was something that
they defined in a very famous paper
called public key cryptography which
involves functions like this that are that
you can that are easy to compute but
are hard to reverse but they didn't
actually find an example of this even
though they found this just this function
that had this interesting properties they
did not see how to turn this into
a public key crypt US system
just to show you how random that that can
be that that discrete logarithms problem
could could be if you're computing six
hundred twenty seven and you're raising
it to the AIs power and you're dividing
it by nine hundred forty one and then
giving out the remainder the remainder
looks pretty randomly distributed
OK So public key cryptography was invented
and this really famous paper defi in
Helman published in one thousand
nine hundred seventy six.
And it began with this sentence
we stand today on the brink
of a revolution in cryptography and
if you read anything about defeat.
He was on a mission in the mid seventy's
to create secure to create secure.
Coding and decoding that was
available to the public to the masses
his mission was to make something that
that ordinary individual could use and so
the use of the word revolution there is
I think I think meant in two ways I mean
on the one hand these ideas were more
mathematically revolutionary but they
were also it was also about a revolution
in personal liberty and privacy.
So he invented they invented.
The concept you know and so it's really
fascinating story I think I'm going to
read visor to it too to take a look at
his son and some stories about his later
years on this pilgrimage across the
country to try to figure out how to create
this publicly criticized out of you know
how to capture the notion of a public key
encryption system and then did up in
California where he met Marty Hellman
working at Stanford they invented
the concept of a public key
cryptosystem they describe what
a digital signature was and
they gave an algorithm for
secure a public key exchange but
they they could not find examples
of a public here cryptosystem So
the problem that they were trying
to solve was how do you create
secure communication over
an insecure channel between two
people who have never met or
shared a secret and so
what they gave was a recipe for
what was needed to solve this problem.
So back to the government controls so
later you know the very first
example of a public key
cryptosystem came only two years
later after this paper and that was
that was the Revestive should be aware and
Edelman paper this was the first publicly
disseminated solution to the problem
that I just stated actually the R.S.A.
algorithm had been discovered years
earlier in British intelligence but
we didn't we will know that for
another doc for us for decades.
And so.
The export of cryptography
at this point in time and
up until and through the ninety's.
You know was controlled as a munition So
for example that T.
that T.
shirt contains a machine readable
barcode and somebody wearing that T.
shirt with that the machine
readable barcode for the R.S.A.
algorithm could not get on a plane and
fly to a foreign country likewise
that Coke can with its machine readable
barcode is controlled as a miniature it's
it's as controlled as a bomb All right so
let's go back to the mathematics of public
key encryption What did what did defeat in
Helmand describe so I think the key
ingredients are you need a function
called a one way function that is
easy to compute but hard to reverse
hard meaning there's too
many possibilities to search
so in this context the input
is your message and
the output is your encrypted message OK so
if it's too hard to find it how does
anybody decrypt it well I was the intended
recipient decrypt it while this is
the the second key ingredient is not
simply enough to find this function this
function you have to also find a trapdoor
some secret piece of information that
nobody can discover just by looking around
this secret private key and send
the person in possession of that trap door
that's what permits decryption So
in other words the general set up and
this is what was defined in
the defeat Helen paper the general
set up was the following say
let's say secrets are read and
what Eve see is what everybody
sees as an eavesdropper is green
We have our mission Bob and Alice is in
possession of a trapdoor only she sees
and also is in possession of a public key
some some number that everybody can see
now Bob wants to encrypt
am using Alice's public so
he takes his message which is a number and
combines it with her public key which
is another number using an algorithm
that everybody knows it's not
a proprietary algorithm everybody
understands how it works.
So producing therefore there by
the encryption of them and and
then sense in corruption in them to
across an insecurity channel to Alice who
then uses this trapdoor to reverse
the encryption function and
then the question is What
are the examples of such things OK so
let's just first look at our essay
which is probably familiar to
many people in the audience but
let's let's go through it anyway so
in our essay we have a one way function.
Is.
I'll come back to this problem
in a moment actually R.S.A.
does not use this as a one way function
nobody's ever found this particular
nobody's ever found a trap door for
this particular one way function R.S.A.
uses something there's a little more
complicated that that has this one way
function lurking in the background but
this is the basic hard problem in R.S.A.
multiplying two big prime numbers
together OK that's the problem
the hard problem in other words it's not
hard to take two large prime numbers and
multiply them together what's hard is
looking at a number which you know is
a product of two primes and
saying what are the prime factors so
finding the factors of a large product
of primes is hard in the sense that
the current best algorithms are subjects
been and shal and the number of beds
that's the number field method so
here is an illustration
what are the prime factors not going to
wait for you to guess there they are.
OK So R.S.A. was the first practical
public key crypt system and
then there was a lot of effort
to find other examples of such
things and many of these were
somehow doomed to failure.
The factoring problem as I
mentioned has no known trapdoor but
R S N A found this related one
way function which does possess
a trap door and it's really important
campy understand how important it is that
everybody knows the protocol it's not that
the protocol is hid I mean you know for
a long time you know especially when when
we were involved in cryptography and
talking to two to companies and people
about security we'd find yeah this is
secure it's a proprietary algorithm you
know nothing is secure because you try
to keep our work secret the idea stick
is to create something that secure and
everybody understands how it works so
as I said there you know the of right if
things were tried over the years to to
to generate new new methods of.
New Public encrypted systems.
So underlying every public key
cryptosystem is some hard problem and
what's compelling is to base a public key
cryptosystem on a problem that's that's
hard in the sense that everybody agrees
that it's hard in the sense of complexity
theory So for example for
a long time there was so for a while there
was great hope and promise in trying to
build a cryptosystem around the following.
Hard Problem the subset some problem so
you're given.
A large basket full of integers and
a Suburban and
a sum of some of these integers and then
the question is if you just given the sum
and even if you know what the basket
of images is find the sound so so.
Casey's based on the subset some problems
were called knapsacks systems and
they were not they were not successful
ultimately because the new ones that were
efficient in the sense they could be
practically used turned out to be broken
you know turned out to be too to have
to be breakable at the at the size and
the things that broke knapsacks systems
were lattice based methods which I am
going to come back to when I talked about
some lot of space matters in a moment
after R.S.A. a version of the defeat
Helman discrete log problem was and was
done in the context of a loop to Curves
This was invented simultaneously and
independently by code blitz and Miller and
that's that proved to be secure over time.
And and then and
other developments PETER Sure an MIT
in the early ninety's found an.
Algorithm a quantum algorithm for
solving a certain a billion hidden
subset some problem which could solve
all of these problems the defeat
Helman problem R.S.A.
bridge in other words breaking
public key crypt as systems founded on
the hardness of these problems so so
right now this there's some you know so
we introduces some uncertainty into
the length of that these systems will last
assuming that you know if there's any sort
of advances in quantum computing at that
time quantum computing was so far away
that this algorithm was a mere curiosity.
So then now I want to tell you a little
bit about so a lot of problem a lot of
space cryptography you know it was prior
to say the mid ninety's when I tried to
work you know invented their famous worst
case the average case lattice system which
was a very theoretical and beautiful
construction and we got into this this.
Area at the same time lattices had been
used primarily in cryptanalysis and
so there hadn't been much use
of lattice problems in the area.
Of publicly crypto So
the first scheme that was
invented that was both based
on a lattice and efficient was
the untrue public key cryptosystem which
was invented by followed some some
ideas of John Hostin and
brought in to two colleagues myself and
Joe Silberman to two to do
the cryptanalysis and the and
flesh out these ideas this was presented
at crypto ninety six so this was pretty
These ideas were presented at this what's
called a rump session of this conference
this is a major crypt conference there's
several of them that happen every year and
they have this this thing called a rump
session where they give you two minutes or
four minutes or six minutes to
get up there and say here's my
here's my idea what you think you know we
were pretty naive we know this was that
this was the computer science culture that
we were sort of coming into without really
understanding you know the way
the best way to communicate and
Hostin got up there and talked about
the new this great new ideas and and
I had four minutes to do this and
gave out a paper and
Shamir was in the audience and
took the paper and
basically their reaction was
Well it was not good it was.
There is like like we do you think you're
doing like throwing out this idea.
But we were trying to talk like
mathematicians talk to what end.
I would say What do you think of this idea
let's let's you know let's all work on
this together but anyway so so
before ninety six as they said lattices
had only appeared in cryptanalysis and
their constructive use was really regarded
with suspicion if not outright disbelief
and before we even managed to
get our paper published on it so
mere congressmen attention Maire published
in Europe ninety seven something called
lattice attacks against entry win which
they claim that this that the crypt
a system would be demolished with
with minor technical advances and
Lattice algorithms so
we were off to a good start there.
So I mean it was compelling to do this
because this a problem is based on another
N.P. hard problem which is the problem
of you know of a closeness factor or
shortness factor in the last which I want
to now sort of tell you a little bit about
so the algorithm itself is published in
ninety eight it did finally prove to be
you know finally convinced finally people
were convinced that it was secure after
some decade of of work and some and
some mistakes that we made
in certain algorithms that we tried our
digital signature scheme that we first
tried was was was broken to the to
the glee of most of the people
in the computer science community around
us but you know after about a decade you
know we the parameters were solidified the
whole of the scheme itself is as secure.
So let me just tell you what what
a lattice is in case you're don't know so
a lattice is an array of points
a regular array of points and so
what I've drawn is a lattice
in two dimensions and
a lattice is generated in two
dimensions by a couple two
arrows two vectors meaning that you can
take those two vectors and generate every
point in the lattice by simply using these
arrows to walk around the lattice OK so
you walk forward and then you can also
walk backward another which you can cover
every single point in this way by walking
around using these arrows what's not so
obvious is that you can do the same
with those arrows if you want
to return to a point close to the origin
you have to walk pretty far out but but
you can get back so a lot is has lots
of different generating vectors or
these are called bases and each of
these bases determines a fundamental
domain of the same area called
the determinant of the lattice and
that's basically you change
basis from one to another by
multiplying by a matrix
of determining one so
which the hard problem
associated with lattices.
Well one is the closest factor problem
you pick a random point in space and
you want to find the closest point in the
lattice well how hard can this be really.
You know if there's your
random point in space.
And you use your arrows to draw the
fundamental domain around that point and
then once you have your fundamental
domain around that point you just
see which one of those vertices are the
closest to the point and you're done.
And that's all possible if you have those
good arrows to work with if you were
working with the long arrows that a shared
your need through that fundamental domain
those for to seize would not be
anywhere near this point and so
this closes vector problem is also very
intimately related to another and P.
hard problem which is finding which
is the shortest factor problem
which is how do you find in
a lattice the shortest factor and
it's really hard to see why this is a hard
problem in two dimensions and in fact it's
not a hard problem in two dimensions it's
an algorithm that goes back to go for
solving this but it's really hard
thousand mentions and that's where and
who sits that's where that's where we
work so enter uses this hard problem in
enough in a particularly efficient way so
that the one thousand backers
that form the lattice in one thousand
dimensions are all generated
by their were Taishan of a single factor
and of course that's what aroused
suspicion among people that looked at this
in the first because there's a structure
in there sort of looks like there's
structure to be exploited in some way.
So the closest factor problem is an N.P.
hard problem and
there are Al Gore themselves fine
short doctors and lattices and
I'm proud to say I actually work very
well in low dimensions and we spend a lot
of time from nineteen you know
ninety's six to use it for
the next ten years doing computer
experiments to try to actually get
a handle on how how how well these
outer them to run because in slow
dimensions these algorithms work.
Better than they are predicted
to in theory in practice but
then at some point they
just stop working and
nevertheless we have to use these
algorithms to to get some kind of tracking
of our security parameters we have to see
if we could extend this out you know to to
all these dimensions what kind of security
we are we are we achieving how and
how long with ideally would we would would
this take to break so I just want to throw
a picture up of a dent just because I
look so beautiful to me that that Q.
is some prime number so everything
everything is determined by the simple
number up there age zero
age one through eight and
that's the public that's the public
even and to last a private key.
Is a base is a matrix where the rows
are much shorter there's those ages
are big the rows are much shorter so
the private key is a good basis
the public key is a bad basis and
this is an example of
something that has come over the years to
be known as ideas or are ideal lattices
OK So let me move to some
more modern developments and
Lattice based crypto which is related
to two things that are involved and
two so in twenty fifteen.
Post quantum crypto became rather urgent
for government and financial institutions
was about that was a big There was some
turning point where government and
financial institutions believe the quantum
quantum computing well if not around
the corner was a very real possibility
in the next fifteen to twenty years.
So why do financial institutions and
governments care about something that's
coming up in fifteen to twenty years
because they are protecting information
now with encryption that can be
broken in fifteen to twenty years and
they and there's information that they
want to protect for longer than that so so
anything you encrypt now with with R.S.A.
or
elliptic curves or anything I mean can be
Dick will be will be available to decrypt
ever if there's quantum computing
technology a lot of space crypto
like Andrew continues to withstand
the power post quantum computing So
those two lattice problems
are associated another what's called
a hidden subset I hadn't
subgroup problem but
it's not the one that Peter sure solved
it's a different one which has not
been which is not theirs for
which there is no quantum algorithm and
the centrally nobody has found a way
to make the problem of finding
the closest factor or the shortest
factor in a lattice paralyze a ball
and entry like systems are now being used
in homomorphic encryption schemes to maybe
I can explain a little bit of that
because of because now I mean used to be
a curiosity where you know run run we've
asked in one nine hundred seventy nine
asked a question that was very theoretical
now it has practical importance
OK So morphic encrypts so
in homework fic encryption The problem
is the following We want to compute
an encrypted data in the cloud
without without decrypting
it first right we want to be able to put
information in the cloud make it but
dated there make it readily available to
people to compute with without without
without giving them the power to teach to
decrypt it so like I said I mean this was
a Couldn't whether says such a thing
was possible was asked by Rev vast in
one nine hundred seventy nine before there
was cloud computing in any real practical
application of the US And so what does
it mean to to to build a computer on
this without encrypt thing as well we
need those we need to be able to take
the sum or
the product of the encryptions and
have that be the same as taking the sum
of the products of the decryption and
then encrypt in them in other words this
we need this operation of decryption or
encryption to commute with some
products with the computations so
we need a sort of we so that and
that's that was what reversed asked in one
thousand nine hundred ninety nine is there
is there a criticism that that committee
where the operations of encryption and
decryption commute with the rain
operations of multiplication and addition.
And this one took a long time to solve
this Craig gentry in two thousand and
nine gave the first
theoretical example of this and
one of the things I really loved about
gentry solution is that I had this sort of
self-referential quality to reminded me
of girdles theorem in computer ability.
So but it was terrible in the sense
that it showed that there existed
there existed such a.
Homomorphic encryption system and
his basic idea was well
you know if you could if you could get
a system that was partially home or sickly
encrypted like if you could interchange
this encryption operation was sum and
product just a few times and nuff times so
that you could really encrypt and
start over again then you can make it
fully a logic encryption but that ability
to really encrypt and to start over
again means that the crypt a system must
have this homomorphic capability on its
own encryption circuit that's the sort of
self-referential part of it anyway it was
a beautiful theoretical construction but
there's no practical solution to this
problem really there are partial
homomorphic encryption schemes and how
you know how practical that is depends on
how far you can go with these computations
and how far you need to go and so
that's an area of research that
really requires ideas were way
beyond lattice ideas and other things that
people have use one of the things that
gentry did was you know he used this lot
of space systems to get a handle on this
theoretical construction so
there's practical there's there's So
this area of current research which
is both it both very applied and
very very theoretical and very interesting
really require some some new ideas.
So when will we have a quantum
computing capability well so
in the last and the last few years we've
seen we've seen various estimates people
are taking you know making an estimate
taking a stand on this Google says
Google says that they expect nearly
useful quantum computers by twenty
twenty Well OK that I think that the birds
in your definition of nearly useful but.
Microsoft predicts quantum computers by
twenty twenty five financial institutions
as they sat are thinking now about how to
protect information for several decades
the National Institute of Standards
technologist has issued a call for
proposals for post quantum cryptography so
it's like Send us your best ideas.
So.
So Andrew so when we started this work
started this work in can progress.
We really wanted to do something
practical and so we can't really prove
security of entry because it's not
based on a worst case lattice problem
it's based on a certain structure of
lattice problems that you know for
a variety of reasons we felt you know
it was a secure but you know it really
what we really were interested in was some
practical applications of this we wanted
to replace R.S.A. and E.C.C. because
these were computationally intensive and
we were in visioning you know reader and
tag applications and so
so you know we went full steam ahead and
couldn't get anybody else interested in
this technology so we started our own
company and we incorporated in one
thousand nine hundred nine with
some initial investment by Sony and
then and
then we raised venture capital and and
so it was this was the late ninety's
early two thousand the dot com
bubble had not quite burst and
it was quite quite a a wild ride and so
that's the picture I generally show and I
talk about about you know our experiences
with this with this company which in
the end was actually so it was so
we developed a number of things in
this company was things we started
in the mid ninety's was working with
vehicle to vehicle communications and
that was for of a have we were a little
bit ahead of the curve there showed Now
that's actually a very integral part of
what this company is doing and considering
it was the company was acquired in two
thousand and nine by security innovation
Incorporated which is another privately
held company when I say acquired I don't
mean any cash changed hands where we're
talking you know the usual dream lives on
the equity in the company and a bit and
very recently has the company
grew security innovation grew and
we decided to go in
a different direction and
just sort of split itself into again and
so now I know a new company that.
That that has to algorithms and
patents and
is now specializing in
the ubiquitous in encrypt and
for Internet of Things and
vehicle to vehicle and so forth and
post quantum cations has spun
off called onboard security and
with that I'm from Phil in my obligation
to my university to tell you my financial
interests in another
privately held at thirty.
But all I can say is this is the slowest
get rich quick scheme I've ever seen and.
Anyway but one of the things
that I think is really my.
Unless about this this work that I sort of
got into Syria you know serendipitously
you know when my colleague
came to me one day and
asked me a question in probability and
I did I was able to answer is there a why
are you thinking about that turned out
that was authentication digital signatures
so and so at that time as I said it was
possible to learn quite a bit about public
key cryptography just about everything
you'd want to know if you can learn them
in a couple of months because the subject
was was so young so the marvelous thing
about it is that there's really a lot of
theoretical work that's going hand in hand
with these applications which is which
is really fascinating and it's it's it's
always wonderful when you find a subject
like this but cryptography really still is
a subject like this there are so few
actual ideas that are being used in this
field there must be there must be room for
so many more things happening that.
I recommend I recommend the subject in
the field too to people who are looking to
think about things new things and
new ways to apply your ideas so thank you.
To.
The I think I think that most of the
crypto currencies and certainly Bitcoin
have no car not quantum resistent there's
there's people are starting to think
about how to how to do quantum pre you
know resistant block chains now but
I don't I think that's also very much in
its infancy so you know when a quantum
computer comes around and you know that
person who privately built that can now.
Get hacked through but
COHEN Well there you go.
Well you know
what we found you know
was that what once was so
the first thing we found was that
people don't care about security and
then when not started to change when
that started to change people were so
embedded you know in these systems that
changing something was amiss you know sort
of monumental effort and had to be really
worth it and by the time you know but
it time our system became
you know credible and
people believed it was secure we were
sort of past this point where were
you know processing power of computers
was you know were there you know we
were running up against the fact that
we were bringing something that was
that was compelling enough but
now I think the compelling story is is.
Is post quantum resistance because
there aren't there aren't really other
fish and cryptosystems that
have been studied for so
long that also have this property
I mean obviously NIST and
other government agencies don't want
it to be the only one we however.
Don't mind.
So.
I'm sorry there's no proof
I mean there's no nobody's going you know
made of no nobody's proved the latter
space that the closest structure probably
a lot of space systems that have this.
You know the rest on this
hard problem are forever
going to be secure but you know when
you're looking at practical cryptography
you don't ever have such proofs
I mean the R.S.A. the R.S.A.
algorithm as I said is based on
the hard problem of factoring.
It's not provably equivalent to
that nobody's ever proven that
that that that if you can't break R.S.A.
unless you bring you know you know
break the factoring problem and
likewise you know in this you know
in this particular system Andrew
it's not pretty even provably
equivalent to the closest actor or
shortest doctor in a lattice problem
there might be another way to find and
that's the tricky thing about practical
cryptography and so there are these other
as a alluded to theoretical constructions
that I didn't talk too much about where
there are sort of proofs of you know
that this is you know the system.
Is based you know it has a worst
case average case reduction so
there are other theoretical
constructions out there but
when you when you move into
something that there is a fish and.
There aren't really proofs.
So.
What was.
The one.
OK so first Congress messenger merest sot
that last algorithm is one of
the point where they would this would.
Break Andrew and break a lot of space and
a system that relied on the security would
would fall apart within a few years with
a few advances in lot of space systems and
and so I mean yeah I mean they
have had a strong belief in their
ability to make L.O.L. and its variants
more more efficient which has not
proven to be the case you know it really
looks you know when you did experiments or
really looks exponential so you know.
They are not really an acronym in the
sense that you know that one point there
is this joke that it might be
number theorists are we said.
It can't be because that's
copyright then I'm one video.
Maybe number theory research you know but
we don't we don't even worry about
what it stands for it's just entry.
Sorry Yes Good question thanks so
much for spending your time and such
a complete history I hope that you could
provide us with some context because some
of the time truths that you mention ninety
six years and I was around the view.
That what the.
Pentagon Papers and
all those things might have been a.
Community of distrust
government to some extent and
that's to ninety's which was the end
of the Cold War when I understand.
Through the seventy's a lot of.
Things taking place between you and it is
so as you look forward into the future.
What are some things
that you would speculate.
The worst things that you mentioned
before she doesn't seem to change much.
But she's looking to the future from a
historical context would you in the future
do you think security will just become
does not look Security will be more.
Like her it just happens.
To be looking.
So please people you know go on.
This is one of the hardest
questions I've ever been.
So.
What happened I guess in the ninety's was
that the government really thought it
could control access to information and
and there was a lot of.
There's a lot of that and that that
actually just cannot happen I mean there's
you know the they really thought that they
could control access to two algorithms and
and I think that one of the things that
really you know what the main thing that
happened was it was the Internet I
mean the communication became rather
you know tools for communication and
fast communication became ubiquitous
and she was the future holds
I you know in terms of
in terms of you know security and privacy
that mean to now I mean you know I.
I'm not really sure I'm not really sure
how to answer that I just especially.
In the current political climate I just
it feels like it's hard to know so.
Well the answer is really no I cannot
it's because not and that's that's
my feeling is I'm not really an expert in
quantum computing either I'm about as X.
bird as Justin Trudeau and
you know I can give the answer
about you know classical computers work
on with bit on off switch and bits and
zeros and ones and quantum computers use
the principles of quantum mechanics but
you know and I've even studied you know
the short shorts algorithm to some extent
to try to understand it but the basic
idea is that you know you know have
the ability you know the hope
is that you know you can be able
to perform exponentially many operations
in a sort of simultaneous way and then do
a measurement which allows you to collapse
it and get some information out and
I really you know I think a very serious
understanding of this takes a much
much more of an expert appeared to to to
say more to explain it so sorry we can.
Do so we're.
Going.
To.