[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.

I’m going to start with definition

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

about that later.

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

for your LWE problems,

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,

there are broadly three methods

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,

the running time is already

polynomial as long as

the number of samples given

is more than quadratic.

So it’s quadratic.

So that’s the current start apart.

As some of the number of samples is

slightly restricted to be

smaller than the quadratic,

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.

So this already becomes

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

already substantial.

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

and error trade off.

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

already logged in

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

does not really take advantage

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,

probably you follow that on.

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 that’s the task.

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.

So instead of finding

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.

Instead of having

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.

This will return to me a vector v

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.

Instead of finding

the exact left kernel of A,

we can find the approximate

left kernel of this A,

such that if I multiply

them together,

instead of getting zero,

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

already have w,e over here.

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.

Sometimes, it leads to

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

e. Instead of completely

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

for A_1 instead of A.

After that, I got this relation

where this part in the parentheses,

should be short because that’s

exactly what we had before.

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

only talked about the strategies

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

are admitted before,

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,

then we already have

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.

The previous problem leads

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.

We can link them together

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

is gradually being put down.

So that’s the principle of this.

All right. That’s the end of BKZ-40.

There are two tasks

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.

Where the second task,

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

to be gradually decreasing,

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

the answer for this one.

That’s all of my talk.

So thank you very much.

>>Questions.

>>Yes.

>>You mentioned that

for small block size,

your misbehavior where the Gaussian

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

there are already

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.