# Lattice Attacks for Variants of LWE

[MUSIC]
>>Thank you everyone.
Thank you for coming,
and thank you to Melissa
for continuing to organize
the MSR Crypto Colloquium Series and
for helping to invite visitors.
So today, we’re very pleased to
have Professor Shi Bai visiting us.
I think this is his first visit
to Microsoft Research here.
I’m very pleased to have him.
So he is an assistant professor
at Florida Atlantic University.
Before that, he did a post-doc in
Auckland University and also at
Ecole Normale Superieure des Leam.
>>Yes.
>>Thank you very much for coming.
>>Okay. Thanks very much
for the introduction,
and thanks very much for
the invitation from
Christine and from Hall.
It’s really nice to be with MSR here.
I’m going to talk about Lattice
Algorithm for Variants of LWE.
You can watch, there must be
something dangerous in my slides.
of LWE and SIS problems.
Then only after that,
I’m going to introduce the lattices.
So my intention was trying
to convey the message that
the lattice attack is not
the only attack to LWE
and the SIS problems.
So the lattice attacks
have some good features,
but they are not the only options
for attacking lattice-based themes.
Then, I’m going to talk about
the general structure
for solving LWE.
I’m going to divide
that into two steps.
The first step, I call it
strategies and the second step
I called the uSVP and BDD solver.
So we combine them together to
solve the LWE using the
lattice based method.
In the end, I’m going to give
some questions and a few tutorials.
LWE, I’m going to write out
the matrix form of LWE.
So sample uniform matches
A for integers mode q
that measure m times n,
where you only require
m is bigger than
n to form LWE instance
to making sense.
There, I re-sample s according to
some secret distribution where
the distribution is to
be specified later.
I’m also going to sample
small error according to some
error distribution, D_e.
So the matrix version
of LWE problem is
to recover s or e given A and b,
where A and b are called
metrics form of LWE samples.
As a typical parameter given
the input security parameter Lambda,
I usually take n as
the state function of Lambda,
and take q to be
polynomial in terms of n,
and to be not really far from
n and the secret and
error distribution,
we expect it to form uniform
and discrete Gaussian.
But these are just one
typical choice for LWE.
They are really
conservative parameters.
In practice, in order to enable
more functionalities built on LWE,
we will need more secret
error distribution.
So I’m going to talk
So this is a visualization
of the LWE problem.
So given the uniform A,
I have secret s and e,
and b is given,
so the problem is to recover
s or e given only A and b.
So the decision version
of the problem is,
given samples A and b,
either they come from LWE samples or
is it they become
from uniform samples.
Decide whether they are
coming from LWE or uniform.
So there is a reduction between
search version to decision version
and vice versa, which is trivial.
But there might be some loss
during this reduction.
But in practice, we could either
solve the search version
or the decision version.
So in order to introduce the
strategies for attacking LWE problem,
I’m going to introduce the dual
problem which is called the
ISIS problem or inhomogeneous
short integer solution problem.
So the problem is really
due to this LWE problems.
Let me right get to the next picture.
So the problem is given B,
which is a wide metrics,
you can consider this
as the transpose
of the matrix A as a B sample,
and given the target t,
SIS problem is to recover the e,
such that B_e equals to t mod q.
So that’s a dual problem
to the LWE problem.
Variants of LWE as mentioned,
in order to enable
more functionalities for
cryptographic schemes built on LWE,
we’re going to choose
the distribution of
s and e from a variety of choices.
So the textbook one is to
choose s to be uniform
and e to be small.
So small here means standard,
means Gaussian distribution
of valuation not too small.
Well, that’s what small mean here.
Also, there are the normal form
or hemi-normal form of LWE where
the secret distribution follows from
e. So I say both of them are small.
There are also binary
error versions LWE
where the s is uniform
but the error is tiny.
Tiny means binary in
this typical case.
There are also cases where I
require both of my s
and e to be tiny,
which are both binary.
Of course, there are
also binary secret
only LWE where e is standard.
So small means standard over here.
For more functionalities such
as for homomorphic encryption scheme,
sometimes we need s to
be extremely small,
s to be small and e to
be relatively small.
So here, the variants,
I only classified the
variants according to
the distribution of our s
and e. So in practice,
there could be
a different situation with
the number of samples given
or the size of the modules q.
So all of that becomes useful
for typical or specific schemes.
They are supported by functionality.
So there are lots of
applications for LWE
such as signatures encryption,
homomorphic encryption
schemes including
the SEAL developed by Microsoft.
These combinations of
secret and error distributions,
the number of samples
given and modules of Q,
they give variants of LWE
with various difficulty.
So the concrete security
level needs to be
carefully analyzed even
though asymptotically,
sometimes they don’t
really differ too much.
So before I start to describe
the lattice algorithm,
which I presented it as
a geometric algorithm,
in the calculator to
solve the LWE problem.
So the first one is to call
the algebraic attacks,
which arise from the initial work of
Arora-GE algorithm
and their variants.
Combinatoric algorithm follows
from the original work of PKW,
as well as meet in
the middle line algorithms.
The geometric algorithm is to freeze
the LWE problem or the SIS
problem as some lattice problem,
and thus solve this
problem on lattices.
So this is not necessarily
the best method to solve LWE,
but this is just one
alternative method,
that’s why I list all
of them comparatively.
So in this talk, I’m
not going to consider
the structured LWE problem because
of the reach of the structure,
there could be some other attacks.
In particular, one of
these structures are involved
with the error and
the secret distribution,
there could be some either attacks.
So some of the words can
be found in the literature
where I’m not going to
discuss that in this work.
So in this talk, I’m
going to focus on LWE,
in general QRA lattices in this talk
where the definition
of this will be given.
So just a very quick summary of
algebraic attacks for LWE problem
where I mentioned that it
follows from Arora-GE algorithm,
is particularly used for
the LWE problem where the
error is really, really small.
For example, for binary
error LWE problems,
polynomial as long as
the number of samples given
So that’s the current start apart.
As some of the number of samples is
slightly restricted to be
we still have a set
of natural algorithm.
This is by the global basis
algorithm for these authors.
On the other hand,
there is a reduction from
the worst-case hard problem
with polynomial Gamma but
in dimension over log A,
as long as m is slightly
larger than n. So the number
of samples given is
much larger than n. So by looking at
the best attacks here and
the best reduction here,
there’s still a gap between
the number of samples of a little
bit more than linear
compared to this linear one.
So the best attacks still does
not match the best
reduction for the moment.
So there must be a gap in between.
So as soon as the
error becomes larger,
so it’s more than the binary,
then this Arora-GE or
algebraic attacks are becoming
harder to solve the LWE problem.
So the rule of sum is the running
time is 2 to the Tilde order,
which drives the logarithm
of this part,
of Alpha squared q squared,
where Alpha is the error
rate for the LWE problem.
substantial when
the deviation for the
error or proximity of
q is smaller than square root
of n. So that’s smaller
than 2 to the n. That’s
However, for standard error LWE
where the error is
small or from Gaussian,
so this algorithm belong to
2 to the n log-log algorithm
which is even slower than
the senior algorithm.
So that’s the current state
of combinatorics attacks.
So in the second class of algorithm,
we try combinatoric type
of algorithm service,
which originally follows
from the BKW algorithm.
It does something similar to
the Gaussian elimination and
use that to do dimension
So that’s the basic idea of
this combinatoric algorithms.
In the extreme case,
if we treat the LPN as
a case where the q is two,
then the BKW algorithm
substantial time which needs
exactly the same number asymptotically
the same number of samples.
Lyubashevsky, it has some kind
of sample expansion technique
which simply combine samples
with a sacrifice on
the increase on the error.
So this gives us
slightly worse running time.
However, this only needs
a slightly more than
a linear number of samples.
For binary secrets and error LWE,
the better attack is from
is from Kirchner-Fouque.
They use BKW variant but they send
this BKW algorithm to have
a running time of two to the 0 n
log-log n. So as far as I understand,
they still does not match
the best reduction where the
redundancy is two to the 0 n log X,
they’re still get the 0 there.
For the standard LWE,
so that’s pure natural.
There’s also the meet-in-the-middle
type algorithm which does
a memory and time trade off.
They are typically used
for sparse secret and B.
We’re going to mention
some of them later.
The third category or class of
algorithm is the so-called
geometric algorithm,
essentially the lattice algorithm.
They turn the LWE
problem into problem or
lattices and then solve it either
using lattice reduction algorithm
or lattice sieving algorithm.
So the main feature is that in
this type of geometric algorithms,
the LWE resembles required
are usually small.
So if this is the case,
if the number of LWE
samples are restricted,
some of the previous algorithms like
the combinatorial algorithm does
not usually work very well.
In this case, it is
the lattice algorithm
which works really better.
On the other hand asymptotically,
if I only use the lattice
algorithm for taking the LWE,
the asymptotic running time is not
really as ideal as
the other algorithm.
For example, for LWE,
binary 60 error LWE,
binary 60 but small error LWE,
or binary 60 but small
uniform secret LWE,
or the sparse LWE.
There must be something
important in the slide, that’s
why they don’t want to show.
So for all of these variants of LWE,
the asymptotic running time of
lattice algorithms are
all fully exponential.
So in this case,
the lattice reduction algorithm
or lattice sieving algorithm
of the small secret.
Probably, the restrictions also
comes from the number
of samples it uses.
So in this lattice
reduction algorithm,
the number of samples it
uses is usually small.
So in the information
theoretic point of view,
it does not fully use
all the side boards
compared to the previous
combinatorial algorithm.
On the other hand, if
you allow large modulus,
for example if the modulus goes to
exponential but with small
errors up to some extent,
then the lattice reduction algorithm
is already run in polynomial time.
This is a property in this paper.
However, this lattice algorithms
are most relevant in terms of
concrete security levels to give
a concrete security
for practical schemes.
So a very quick
introduction on lattices,
because we only use the lattice.
Integral lattice is the object
that we are interested in
this talk because I want
computer reputation to be efficient.
So this is our integral linear
combination of vectors bi where bi,
I assume it’s a fluoride
lattice in this case.
Just notation purpose,
I take all of the basis
vectors b1 to bn and I call
b to be the basis matrix.
The lattice can be
represented by having
the integral column combination
of basis matrix b.
The volume of lattice is defined to
be the absolute value of
the determinant of the matrix,
which is independent of
the choice of the basis.
So it’s up to uni-modular
transformations.
So the quantity that we’re interested
in lattice problem is
the so-called the lattice minimum.
So it’s the shortest lattice
vector except point zero.
So in this picture,
it’s probability one,
because there is two-dimensional
lattices, it’s probably this one,
because that gives the smallest
radius and it does not include
any other lattice point
except the reciprocal of
itself and the zero-point,
since the definition
removed the zero point.
The main computational problem on
lattices is so-called
the shortest vector problem,
which we’ll show up here in second.
So the input of the problem is
that basis matrix b and the output
of the SVP problem is to find
a shorter vector in this lattice.
So in the integral column space
of this matrix is b.
So if we just look at
this two-dimensional lattice graph
which are represented by
this green dot points,
even visually, this seems
to be a very easy problem
because this blue wire seems to
be the shortest lattice point.
The main difficulty of
the SVP problem depends on
the inputs shape of the basis b.
So let’s compare with this
with the other picture.
If the inputs are these right
and blue two lattice points,
then this problem really seems to be
much more difficult compared
to the first problem.
That’s what it means.
The difficulty heavily depends
on the shape of the input basis.
In cryptography,
this input basis have
some similar shape of
this wire where they are
very skewed to each other.
So they are very far from
orthogonal to each other.
So the task is to, with that input,
recover the small
orthogonal lattice basis.
So in cryptography, we need
a relaxed version of
the shortest vector problem.
So the previous problem
is called the SVP-1,
where this gamma is some relaxed
or approximation factor.
the smallest shortest vector,
we are allowed to find a vector which
is at most gamma times the
last of the short vector,
that’s the relaxed version.
So in order to solve
the original data to exact
SVP-1 problem through the algorithm
or enumeration sieving.
In order to solve
this approximated version,
which are SVP gamma,
there are a variety
of algorithms which
renders from the triple-A algorithms
and the so-called BKZ algorithm.
Just a quick summary,
the best algorithm for solving
the exact SVP problems are
the enumeration and sieving.
The enumeration algorithm runs
in super exponential times,
so two to the n log n or more
than single exponential,
while the sieving algorithm run in
single exponential running time.
So in practice, there was a bit
of interest in history that
the enumeration algorithm
although asymptotically slower,
yearly outperformed
the sieving in practice.
However, this situation
has been changed since
last year where people
find that they can have
good algorithm which try to boost
the sieving algorithms such that
it also works faster in practice.
So the current state of art
intended to algorithm is,
in practical dimensions,
the sieving algorithm is
faster than enumeration as
well as asymptotically.
So that’s the current state of art.
Of course the consumer is wider.
The the sieving algorithm can be
extended to higher dimensions because
the sieving algorithm requires
exponential amount of memory,
while the enumeration algorithm
only requires polynomial memory.
On the other hand,
the best algorithm for
the approximated SVP
gamma problem is so-called BKZ,
whose complexity is dominated by
the exact algorithm but
in smaller dimensions.
So if the dimension for this
SVP gamma problem is in n,
so these SVP problems are usually
in dimension smaller than n,
maybe half of the dimension fall
for some practical schemes.
So that’s pretty much
the scene we need.
Two types of lattices that
we’re going to use and they are
relevant to the LWE problem.
So this is the LWE shape of
matrix which is input A,
and the lattice is
the qr lattice on this A,
which I call it as the either
maybe the column lattice or
the image lattice is
the image space of Ax mode q.
So the only difference
between the column space
over the ordinary r is
that I have a mode q here.
Let’s assume q is prime.
Maybe let’s see there,
it’s of a finite field,
and then I do a reciprocal lattice A
is orthogonal one,
which is called it’s
a kernel lattice,
because it is the set of
all the points E which
cancels out this input b,
and to make sure these two
lattices are non-trivial,
so they’re not that
m. I only require m
is strictly larger than n.
That’s the case for our input.
So if we have a LWE instance,
you only consider this one.
If I have a cease input like basis,
I only consider this one.
So that’s the two lattices.
So lattice algorithm for solving LWE.
I’m going to decompose
that into two steps.
The first step I call it a strategy.
So given the LWE problem,
there are different strategies
to solve the problems.
We can directly solve the problem
using some solver or Oracle,
where the Oracle can be
some instantiation of
the SVP solver or
some Combinatoric algorithm.
So on the other hand,
this LWE problem can be
first converted into
another LWE problem or another
ISIS problem or ISIS problem,
which I described in
the very first part of the talk.
There after that, we use
the Oracle to solve this problem.
So it looks like this is detour.
We’re doing some kinds of
detour in this attack.
However, in certain variants of LWE,
such detour indeed gave
a better algorithms.
I have a dotted line from
the solver to here which
means during this conversion,
it could be possible
that I use the power of
the Oracle in order to
get this conversion.
So some non-trivial computation can
happen either on this conversion
or either on this conversion.
So the very first strategy is
the so called the primal attack.
The main features it uses
is that in LWE example,
where the As is very close
to b modular q up to
the error vector e.
Because the e we sampled
it from a small discrete
Gaussian distribution.
We can directly solve this
problem as a CVP problem,
closest vector problem or the
bounded distance decoding problem,
using the Lattice Solver.
To do this, we consider the image
lattices arrived from A,
which is the column space of A mod q.
So this consists of
all the y such that y
equals to Ax where I’ve
come in from other that
n. So what if this y
is going to be close to
our b because e is short?
This lattice has got m
and volume q of amongst
n. So to solve this problem,
we can convert this BDD problem into
a unique activity problem using
Kannan’s embedding that
I will describe later.
But the concrete security
depends on the number
of the samples given.
If there is no restriction
on the number of samples,
then the best choice is to choose m
approximate equals to A over log q
divided by minus of log Alpha,
where Alpha is the error rate.
So asymptotic is
the running-time with
this primal attack is
given by this relation.
So from this, we can already recover
the argument that I mentioned before,
when if the error and the secret
are really-really small,
the asymptotic is of
a lattice algorithm are
still free to measure,
simply because as long
as q is polynomial,
that is sine becomes the
same, has the same sine.
It won’t change the asymptotics.
So the binary LWE does not
change the asymptotics.
However, the concrete security
could change, of course.
To convert the BDD problem
into a unique SVP problem,
so the standard way is to
use the so-called the
Kannan’s Embedding,
where I expand this mod q in
the LWE problem by rewriting as b is
equal to As plus e plus c times q,
where c is some arbitrary vector.
So the argument essentially says,
the lattice point As plus cq is
close to b up to this error vector e,
where e is a small shift.
Where I can invite
this small-shift e together with
another short amount y into
a lattice generated by a new basis,
which I called L prime.
So L prime consider for Lb,
where L is the basis for
the immediate lattice of A.
So if you look at
the multiplication Lb,
zero one and the star one,
where the star part is
the coefficients generating
the lattice point
As plus cq over there.
So L times star equals to As plus cq.
But this is a negative one
so I just ignore the sign.
So the second strategy goes
from the other direction.
the direct decoding attack,
I can rewrite the LWE problem
in terms of ISIS problems,
by multiplying the left kernel
of the matrix A over FP.
There, I will use the solver
to solve the ISIS problem.
That’s the second strategy
which sometimes it’s called the
dual attack because this is
really the dual of this sine.
So the workflow is simple.
So I take the left-kernel,
which I denoted as A perpendicular,
times As plus e. So
this part becomes zero.
Left over is A
perpendicular times e. So
this has the shape
of the ISIS problem,
where A perpendicular acts as the b.
Remember, this is going to be
a wide matrix in
the previous picture.
So the general way to solve
this ISIS problem is to
solve a CVP problem.
So first of all, we find
the arbitrary vector y such that
B times y equals to t. So there
was no requirement
on the length of y,
therefore this step
is very efficient.
Then I consider the kernel
lattices of this B,
which consist of all the vectors
x such that Bx equal to zero.
Then I will take some target point
y and then call the BDD or
CVP solver in the kernel
lattice defined by this basis.
within this kernel lattice and
close to y and that in the end,
I’ll simply subtract them.
Because v is close to y,
the subtraction should
review a short vector e,
and assume that the solution
is unique in the LWE instance.
So in this attack,
it’s similar to the previous
attack in the case that
once I did this cancellation,
only the information on e is left.
The previous decoding attack
is very similar,
where I only use the information
that e is short.
Therefore only the e
information or e is used.
This also means if I have
a very short secret or have some
special structure on the secrets,
these two attacks does not
really use that property.
In order to tackle that,
I can have another attack
which is called the
primal attack expanded matrix.
Where I rewrite out
the problem As plus e,
as A concatenated with
identity matrix that I mentioned and
times a very long vectors
co-creating with s and
e. So that does not change,
there is the way that how we
construct this set problem
has been changed.
For example, I rewrite this
problem as this one and that.
Now, the new task is to
find the short solution
As and e in the kernel
lattice of A prime.
In this case, since
the solution we are seeking
for does contain
the information on the secret,
so the information on
the secret is retained.
It’s relevant in the text.
If the asset you are not
balanced then we can
re-balanced the lattice which
is the lattice introduced
from A and AM.
All of this method we mentioned
so far some have equivalent,
but not always as you can see.
At least, the information on s
is irrelevant in this attack.
There are the four strategy which
is repeating what we mentioned
before using the dual attack.
However, it does leave
the information on the secret.
The previous dual attack
completely cancel
the information on s. However,
if we do a little bit of
modification on this attack,
we can still keep
some information on s.
the exact left kernel of A,
we can find the approximate
left kernel of this A,
such that if I multiply
them together,
they give me a short vector.
That’s the simple modification.
To keep s, we will find
A_t such that we find the axis
such that axis does not
completely cancels A.
However, it cancels A
up to a short vector y.
Here, I only require that
x and y are both small.
Otherwise, I can again
write this in ISIS form,
where I concatenate the A.
This is going to be a very kind
of wide matrix times x minus y.
If w,v is a short
solution to x and y,
then I can multiply w on top of v,
and before, this almost
cancels up my A,
except left this y,
which is this v. So I
have v times s plus w,e.
So w,e is the previous ISIS.
In the previous attack, I
But now, since I do
not fully cancel s,
but I live with some v,
so I have v times s. As
long as my v is short,
then v time s is short,
w times v,e is also short.
Furthermore, if s and e
are not balanced very similar
to the primary attack,
we can re-balance the lattice
that I constructed in this step,
to balance the solution for x,y.
These two can balance are
really the same framework,
but the y applies to primal,
this applies to the dual, our case.
Okay. The previous four strategies
only consider the lattice
reduction where in practice,
if the secret or error
comes from sparse secret,
it is already good to combine
that lattice reduction with
the combinatoric attack.
This line of research was,
I think was already in the from
the original attack into
where the user a bit
in the middle attack and
the hybrid lattice reduction and
combinatoric attack of into.
This was extended to LWE by Woodrow,
and that extends to
other variance of LWE.
a better algorithm especially
when s and e are sparse.
Giving us the combinatoric algorithm
is already good for sparse secret.
This is my personal claim that
the aforementioned four
strategies can be combined
with meet-in-the-middle
like algorithm,
although I haven’t really
fully recovered all of them.
Some of them appeared in literature,
but some of these strategies were not
combined with
meet-in-the-middle algorithms.
Maybe that could be an interesting
project to work on after this.
Okay. I will just mention once
hybrid attack which follows from
the dual and distinguishing attack
of all of our Albrecht.
Very similar to what
we described before.
Remember before, we have this
v times s_1 plus w times
recover s as a full vector,
we are going to separate
this s into two paths.
I call them _1 and s_2,
which correspond to
the left-hand side columns of A,
and the right-hand side column of A,
so I call them A_1 and A_2.
We only going in a dual attack.
I’m only going to find
the space for the dual
After that, I got this relation
where this part in the parentheses,
should be short because that’s
The actual term we
have is w times e,w.
You know product with A_2 as 2.
However, now I know what w is
because that’s from the dual of A_1.
I know what A_2 is.
I can just try different values
of s_2 and hopefully,
well my guess is correct.
If my guess is correct,
then whole thing over here,
is going to be small.
That’s why I’m saying this in
the do distinguishing
attack of Albrecht,
is dimensional and error
conversion where I
transform the problem into
a new LWE problem with
a new secret s_2,
where the samples are given by
the inner product of w times A_2.
For each guess of s_2,
I will check if the difference
of w,b minus that is short.
Alternatively, this can be done
by using a memory time trade off.
That’s the hybrid attack
on this dual thing.
>>Data tag can be rephrased
in this framework.
So given the RW problem,
it converts that into
another RW problem where
during the conversion,
I need to use the power
of the Oracle.
Then after that, I solve this problem
using some combinatoric attack,
or maybe a lateral type.
So all of them are possible, I think.
Okay. So far, I
for solving the RW,
where I kept this as a Oracle.
I didn’t really open this
the running time of this solvers.
So in this section,
I’m going to open that up,
just gave a little
bit running time on
the algorithm for solving SVP
problem and Unique SVP problem.
So the SVP Gamma problem
it tries to find the
vector we are is up
to Lambda times the shortest
vector of the lattice.
So the main tool to solve
this problem is the
[inaudible] that with
some input parameter,
which will be called the block size,
which is an integer,
which is strictly smaller than
the dimension of the devices.
Otherwise, it becomes the full SVP.
So to solve this SVP Gamma problems,
we’re going to apply a BK that
algorithm with parameter Beta.
However, the difficulty
of this problem
really depends on
this approximation factor, Gamma.
So if Gamma is really large.
So for example, is slightly more
than the substantial factor,
a polynomial time algorithm
by applying BK Beta to solve
this SVP Gamma problem.
However, in cryptography,
people usually start
this Gamma to be polynomial,
or some slides sub-national,
which is way much smaller than this.
In that case, the Beta we
need to use is really large.
The running time is
two to the some constant C times
the block size we need here.
So if Beta is about sizable,
we’re going to have
a full exponential algorithm,
where the constant C
depends on the algorithm,
the concrete algorithm we are
using either iteration or saving.
to our spatial permeability
called the uSVP Gamma problem.
So this problem is different
to the SVP Gamma problem.
In the case that the lattice,
we have a special.
So there is a promised gap
between the second shortest vector
and the first shortest vector.
So the rule of thumb is to plug in
this gap Gamma into this estimate,
and use that as the running time of
the of the Oracle for
solving uSVP Gamma.
For example, in
the very first strategy,
so we have in the decoding strategy,
I’m considering the lattice generated
by the image of A and then,
I’m going to look to solve a problem,
PTP problem which says
the AS is very close to B up
to E. So this gives me
a image likeness of dimension,
and where the gap in this lattice
is estimated by this.
By plugging this into here,
I can get the Beta,
and therefore, I can
get this running time.
So this also involves to
optimize the number of
samples I have given.
As long as we have the number
of samples given is big enough,
the optimal running time
is given by this,
and this recovers
the asymptotic formula
in the very first few slides.
Okay. A little bit more insights
on the BK, that Beta algorithm.
So given a big Beta phase,
the big Beta algorithm
smoothes over the Beta
lighter with many rounds of SVP Beta,
where it does
this continuous SVP Beta
for each block size of Beta.
If a single block is SVP reduced,
then we have this quantity
insurance where Gamma Beta
provides a constant
of dimension Beta.
It provides upper bound for
the quality of the first
vector in the basis.
On the other hand, we can
have the do SVP reduced.
Once we have all the blocks reduced,
they all satisfy this relation.
to get the quality cultural
for the very first vector compared
to the overall determinant.
So that’s how the analysis goes.
The current algorithm including
BK that slight reduction,
and self-dual because that
reduction uses a combination of
these two strategies to
guarantee the quality
of the reduced basis.
So globally, it does many tours,
and for each tour,
it moves down the basis vector
by many invokes of the SVP Beta.
So that’s the gist of
the BKZ algorithm.
So very simple because the algorithm
follows the description.
Simply assume that
this is a dimension of
lighter phase that I will simply do
SVP on block size of Beta for
each consecutive indices
starting from
one up to the n minus Beta plus one.
Then the blocks in the tail,
they are becoming smaller blocks.
So I cannot do the SVP Beta anymore.
So I will just do as
much as I can do,
SVP of size n minus
i plus 1 over there.
After each tour, the Beta is
smoothed by bringing the shorter
vector to the front.
I have a movie on that kind of stuff.
So these are the starting.
So these are the actual route
for BKZ-40 reduced basis,
where the light is
dimension is a 100.
This is the starting point of
the algorithm where I
draw the Gram-Schmidt,
the logarithm of the Gram-Schmidt
of the basis vectors.
After the very first tour,
you can see it pulls down the
very first Gram-Schmidt vectors,
and that puts up
the scene in the tail.
That if I continue the tours,
it tries to further push
out the very first vectors,
and to after the tail vectors.
So the vectors that we are
most interested in is
the very first one,
where it can see
during this procedure
So that’s the principle of this.
All right. That’s the end of BKZ-40.
relevant to the BKZ.
The first one is quantifying
the quality after BKZ,
and the second one is quantify
the time of the BKZ algorithm.
I believe which is much harder task,
so I only gave us slides for
giving some overview for that.
But quantifying the quality
for the BKZ algorithm seems to
be reaching a stage where we
have some confidence to say,
after BKZ Beta, what kind
of Beta is vector?
What kind of Beta is we can expect?
So the idea is to consider the
average behavior of the algorithm.
So although previously, we have
the upper bound estimate
for each local block,
so in cryptanalysis, we are most
interested in the average quality
of the algorithm.
So to do this,
we will substitute the upper bound of
this Hermite constant Beta by
Gaussian heuristic at W Beta.
We’ll look at behavior
of SVP in local blocks,
and that we will simulate
the behavior of tours
globally to see what is
the end quality of this.
So the asymptotic estimate
is going to be this one,
where the volume is
determined of the lattice.
But we have a better way to
decide this Hermite factor,
which is to use a simulation.
However, in the previous experiments,
it had been realized that this
average case analysis by using
Gaussian heuristic seems to
be even worse than practice.
Although it was shown that in
the study by Gama-Nguyen
that the Gaussian heuristic it
seems to be pretty accurate.
In practice, it has been found
that b_1 in the local part,
could be even smaller than
this Gaussian heuristic estimate,
and this was observed
in subsequent works of
Chen Nguyen and Ducas Yu.
To show this, I just
have some picture,
I think I can just skip this,
where the most important features
are the actual Gram-Schmidt,
which are in this red line,
and the Gaussian heuristic
which are in black.
So for average case analysis,
we should expect
this red line as long as
the block size increases
essentially maps the black line.
However, in practice, if I
increase the block size,
you can see there is
a certain converging phenomena.
However, the actual Gram-Schmidt
is in experiments are even better
than the Gaussian heuristic.
So there the intention in terms
of here to say that maybe
the lattice reduction
algorithm even works
better than the Gaussian
heuristic expected.
So it seems the average behavioral,
BKZ algorithm is even better
than the Gaussian heuristic.
So work last year,
we tried to explain this using
some stochastic models by considering
the distribution of
the lattices because
the previous estimator used
Gaussian heuristic which
is close to say that,
okay for every local lattices a
pickup the shortest vector
to be that fixed value.
So our change is really simple.
We just take the
stochastic model into
consideration by saying that okay
the lattices we have is random.
We assume that it’s random,
and that the shortest vector we have
regenerated is also
a random variable.
So to use that, we are able to have
some heuristic analysis
using some other statistics.
So after K SVP’s the
expected lattice is
shorted vector is given by
the previous one which is either
the Gaussian heuristic or
the expected value divided by
the number of runs up to 1 over Beta.
On the other hand,
this analysis says that as long
as my lattice dimension goes larger,
then this impacts goes away.
So probably this
experimental phenomenons
only happens for small block size,
and when block size
become larger and larger,
we don’t have that concern in
lattice based vector analysis.
So maybe that was just some LWE
or some explanation of
some phenomenon happen
for smaller dimensions.
Okay. The quality I mentioned,
we seems to be at stage where we
can estimates the quality
of BKZ reduced basis.
However, the time estimate
seems to be much trickier,
where in order to estimate the time,
we have to estimate
the running time for single
SVP Beta times the number of tours.
Both of these I believe they have
some controversial arguments and
not everyone agrees with each other.
In particular, again
there’s a discrepancy of
whether the local SVP
Beta cost should
be estimated using Sieving
or Pruned enumeration,
where although
this pruned enumeration
gives worst asymptotic running time,
the constant on top of
this pruned enumeration seems
and at some stage for
concrete security estimate,
this might be even
smaller than sieving.
So that’s where the main discussion
comes from I think,
as well as the number of
tours in the simplest model,
where the number of tours
is considered to be one,
where the number of local SVP
is also considered to be one,
so the overall cost is
a single local SVP Beta cost.
Well, whether this is true,
I’m not sure because it also
depends on the number of tours,
which also depends on the strategies.
I’m not sure if it can be
optimized into stage where
a single SVP Beta is enough,
but on the other hand, it seems to
provide very conservative estimate.
So maybe there are also some
alternative reduction strategies
may reduce the number of tours
or reduce the number of
reduction that we need.
Okay. So that’s pretty much all
where I’m going to just
have some questions.
Some of these are from some
of my previous slides.
The first question, which
I think is plausible
which is more extensive study
of hybrid attacks to
other be using the aforementioned
strategies because I don’t think
the other four or five strategy has
been investigated together
with this hybrid attacks,
some of these combination
could lead to a better attack.
Again, there are some gaps
between the best attack and
the best complexity reduction
resulting in various
of LWE for example,
in binary LWE with Beta errors,
there are some gaps.
As making the time of
because Beta is difficult
tasks here as well as the CV.
So one of the issue is for
protecting receiving into
higher-dimensional of course
is the memories become
a bottleneck in real-world
for large dimensions.
Could there be some better
strategies for doing Beta reduction,
this can reduce the number of tours.
The last one, how to better use
the algebraic structures enlightened
reduction for structured lattices.
So I don’t know
That’s all of my talk.
So thank you very much.
>>Questions.
>>Yes.
>>You mentioned that
for small block size,
or ECGs is a bit pessimistic
on the lengths of all five.
>>Yes. Exactly. That’s
from experimental study.
There are plenty of experiments
just to show that if
I do this because out
of small block size,
then the very first part of
the lattice is even better
than the Gaussian heuristic.
>>So I guess one way when you said
also this is appears
on larger block sizes.
>>So from this heuristic analysis,
we sees this behavior will
disappear in higher dimensions.
So that’s our conclusion
because the only difference.
So assume this part is
the expected value or
the Gaussian heuristic
and dividing out
the number of
low SVP times 1 over Beta.
So as long as Beta comes to
larger than than that
then this equals one.
>>Do you think there could
any room for like BKZ strategy
where rather than trying
to solve locally SVP-1,
you’re trying to solve
some approximate SVP?
>>Yes. I did mention that
although there are the
various which says okay,
so in the implementation
various which does not solve SVP-1,
they solve approximated quotients.
But that’s good question.
I’m sure there are
other strategies which can
probably take the
basis in a better way.
So maybe the relevant question is
the current reduction algorithm
only look at the current block,
where doing the reduction,
it does not take
the whole basis globally.
Maybe there are
some global information
the lattice reduction can take,
while doing the SVP reduction
of its single block.
So maybe that’s why I
wrote to consider. Okay?
>>Thank you.
>>So there this particular slide
where there’s a formula
with complexity in terms
of n, q, and Alpha.
>>Yes.
>>So yes, maybe
I’m confused but it seems
like with a larger q
that you actually get
like longer running time.
>>Understand in
this asymptotic over there.
Yes. So over here,
if I barely plug in log q
without any algorithm,
indeed I get lager at
cataloger, you’re right.
>>But from a learning with
errors perspective with larger q,
is expected to be less secure?
>>Yes. The optimization.
So here I used the gap
which is why if you
change that this asymptotic
will change a little bit.
So is only relevant to the standard.
>>Okay.
>>So let’s thank Shi again.
>>Thank you.