Dear viewer, these subtitles were generated by a machine via the service Trint and therefore are (very) buggy. If you are capable, please help us to create good quality subtitles: https://c3subtitles.de/talk/838 Thanks!
Oh, OK.
And with that, I'll leave you with the
experts, please.
Well, it comes down, Wolf.
A lot of applause.
It's like my gun. Oh, there we go.
Thank you all for being here.
And I especially appreciate your
fortitude in coming to a heavy duty
mass talk at 10-15 p.m.
on day number two.
So we are going to
talk about how to use lattices in
cryptography.
And I encourage you, because we're going
to be doing a lot of coding in this talk.
We have put all of the code in our slides
online at this fine Web site.
So if you want to pull out your laptops
and play along with us during the talk
and make sure that everything works, you
are welcome to do that right now so you
can copy paste all of our code samples
into Sage as we're going along.
So here's some
headlines about cryptography.
Cryptography appears a lot in the news
lately. And every once in a while there's
an article that is not about bitcoin or
cryptocurrency or block chains.
So here's a couple examples.
And all of these have something
in common. These articles, popularization
of cryptography, research,
and what these have in common is
lattices.
So this is the topic of our
talk for you today.
Why are people talking about lattices and
cryptography?
So there's kind of two things
that you can do with lattices and crypto.
Number one, we can break stuff
which is super fun.
So there's, you know, basically every
kind of crypto that you can think of.
There's probably some way to break it
using lattices, including,
you know, both like old
public key crypto systems, long broken
public kicker's crypto systems and crypto
systems that we're still using today and
tomorrow's crypto systems.
So the other thing that you can do with
lattices is make cryptography,
including sort of futuristic things like
post quantum cryptography, fully humming
morphic encryption.
Even people have tried to do things like
indistinguishably obfuscation, but maybe
that was a bad idea.
We'll find out in 20 years.
So, OK,
so this talk is going to sort of
happen in multiple parts.
We're going to break stuff.
We're going to make stuff. So if you get
lost in one part, maybe you can catch up
in another piece.
So what does a lattice.
This is not a lattice.
This is a lettuce.
OK, I apologize to all the non-native
English speakers in the room and
our translators.
Let us let us not let us
know.
OK.
So for the purposes of this talk, there
actually multiple kinds of lattices in
mathematics, the kind that we're going to
talk about is think of it as a repeating
grid of points in n dimensional space.
So we have like n dimensional Euclidean
space. Hopefully you can imagine in
dimensions and think of a repeating grid
of points.
Look something like this in two
dimensions.
This is a lattice of lettuces.
I just put this into a mess with
the translators.
So I apologize
to our fine translators.
But slightly more seriously,
a you can think of I mean, we're going
to have sort of abstract looking points,
but you can think of the points as
actually representing MASH met
mathematical things like
polynomials. So later on in the
talk, we're going to see lattices of
polynomials. So you can give each lattice
point as representing some kind of
mathematical object here, a lettuce
or, you know, maybe something else.
All right,
then.
All these points, you need to have some
structure in place.
So, for instance, instead of
taking a stand which pictures let
us all over the place, we can also
take these two vectors.
So imagine this over here.
There's a zero point.
And then from there, we have these two
vectors going out, two lines,
and then these are chosen
so that every other dot
you can be reached with one of those
combinations.
So just to get up here, you take a twice
to get over here.
You take it twice and subtract this one.
So every dot can be, which was those
two things.
Now, these are not unique.
This is also the green ones.
Also former Baz's or the
blue ones, like very long and
stretch.
But again, any combinations of be three
and before can reach all
the dots.
When you think of when you learned about
quartet systems, then you learned about,
say, the real numbers and you had like X
Y coordinates.
Now here, the difference is that we only
allow integer multiples
only and tire copies of this.
There is nothing between those dots.
You can take half of B three
if you take half of B three.
You land here.
There's nothingness.
It's like a game plan.
You can't stop somewhere.
You can only hope to the next dot.
And if you want to describe these was
more math, then we go for coordinate
systems. So, for instance, this
be one vector is something like
two over and
three or four up.
So then you would have this one is two.
And this one is three point four.
And then to store those.
We put them in the top row.
This is the first coordinate.
There's a second coordinate.
And for the second vector, the same thing
now.
Two dimensions is very small.
But when you look at something like this.
You get this little bit of a tunnel
vision that is somewhere in origin and
you can see it goes up to three
dimensions.
Now, incorrupt, we gonna use those with a
few hundred up to a thousand dimensions.
We're not going to do this with pictures.
I think we will be totally fine with
having coordinates for those and then
does the top row going to have the
thousand entries and they're gonna
be towers and thousand such lines
so each other vector will have its
own line.
So mathematically, there's no problem
going beyond four images.
We'll go back to dimensioned to.
All right, I
understand what a Latisse is.
Why do we care about lattices?
What are we going to do with lattices?
So for this talk, most of what we're
going to do with lattices is
find short vectors in them.
So we saw that we could have multiple
bases for the same lattice.
Some of them might be have super long
vectors, but we're interested
in finding pretty short vectors
in some lattice, given an arbitrary
description of the lattice.
So this is called the shortest vector
problem. And the problem is
generally given some description of a
lattice find the shortest vector.
So there are a few ways that you can try
to compute this.
This problem turns out to be pretty hard
to solve. Exactly.
So the fastest algorithms that we have
to compute the shortest vector.
Exactly in a lattice run,
an exponential time in the dimension.
So two to the end in Dimension N.
But you can compute an approximation
for the shortest vector.
So something that's kind of short but not
exactly the shortest vector in polynomial
time, which is fast enough for the
purposes of computer science.
So you have that
option also. So hard to solve.
Exactly. Easy to solve approximately.
That's kind of our setup.
And in this talk, the specific
algorithm that we'll be using to compute
approximate short vectors is
called the LLN algorithm, which was named
after its inventors, Leinster, Leinster,
Lobos.
So the input to this algorithm is some
gladis basis and dimensions.
The output is a pretty short vector in
the lattice. We're pretty short.
Means that the length of that vector,
if you in sort of Euclidean length,
is something exponential
in the dimension times the length of the
actual shortest vector.
This doesn't look super impressive.
It turns out to be non-trivial to find.
And it is good
enough for our purposes in breaking a lot
of cryptography. So that's the part that
we're excited about.
So LLN algorithm.
All right.
The examples with Sage,
which is a lot like Python, plus
a bunch of functions that you might
not have seen before, which is kind of
like Python itself as Python with
a lot of functions you might not have
seen before.
Some of them are pretty obvious and the
same as in Python, like your type two
times three, it tells you six.
Whoops. Wrong way.
If you do two and then a carrot
symbol, which is like shift six for
the Americans, or maybe it's two left to
one for the Germans.
That is not exclusive.
That's exponentiation.
Which people who type mathematics in the
tech language or late tech, they
use this exponentiation.
So two to the three is eight.
There's all sorts of functions which do
what you might expect, like if you factor
an integer or a polynomial than X
squared, minus nine is X plus three times
X minus three. Or you can ask for roots
of a polynomial X squared minus nine
has minus three and three.
What are those ones doing there.
That's the power, like
the multiplicity, the number of times
that a root shows up.
So if you factored X squared,
it would tell you that, well, that's X
minus zero with multiplicity, too.
And there's various other functions.
It gets more and more complicated.
There's some useful functions like
generating random primes.
And this is generating Weld's like Rand
range, but gives you a random prime
number.
And it goes up to two to the 512.
Again, that exponentiation it's two to
the 512 power.
And then if you have two prime numbers
like this, P and Q, you could multiply
them together, get a big number N and
hey, suddenly we're doing the RSA crypto
system and then choose some exponent for
RSA like Exponent three.
And then you can encrypt a message, you
can do some message which is an
integer modulo N and compute Powell.
Now that actually is a python function.
You can use Pough in Python itself, the
random prime. You need sage or you have
to implement that itself.
Implement it yourself. That's all you can
do in in straight
up python. And that gives you message to
the power E modulo N and
that's your cipher text, for instance,
the third power of a message modulo and
and then there's some slightly more
complicated procedure for figuring out
the exponent that you need to decrypt
using the same PÃ¥l function again.
Lots of warnings that we should be giving
about how to implement RSA don't to
do exactly this for RSA.
Maybe some of the warnings you'll
actually see later from some attacks, but
there's many, many more warnings.
If you're actually going to do a crypto
library, then you should do something
which has a lot more protections
than what we're showing you. We're just
gonna do the kind of math details and
not get into all sorts of other attacks
that are out there.
So the thing that we
want to get from the previous slide is
that we care somehow about factoring.
So we want RSA to be secure so
that we have a secure Internet, which
means that it should be hard to factor
those modules in.
So how hard is factoring?
I don't know. It seems pretty hard.
Let's build the Internet.
Sounds good.
And so for this next section,
we're going to talk about how to factor
with lettuces.
So we care about factoring for the
purposes of proving the security of RSA
or at least establishing the security of
RSA. So how hard is factoring.
Really?
Some of you may have may have seen our
talk a few years ago.
All right. Let's explore is kind of the
parameter space of this problem.
Now, I have say our modules
end which have colored purple and say two
primes, P and Q and P times Q equals.
And that's kind of the setup.
So if I give you P times Q and N
and P and Q and N, then
you know how to factor in because I gave
you the factors. So then the problem
is easy. Right. Okay.
We're good with that part.
All right. If I give you an
and one of the factors P then
you can still factor N because you can
use division to get Q then you're done.
Right. So still we're
in good territory.
If I give you neither of the factors
P and Q, but I just give you N,
then I hope this problem is hard because
otherwise the Internet is broken.
It currently sort of the best algorithm
that we have for factoring in this case
is sub exponential time in
the length of the modulus n
current record. Nobody's factored the RSA
10 24 challenge in public yet.
Maybe the NSA is factored numbers of this
size. I don't know if you're
super excited about this topic.
You can see our talk at twenty nine C
three for more information.
So this is somewhat hard.
Let's do something a little bit more
exciting.
What if I give you something like this,
like half the bits of P and half the bits
of Q. If they happen to be arranged like
this, this turns out to be really easy.
You can sort of divide and like rearrange
a couple of bits and then just
recover both P and Q.
It's a little surprising, but there's no
like real situation in which you can
imagine like this being relevant to your
daily life.
Let's make this a little bit more
exciting. What about this?
This easier heart like this is like
halfway in between something that's easy
and halfway between the something that's
hard.
Where do we stand?
This is more exciting.
All right.
So turns out that this with
this kind of information, if I give you
half of the bits of pea like, say, the
most significant half of bits of pea,
although it doesn't really matter which
half of it's the pea I give you, then you
can factor. And in polynomial time,
even though like the remaining half of
bits of pea that you don't know is like
gigantic, you can't brute force that.
So we're doing something super
interesting here.
And it turns out that the way that you do
this is with lattices, hence the
subject of our talk.
So let's see how this works.
So this is a little cryptographic magic
trick. This is all sage code
that you guys can run.
So if you don't believe me that this
works, you can totally run this yourself
and verify that it works.
So I'm going to do my little magic trick
here. So I generate 512
bit primes, P and Q totally legitimate.
Nothing up my sleeve.
These are like honest jennet, like, you
know, primes, whatever sage does
to generate prime.
I multiply them together to get an
the product.
And then I generate this value a which
is like most of
the bits of P except for like the least
significant eighty bits.
OK. So if I like look
at this value a
in hexadecimal, like there's a
bunch of zeros in the least significant
bits because I've deleted the least
compute bits.
So I learn most of a.
But like not all of it.
And eighty six bits is enough that I
definitely shouldn't be able to brute
force this on my laptop and I wouldn't
even be able to run like a square root
thing on my laptop in a
sort of feasible time to get this done in
time for the talk. OK, so
what I want to do is recover
my factorization of
the RSA modules end here with only
this partial information about the key,
not the full key.
So how do I do that?
I construct a matrix.
So we talked about matrices and lattices
being somehow connected.
And my matrix contains
mice value A, which is like
the bits of P that I am allowed
to know and and and some other
things that are also public.
And then I run my magic L-A algorithm on
it.
OK. So here comes the magic
trick.
Now I take the output of the LLN
algorithm.
I construct a polynomial somehow
from the vector that I got from l l
l and if I compute the roots of
that polynomial, I magically
recovered p.
Magic, the rabbit
appeared again. I don't know.
I don't know where it came from.
What just happened?
You guys, I hope you're confused because
you should be confused, but
I hope you believe this works like
somehow magic has happened and I have
factored very efficiently.
OK.
So this is an example
of what's called coppersmiths method.
So Coppersmith is one of the greatest
crypto analysts of the 20th century and
probably one of the greatest crypto
analysts of the 21st century, except we
don't really know because he works for
the U.S. government now.
But hopefully we'll find out in 50 years.
I'm super excited.
So.
Anyway, I mean, like, yeah, his all of
his work is amazing, Ellie, so what
the stuff we know about in public.
So and actually like
his original paper from 1996 that
describes sort of the generalization of
this method is pretty hard to read.
So what I'm going to present is kind of a
simplification, which is due to how grave
Grahame's several years later.
But of course, the simplification still
has multiple steps in. It looks very
confusing. So that's sort of the state
of cryptanalysis.
So I will explain what's going on in
English. And
this will probably still look like magic.
So what I just did in English, step
by step, is I wrote down some
polynomial.
In this case, it's a linear polynomial.
A plus X X is gonna be my unknown.
That has a pretty small root mod P, I
don't even know P.
I know that P divides n I know n but I
don't know P.
But somehow this fact still helps me.
I constructed a lattice basis from the
coefficients of some polynomials that I
could just write down that I knew that
varnished mod p if I evaluated them and
ah you know
a plus X plus X squared.
And sounds good.
Throw them in a lot of spaces.
Run L l on this lattice basis it gives me
a short vector and then I turn that
short vector into parliament polynomial
again and then compute its roots.
And magically the piece of the prime
that I was looking for is one
of the roots of this polynomial.
And I can prove that this is the case.
But this is like magic.
The latest is doing something.
At this point, I expect
you're all kind of like at this point,
you know?
Then a miracle occurs
where the miracle is somehow L.L.
like you throw some crypto keys into
El Alal and like magically
private keys fall out.
I don't know what happens. I mean, you
you know, even like mathematicians who've
been studying this stuff for years, we
still feel like this because Lillo works
way better than it's supposed to.
We don't really know why.
So there you go.
So, yeah, you can if you
don't believe us.
We have fully weaponized code
on the website. You can try it out.
And, you know, see what you can get from
it.
So when I got into crypto,
there was a lot of these studies.
I mean, coppersmiths had published a
paper and holograph game had made it
comprehensible.
And then a lots of grad students
publishing a paper.
What if, you know, not this piece
of P, but that piece of P or
this piece or some chunks or some songs?
There were lots of theoretical papers.
But would anybody be so
stupid and give you a whole chunk off of
P? I mean, Nadya was artificially cutting
off the last eighty six bits.
This is nothing that you would see in
practice, not 2012.
We had the first encounter was
coppersmiths in the wild.
This was just after 2093 when
we gave our talk here that a friend of us
said, by the way, have effected some time
on his smart car keys and
the look kind of funny.
Now, fast forward until
this year, there was a great paper at
this year's Unix Unix conference on a
group of Czech researchers, and they had
noticed that some cards by Infineon.
So it's a big German chip manufacturer.
And if you have some of those
external BGP drives as such, they might
be having such a chip.
So they turned it Roka Return
of Coppersmiths and went the news
sometime this fall and that noticed
that Infineon is generating their primes
in a very strange way.
This is not how you generate primes.
I mean, you can search for a whole bunch
of those things and you you'll get a
prime.
But why?
So what was known here was this M
and was a lot of massaging and searching
around. They had managed to get this
a this little exponent, either
with the GS also known that managed to
get this aid into a sufficiently small
set that you could search it.
So then pick one of those
A's computer to a
modem.
And use coppersmiths Mazatec to get Kay,
you get a number, then
probably it's a factor test.
You don't get a number.
Well, too bad.
So just try this for each of those.
These look the same like Tannadice.
Let us and not just talk part,
just not to mention three, but somewhat
larger mentions in the paper that go
through lots of variations of how we can
trade off the number of A's.
You have to try for the dimension of the
letters. So there's a lot of tradeoffs.
But this actually affected 10
20 Forbert and 2048 bit
hours ekis that were used in real life.
RSA, of course, is in much more
trouble.
More than Shor's algorithm
is going to factor RSA
10, 24 hours, a two thousand forty
eight, RSA four thousand ninety six.
It's gonna be a nightmare.
When is this gonna happen?
Well, that's not entirely clear.
There are some predictions.
For instance, back in 2015
when we gave the PKC hack stock.
Mike Moscow, the deputy director
of the Institute for Quantum Computing
at the University of Waterloo, said half
chance of factoring RSA 2048
by 2031.
And then just this
year, Dario Gil was this is
somebody who's the head of
it's a vice president at IBM, the head of
IBM. Q Now
with a name like. Q Thinking about the
James Bond films, this must be something
cool. And it is.
This is IBM's quantum computer,
dare I say, weaponization division.
This is their commercial quantum computer
division. They're actually working on
building a useful quantum computer that
they can sell. And he says he says
we're gonna look back in history and say
that that five year period starting last
year is like the real start of quantum
technology, not just research as a
scientific field.
And he was advertising there, 50 Cubitt
quantum processor.
Now, how does this compare to what you
need for Shor's algorithm?
Well, the usual estimate is that
Shor's algorithm needs two times
the number of bits in your RSA modules
while somebody else's RSA module is.
That would be illegal.
Your own test RSA modules
that you're trying to factor, you need
twice that number of cubits for Shor's
algorithm to run.
And cubits are these quantum bits inside
a quantum computer.
So how does that compare to maybe
five cubits last year?
Forty 1749 cubits this year
to 200 cubits next year.
It sounds like within a few years we'll
be up to four thousand ninety six cubits.
And that's the end for, say, 2048,
except, well, it's actually a little
less to panic about.
It's gonna be a few years further because
Shor's algorithm needs four thousand
ninety six perfect cubits.
And what's being built are cubits that
only lasts a little while.
And then they degrade and you have to do
some sort of error correction.
And it's not like normal error
correction. You say the same thing three
times, three times three times.
And if somebody only heard it once,
they'll figure it out.
If they heard it twice with an error,
they'll figure it out for four quantum
bits. You need like a thousand
quantum bits a thousand times your size,
your computation to simulate
one good cubitt.
Assuming that you're cubits are the level
of reliability that we think is
reasonably achievable, which means Shaw
needs four thousand ninety six times a
thousand cubits and that's
several doublings further away.
It's gonna be some years, maybe like 2031
before somebody in public is factoring
RSA 2048.
So what do we do about this?
Well, post quantum cryptography, there's
lots of replacements for RSA
that we don't know how to break with.
Quantum algorithms like Shor's algorithm
and Nyst a year ago called for
submissions of proposals for
standardization.
And they got the deadline was the end of
last month. They got 82 submissions
and they put up this table, which was
classifying these submissions into
theirs.
Latticed based, code based, multivariate,
hash based. You can see the numbers for
encryption and signatures, numbers of
submissions at peak.
You see Hack's, we talked about code
based and hash based because those are
the oldest lasting
post quantum proposals.
There are some systems from 40 years ago
code based on hash based proposals which
seem to survive quantum computers.
There are also lots of code based and
hash based systems that are much newer,
but at least there's some that go way
back. And if you're willing to pay the
expensive them, then it seems that
you can get security.
What that means is nobody's come up with
a quantum algorithm that breaks them
lattice based and multivariate.
Those go back about 20 years.
There's some lattice and multivariate
proposals that we don't know how
to break, even if somebody builds a big
quantum computer and then other there's
things like I Sargents published about 10
years ago. First proposal, somebody came
up with a pretty good quantum attack.
Now they're super singular.
I saw jinnies which have held up for a
few years, but maybe they don't continue
to hold up.
Nyst put up a week ago.
They list of submissions.
So we'll be hearing quite a bit more
about these submissions, not in this
talk, but over the next few years as
people study the security of these
and figure out are these things that we
can actually trust to protect our data
against a big quantum computer.
They only posted sixty nine instead of
the 82 that they received because they
said, well, the other 13 were not
complete, not following the rules.
So we're down to sixty nine submissions
a week ago and
now we're down to actually somewhat
fewer submissions.
So there's some that I put and read here
three hours after Nyst
posted this list of submissions,
I.
Guess again is in red there.
Lawrence Penny, who might be in the
audience.
And in any case, he'll be able to see the
videotape later.
He posted a script which retrieves
a guess again, plain text from a cipher
text without the secret key.
So that's the end of guess again.
And that was it. OK. Three hours and 10
minutes. That's good work.
Yeah. All right, Lawrence.
Are VB and other one, they're
also broken by somebody named Lawrence
Penney.
And then let's see, OK.
HK 17, that's one that Tonya and I
put up the script that breaks
rack costs.
That's one where that's actually,
I should say, the three that I mentioned
before, HK 17 RGV.
Guess again, those are other submissions
and they're maybe not. Things have been
studied so much.
What about a code based submission like
Rack Costs, random code based signature
scheme. Well,
Tonya and I and
also Andre is hosting and also somebody
named Lawrence Penney
posted a script which
well, completely breaks.
Right. Cos actually we came up with three
different attacks and it's maybe
it's OK with bigger parameters, but
not something you should use with the
parameters they submitted.
And then another example, Heela five
or what.
Dutch people in the audience.
This is called Helus.
This proposal is well
it's OK if you use it with signatures
that stopped chosen ciphertext attacks.
If you have somebody else giving you a
signature scheme like A.l.
S. But the submission claimed
chosen cipher text attack
security.
And we posted a script.
We.
Well, Tanya. Me again.
And then who wrote but I don't drink.
And also somebody named Lawrence Penny.
He got to watch out for this guy.
All right.
So at this point, there's still some
submissions left and
we'll be hearing more about what gets
broken by Lawrence and maybe some other
people in the future.
OK, so since we heard so
much about breaking stuff, let's break
some more RSA. Just for fun.
So I want to show you another variation
of how to break RSA with lattices, which
is the coppersmiths small public
exponent attack.
So.
All right. This is audience participation
time.
Here's some code.
All right. So I take a message which is
squeamish. Orsa Farraj.
How do you pronounce that?
I turn it into an integer by making
it base 35.
This is just so I can, like, print it out
nicely on the screen.
There's nothing really complicated going
on here. I generate a perfectly
legitimate RSA modulus and
it has 10, 24 bits.
And I encrypt my
message with RSA by cuming it
mod and.
All right. There's a problem here.
What's the problem?
It's too small.
Thank you. Good.
Some people in the audience are still
following.
OK, we've got a problem, which
is that the ciphertext
is smaller than N.
And in fact, slike the message cubed
is going to be smaller than N.
So this like modular reduction mod end
doesn't do anything.
And we can just compute cube roots over
the integers, like easily.
So this is not secure RSA
encryption problem.
This is this is why you use padding
schemes for RSA.
One of the many reasons.
OK. So messages to small
message, cube lesson and module reduction
does nothing. That means you're not
actually doing RSA.
OK, here's a variant
of this problem, but it's a little bit
more complicated. So I made my module's
and a little bit smaller just so the
example could fit on the screen.
But, like, that's not going to be the
issue here. So I generate a perfectly
legitimate RSA modulus n
300 bits.
I'm not going to try to factor it, even
though it's probably possible.
So now I have a message, which
is the password for today is swordfish.
Turn it into an integer in the same way
as before. Not trying to do anything
super complicated.
I do textbook RSA encryption by cubing
the message mod n.
OK.
So since I,
since my message is logger and my my
module is smaller, I don't have the same
issue as before. Or if I just try to
compute the cube root of the cipher text.
It is not equal to the message.
So I've, I've not broken that way
but through might still be an issue.
So maybe like since this
message has a particular format, you
could imagine that attacker could guess
like the message is the password for
today is something and maybe
there's like whatever password it is.
And maybe they know that it has nine
characters, but they don't know what it
is.
So can they compute that?
So maybe the attacker has guessed
that the message looks like this where
they don't know some chunk of
the message, but they know the rest of it
through some attack.
So I have my secret value or by it my
evaluation that the attacker has guessed.
Here comes the magic trick again.
So I construct
a matrix.
This is gonna be a lot of spaces from
my guess is what the message looks like
and the cipher text
and the modulus.
And then I've just like filled in some
zeros for for the part of the message
that I, I don't know yet.
OK, so I have a lot of spaces.
What do I do is that I run LML on it as
before I get some vector.
I construct a polynomial from
the coefficients of this vector.
I'm, you know, magic.
And when I look at the roots of the
polynomial, I got the piece
of the message that I didn't know.
Back out again.
Magic trick.
I hope you guys have been scared into
never trying to implement RSA on your own
at this point.
So, OK, what's going on?
It looks very much like before, so I'm
going to write this in English.
I don't expect you to necessarily be able
to, like, prove that this works, but just
to, like, verify that.
I don't know, like we're doing something.
I wrote down some polynomial that has
this pretty small root.
So in this case, I do.
I don't know what swordfishing is, but I
know that swordfish plus the thing that I
guessed for the message
is, is my message.
And I know if I cube that mod and then
I get the cipher text.
So, you know,
swordfish plus A cubed minus
C should be zero mod and.
Some polynomial magic.
I construct a lattice of the coefficient
vectors of polynomials that vanishment
n one of them is the thing that I wrote
down there and I don't know, like end
times X squared seems good.
I called El L magic
happens and I wave my hands
and then somehow I got a polynomial
out of El Alal and my solution,
swordfish was a root of the corresponding
Spaull polynomial.
So this is coppersmiths small
RSA exponent attack.
And there's a bunch of variance of it.
It's super cool.
So if I have just freaked you out,
here's some countermeasures against
Coppersmith sort of padding, attack,
small exponent, etc..
You could if you're if you're worried
about this donees RSA, it's one option.
If you must use RSA, use a proper padding
scheme, RSA, OEP, that kind of thing.
If you must use RSA, don't use small
exponent ee.
Like use exponent eyerly six five five
three seven. Then this definitely doesn't
work.
So we actually didn't come into it.
We didn't want me to talk about RSA the
whole time.
We also talk. Wanted to talk about
constructive uses of lettuces
and sort of talked about one of the
oldest of the let space criticisms called
entra.
It's due to hefting Pyfrom Souleyman.
The publication is eight.
There's even some preprint which are know
online from Ninety-Six.
And they were looking for just some
alternatives for hours.
ATCC, they're pretty
aggressive in their advertisements and
they did manage to get speeds that were
faster. They looked at curves and
ah, as a
competitor, as you see, they still had
larger key sizes and larger ciphertext.
But they were kind of going forward
just as an all competition.
They were not so much running the oh, we
might be secure against C1 computers.
Even though Shor's paper had appeared,
this was not so much on the mind of
people.
Now they did a signature system
and an encryption system.
And these signature system
is multiple signature
systems.
Had a bit of a bumpy ride.
I remember being a trip to 2006 when
phone again was giving yet another talk,
breaking some of the interestingly just
systems. And he was like, so
who in the audience has not yet broken
an interesting control system?
Well, for the designers, they look limit
board, I like that
description system has held up
better that at the beginning a little bit
too small parameters, but
in principle this was fine.
And so there was a bunch of cryptanalysis
during the last 20 years, but there
wasn't all that much research
into how to use it efficiently.
And then just because you have a nice
math system like
ours, a you take em to the three,
all the things you've just seen are
proper are it's a but improperly
used.
So secure use, which is usually big
issue, but not much
happened on that.
I think partially because ah the entry
company had decided to patent this
thing and we are all like,
why should I spend my time investigating
a system which I can't actually freely
use afterwards.
By now the patent has expired.
So I'm happy to talk about it and say,
well, let's look at how it works
and maybe we can break some stuff.
First of all, you have to understand how
entra works, so ways
are as AFC and you need pretty large
integers with entra, we
need polynomials.
And there is one system, PROMETA,
which is N, which is the D
limit on the degree of these polynomials.
These are just integer polynomials, so
you have coefficient zero one two minus
five and whatever.
And then for the examples, we're gonna
choose slightly less than 250, like
seven or something.
If you have two such elements and you
want to add them, you can
just do this coefficient wise.
So the Azera plus B zero is
a coefficient of one,
A one plus B one is the coefficient of X.
And so until all the way till extra
the N minus one, which has
a minus a sub N minus one
and D up Amara's one.
We also want to multiply those.
Now if you multiply polynomial degree
three was one of degree four.
You getting something of degree seven.
But we won't like to have something of
small degrees, so we need some way of
wrapping around.
And so they define a thing called a
sickly convolution where you basically
wrap everything around after and
minus three.
Minus one.
And the rule for this is.
The coefficient of extra
one, for instance,
the aye ay I.
B.J., these two indices,
they will sum up to one
or end plus one.
And for the X to the end minus one, they
will sum up to the.
And minus one. So and minus one bloops.
There will some up to X months to end,
minus one.
OK. So this is her explanation with which
we can compute.
We can work with it.
We can teach it to a computer.
If you want to know where it comes from
is the same slide with a little bit more
math notation.
So what we're actually doing is we work
in the polynomial ring.
That's just a fancy way of saying Polearm
is an integer coefficients.
And then we reduce modulo
X to the end minus one.
This is the same kind of function where
we say we would use, what, seven,
but we take every model of seven
and replace it by zero.
Here, replace every multiple of X
to the N minus one by zero.
Or you take extra the N
and replace it by one.
And then all the operations
just work the same way.
Except that we have to. Right.
And minus one there.
Well let's see some numerical examples.
All right,
starting with a little bit of
incomprehensible sage notation for
creating a type of Class Z,
X, which is going to have our polynomial
objects and looking at an example that
this F here is a polynomial four
times X squared, plus X plus three.
So two, three terms in that.
Three things being added up.
The coefficients are the integers four
and one and three that are multiplied by
X squared and X and one.
This is degree two.
That's the biggest power of X that you
see there.
The exponent that if you multiply,
then the distributive law says you're
supposed to multiply each term that
you're adding up by every other term
you're adding up like if you multiply F
times X, you you multiply the three times
X, get three X, multiply X times X,
get X squared and so on.
And all the times here, it's just built
into it.
Another example, multiplying by this
other polynomial g OK is a bunch
of things. I won't go through all of
them, but looking at the last coefficient
of f that three it gets multiplied.
Maybe I'll point with the males here, the
three and F gets multiplied by the two
in G and that gives the six and
the three and F gets multiplied by seven
times X giving twenty one times X..
Wait a minute, twenty three times X while
there's also a two times X
which adds to the twenty one times X
giving twenty three times X etc..
And you can multiply all these or just
tell Sage do the work for you.
All right. What about that multiplication
operation with the end coefficient
things. Well this is how you say that
and say you take two inputs
and coefficient polynomials F and G and
multiply them.
The percent is mollet just like in C mod
X to the N minus one.
For instance, if and is three then
same polynomial F if you
multiply F by X
then you get the same three X and X
squared and for X cubed.
And what happened to the four excuse that
turned into four.
If you see X to the end it turns into one
and if you see X in the end plus one
turns into X and so on.
And if you multiply F by X squared
then well it rotates the coefficients
again. And another example,
the same F Angie from before.
If you do the convolution, you
multiply f Angie and then replace
X cubed with one, which means
you add the twenty nine into the six
producing thirty five and so on, leaving
you with only N coefficients.
All right, back to the description.
You've gotten a little more comfortable
with our elements here.
So we are going to continue working with
polynomials.
But if you saw the last examples.
But then if you imagine
multiplying, multiplying or explanation,
you see that the coefficients get larger
and larger.
So similar to how our is a.
We also need to it use what n else we
gonna see these same scrimmaged also
projects before.
We will need to have some well.
Reduction here. So there will be another
system. Prometa called Q.
Doesn't have to be prime, it's typically
extra power of two.
And it just means we will have
our coefficients bounded by it
most. Q. So when you wish.
Q We would use MOTD.
There is one condition that Q is not
three, because we will also have three
running around as another thing where
we reduce.
So we'll have two things to reduce by
will have this extra the end minus one.
So we will reduce the degree
and we will reduce the coefficients.
So every single coefficient, each of
those N coefficients, we will apply
reduction or Q or reduction what three
to them.
Good. We're now ready to get
entra public keys and private keys.
What we do is we pick two
such polynomials.
We're gonna be even more restrictive
because we to have them small.
So this f Anji will only be allowed to
have zeros and then in a few
plus and minus ones.
So this is much, much smaller than Que
will just allow a few ones
and a few minus ones. That's going to be
fixed. Number of those four F and A
fixed some of those four G.
And then while an hour is a
you multiply our two things here,
we have a different operations.
We will search for an H
such that H times F was this second
convolution.
We'll give three times G.
Sometimes it doesn't work.
So if to try again.
So if it doesn't work, we have to try
with a different F.
When you think of the notation we
actually dividing by this F
and not all F's are inevitable.
We can't divide by zero.
So some of the FSB to throw away and try
again.
So our public key is gonna be this H
and the private key is going to be the
F.
H and F for that,
we can't get G, so G is we don't we don't
need to remembered some.
Are we done information we only computed
once because well take some time.
It's gonna be called F three because it
runs around with a reduction or three.
And it's such that if I take F times
F three, I'm getting one.
So there's a polynomial where all the
coefficients for all the powers
of X are zero except for the constant
term.
Can I come to the full slide
and the talk?
So this is explaining how to encrypt
and how to decrypt,
except for. Don't do it this way.
I mean this way. You get all the pending
attacks and whatever.
But this is giving the the heart math
problem.
So this boils down to something similar
to ours. Avey say we have to factor
similarly here because it is still the
entry problem.
If you want to use this in practice, you
have to be a bit careful how you should
see em. You have to put in some headings.
You should really.
Well, don't do that this way.
So we'll have some more slides of how to
use it.
But let's get a wait for your plug
in a message.
Do some stuff. Get a ciphertext.
Do some more stuff and get em back.
CipherText is gonna be put a simple V
pick. Another of those polynomials was
very few non-zero coefficients.
Again, limited to plus and minus one.
Let's call this thing. Ah.
And then the ciphertext simply
our times this h which was a public
key.
Again, this modification which limits
everything to degree less than N
and then we add
O message.
So we need to somehow get our message
into a polynomial which has coefficients
in the set plus minus one and zero.
But there is no restriction on the
density.
This can be totally everything.
Plus one. It can be everything.
Minus one.
No restriction.
So, for instance, you take your message
in ternary.
And then replace powers of three with
powers of X.
So getting em in there is no
big deal. And then encryption was easy.
Then you have encrypted.
You send the ciphertext over.
And now it's a question how we can get
this MBK.
So we basically would like to
divide by H.
But dividing by H.
Compiz as loose because just public,
anybody could do that.
And there's all this em sitting around.
So it would be an inexact division.
So if we wouldn't have any of the
reductions smalls extra, the N minus one
would just be divide page and take
the leftover, take the remainder
because we have this reduction to the end
minus extra N minus one.
This one is not possible.
Now, here's the way that we decrypt,
if we have the secret key,
we take our ciphertext, we multiply by.
If this was our first
secret key.
And remember the relation between the
public and the secret key that was eight
times F is 3G.
Came, I'll put in everything so we are
brave. We plug in, see the ciphertext
that was our times H plus M
and then we move things around.
I should have said these modifications
are fully so that you can move things
around. It's distributive.
It's commutative. Everything you want.
OK. So we can move this F next
to the H and F times H
gives you three G.
So then the first term simplifies to our
times three G and
then second term. OK,
now we have F times M.
We all had M.
There still is F running around
but there is now a three, the first in
the first term.
So if we can I would use my three.
We don't have to worry about the.
Our Times 3G term
and then we have this EF three running
around, which, if I multiply
by it gives me one.
So if I have the second part F
times M because I got rid of
the three by reduction.
Then I have this times F three.
Gives me F times F
three, which is one times M.
So it gives me M.
There are few technicalities.
I've been kind of glancing over that I
need to reduce more m every once in a
while also, partially because
else you would see some growth.
So that's the important part in the
encryption function.
And then down here in the decryption
function, I need to first would use
we do smart cubicles.
Else this relation, this HMS F
3G only works what.
And I also have to move my representation
to something specific.
Normally if I tell you more.
Q You would want to have zero till Q
minus one.
And I now shift this to be symmetric to
zero. So now going from minus
Q over to Tokyo, over to.
Let's see how this works.
So this is that moment in
Waterfall Software Engineering, where
they've just dropped the one hundred
pages of documentation on your desk and
said, implement this.
This is what the designers have done.
All right. All right. Let's see if it
actually works. Let's see if we can get
the computer doing it.
So this will be with smaller ends
and Qs and D then.
Well, there's a number of coefficients in
F and so on.
Smaller parameters than you can use.
But at least will fit on the slide.
So there's one of the functions
you can find online is
random Deepali.
This is not a stage function.
This is something which takes its global
variable D and gives you and also N and
gives you a polynomial that has
well D in this case five
plus and minus one coefficients out
of well a maximum of it goes up
to X to the end minus one.
So in most X to the six and there's
some random polynomial.
And then there's another function that we
put up called invert mod prime.
And that is doing this come up with
three F sub three which.
Well what is is have three supposed to
do. Let's check this.
What it's supposed to do is that if you
multiply F by EF three, when I
say multiply, it's always this is
convolution operation.
When you multiply F by a three, it's
supposed to be something that's one mod
three.
And if you look at this and
ignore all the multiples of three, like
three and minus three, then all you're
left with is one.
So think of this as F times.
F three is one.
All right.
There's also some inversion
mod. Q that was for computing
h h the public, he was
well some formula with some GS
and threes and divide by F at some
point.
Well F Q is something that if you
multiply it by f convolve it with F
then you get one mod cute.
Q is 256 in this example.
And yeah, 257 mod 256
is one and these multiples of 256
all go away.
All right. And then G is another secret.
And the public key is three times
the one over F times G
modulo Q And there's a weird
thing that happens here which is this
minus sign.
Now if you're accustomed to
mod in C or lower level
languages, then it'll give you
negative outputs.
If you give it a negative input mod
something, unless it gives you zero, if
you have a multiple of Q you'll get
you'll get zero.
When you say mod Q if you have a negative
number you'll get something between minus
one and minus of Q minus one.
If you have a positive number, you get a
positive result, which can actually be a
real problem for crypto leaking.
Whether that input was was positive
or negative in the math description of
entier, there was some footnote in some
part of the design document going, yeah,
I make sure you only release a range
of exactly. Q numbers between zero
and Q minus one or.
Well, OK. She said between something like
minus Q over two and Q over to minus
one.
And then if you leak well whether
the input was positive or negative,
that's actually maybe a security problem.
So instead of that, we have a function
online which is balanced mod, which
always gives a result, which is well,
it's like a normal sized character
assigned by it. It's between minus 128
and and 127 if Q is 256.
All right. That's the public key.
No more leakage of whether the original
input was positive or negative.
And to check what this
F. Q was supposed to do, the whole point
of H. Is that if you multiply
H by F, multiply the
public key by this important part of the
secret key modulo Q
then you get the same thing as three
times the random G.
That was come up with as another secret.
All right. Let's see if we can encrypt.
Here's a message. Just a bunch of random
ones, zeros minus ones.
And then another random R
that was showing up in the encryption and
then the cipher text C is you take
H times the public key
and then add em to it.
That's this convolution of H in are add M
and then reduce Mond.
Q and that gives Sugandh some random
looking bytes. Seven random looking
bytes.
And now decryption was multiply
the cipher text by the secret F
reduce mod. Q And then
Tonya mentioned that.
Well this is gonna be the same as three
times G. Times are plus F times M
and then well multiplying
that by the F three and
reducing Mod three finally
gives exactly the same as the original
input message.
So this system actually works.
It has successfully decrypted a message
from the ciphertext.
This shouldn't actually work.
Didn't somebody tell you that he can't
just reduce, what, three and what?
Q I mean, if you take something
like this expression and you hope
that there is a three that is running
around there, let's assume molecule's
five.
And we have six.
Six is beautiful.
We divisible by by three.
But then we reduced, what, five?
And we left with one, which is not a
multiple of three.
So in principle, this shouldn't
work.
Now, the reason that it still works
or depending on the product is how you
choose them works most of the time.
Is that the parameters it
shows in such that
the numbers are small enough?
So this only works if there's more.
Q On the right hand side doesn't
actually take away the three.
So if there is actually no need to
compute more. Q So if this thing on
the right hand side is by itself
smaller than Q.
So this is where everything comes in the
reset at the beginning. Oh, you're only
allowed to choose a few of the
coefficients to be non-zero.
You're only allowed to choose plus and
minus once because
this our times 3G.
Our has only small provisions.
G.S. only small provisions and OK, then,
if the three running around, so
the maximum coefficient we get at every
moment is if a plus one of
our hits, A plus one of G
and the multiply.
And then we sum this up in
times.
But there can't be any such things.
There's only deep coefficients that are
non-zero.
So the worst coefficient of this product
will be D times
a perfect match of plus one plus one
and perfect match of minus one, minus
one.
So if they really conspire to always
add up to the maximum, we can see
something like 3-D for the first part.
And then similarly, while there was no
weight restriction on M, but there was
a weight restriction on F.
So when a coefficient of F of which we
own have D hits
a non-zero coefficient of M, we get
a summit.
So the maximum we can see in any
coefficient is gonna be four times T.
Now, our choice will be that we want to
have that cue over to is larger
than 40.
So let's choose our cue large enough.
Say large part to
then this reduction will not make any
problems.
OK, now what
does actually have to do with lettuces?
I promise at the beginning that this is a
letters based Krypto system and then I
start talking about polynomials.
Now, yes, we have seen and not just part
of the talk that you can take your
coppersmiths thing and put polynomials
in as basis vectors.
But I first have to still explain how
to translate that into a problem.
The problem of finding F.
Into a problem of finding a short vector
in a lattice.
So first of all, here's how I set up
the same matrix.
So for setting up the Matrix, I'm only
allowed to use public information.
I don't know the F.
I don't know the G, but I do know this.
H.
And this matrix, this capital H
block there, that is going
to be a block, which is in
columns and end rows
and then above it there is a identity
matrix. So that has Q entries
that are all equal to one on the
diagonal.
Then there's another matrix which has
those once on the diagonal.
Everything is zero up here.
But this H is the interesting part
H. I've been putting in each row
all the coefficients of little H.
Well actually divide by three, but keep
such that if I take any vector.
Taken as a polynomial, say this first
vector there, this one zero zero
would be the constant one.
The other one would be the constant
three, such that it corresponds
to modification by the polynomial
H.
So let's show an example.
I have this long.
Links to any rector.
I have to end by to
end Matrixx sitting here
and I now take the first
part. That's nice.
It's just a unit vector.
So that will take from the top part
of The Matrix, just the Q Times identity,
so that just gets me a Q They're
aggressive zeros.
Then the second part is this
three zero zero zero.
And I said it should be such
that if I multiply by anything,
it's like multiplication by the
polynomial.
So this will grab exactly
one times this polynomial H.
So that tells you how you write this
polynomial h there.
And then you would have say the next
coefficient would get this one but
rotated this one rotated times
two.
So this is how you write a matrix.
And now what is a short vector and this
let us.
To get any victor in the lettuce, that
means to take integer multiples
of these vectors.
That means we're taking some polynomial
combinations or integer polynomial
combinations of this.
The reason why I'm getting G times F out
of G, comma, F out of this is,
well, I don't know what it looks like,
but there is a polynomial K.
And there is a part of my life that I
knew, such as Kate
Holmes, f kick him out f times
his matrix is give me G, come
F and G and F
are small.
That means they have very few non-zero
entries and the entries are very
small. They only plus or minus one.
So if I'm right about this
and I'll walk through steps in a moment,
then this vector in the letters is very
likely to be the shortest vector at all.
So then I can use l l or something
to actually get this vector.
So if you run through this, well, this
molecule just means there is some certain
multiple of Q so that H
times F is three G.
That's more. Q So there's times
K times. Q and that's
the K. I'm stuffing it there
again.
Don't trust me, just implement this.
See how it works.
Just implement, just implement,
she says.
Doesn't she realize how hard this is?
All right, so we pull out Sage.
And first thing is just a little
conversion of H into H divided by
three mod. Q I think since we're a little
low on time, I'll skip that part
and just say what happens when you
multiply.
Yeah, a lot of big polynomials.
What's happening here is that H
three which has H divided by three,
that's being multiplied by X and X
squared next cubed and so on as
convolution, which means it's rotating
the coefficients around.
If you look at each line of numbers,
fifty eight to ten, fifty four.
You see that on the next line.
Rotated round
one position to the left.
Fifty eight has gone to the to the end
and so on. And.
OK. So here's a bunch of polynomials.
And what matters about these polynomials
is that some
combination of these if you add up some
of these and subtract some of these,
you're gonna get G modulo
Q because remember, F is
a bunch of one
X, X squared and so on, added and
subtracted in some way.
And if you multiply that by H, you get
three G and this H three is while
you multiply by H over three.
That's gonna give you G.
So G is gonna be add and subtract
whichever of these polynomials you get
for corresponding to you
wrote F in the first place.
The secret F was some indifference
and some of these X squared.
All right. I'm going to just show you
the matrix that comes up at
the end of this. Here's this
to end by two and matrix, where on the
bottom left are the same numbers that we
were just looking at with some 58
suns on.
And then down
the diagonal, there's some cues and ones.
All right. And then we pull out the
nordia to give us our
short vectors in the lattice and.
OK. There's l.
L results and suddenly there's much
shorter results.
These are all l ls giving you not
just one short vector, but a bunch
of short vectors, a short kind of short
basis. And this KCC super short
vectors up at the top.
The first row is a very short combination
of the original vectors.
All right. If you extract the second half
m dot l l bracket zeros taking
the first row and then the bracket and
colon is taking from positions and two
to end through two and minus one of
that first row.
And that gives you five non-zero
coefficients, two more zero
coefficients.
Converting those into a polynomial
is exactly the secret
F well with a minus sign.
But that doesn't affect the decryption.
So if you run for this f that the
attacker found just from the public key,
setting up a matrix running l l l
on this polynomial lattice.
Then you break enter.
You can decrypt any message you want.
Now you have to scale this up to
get real security.
Of course, seven dimensions is not
enough.
If you go up to, say, 150 dimensions
and hundred one non zero
terms in F and so on and Q
scale that up to a two to the thirty two,
then there's gonna be more than two to
the 200 choices of the secret f
you try the attack again and
the attack does not find plus and
minus ones.
It still finds a kind of short
polynomial.
It's not necessarily the shortest, but
it's sorta short and it still breaks
the system, which is kind of scary.
What you need to do, the reason this
still breaks the system is that Q is
actually too big.
You don't always have crypto parameters
being more secure if they're bigger when
Q is really big, that allows
this kind of big F to decrypt
because the whole decryption procedure
needed that there wasn't some wrap around
modulo. Q If Q is smaller,
it actually gets more secure and then
this F does not break the system anymore
and then well for good security also need
end to be somewhat bigger.
All right.
So what do you do this?
There's a whole bunch of text to take
into account. Choose smaller and smooth
shoes. Logic,
shoes, smaller, cute shoes larger.
And they are all the corporate tax I
mentioned at the beginning.
But to close on a positive note,
if you take this and
try this at home.
Am I on. Okay. If you want to try this at
home. Everything that we talked about.
So there are plenty of things that you
can do.
You probably don't want to use lattices
yourself right now.
So every Naess submission to the
post Quantum Crypto Competition has a
reference implementation which is
available online.
More than 90 percent of them have
survived to survived a week of
cryptanalysis.
So you two can go
and analyze these implementations,
break them, prove their security,
whatever you like. So this is what the
world needs.
If you're interested in integration of
quantum safe computing or quantum
safe crypto into actual protocols,
there is a project called the Open
Quantum Safe Project, which
has a bunch of implementations of schemes
and integrations into things like open
SSL.
You may not want to use this right now
because schemes may become obsolete due
to crypto analytic advances like the ones
we've seen.
There's a lot of work at every level to
break stuff, analyze proposals,
look at implementations, all sorts of
things needed. And if you really
feel inspired to turn on post quantum
cryptography and your own projects,
we would recommend using a hybrid
approach with elliptic curve cryptography
and not using bare
quantum post quantum schemes right
now. So Google did this, for example,
this past year with
a post quantum key exchange and
it did a hybrid approach with elliptic
curves. So that is all we have.
So thank you very much.
And we hope to see more broken
schemes.