Video summary
This presentation introduces a significant cryptographic work exploring the quantum equivalence between two fundamental lattice problems: Learning With Errors (LWE) and Short Integer Solution (SIS). The speaker outlines the foundational concepts of using superpositions over vectors in $\mathbb{Z}_Q$ to define new quantum variants of these classical challenges. Specifically, SLWE is defined as a problem where one must find a secret vector given access to a quantum state representing an entire "ball" of noisy samples rather than a single point, while ICISIS involves finding the superposition of all short vectors satisfying specific linear constraints within a coset lattice. The core argument establishes that these new problems are not merely theoretical constructs but offer robust reductions between them and their classical counterparts, effectively bridging the gap with improved resilience against solver errors compared to previous methods like Regev's reduction.
The central contribution of this research is demonstrating a reverse reduction chain where SLWE can be reduced to ICISIS, which in turn reduces to SIS, thereby proving that solving these quantum variants allows for attacks on classical problems even when solvers are imperfect. Unlike earlier reductions that required perfect LWE or SICIS solvers and suffered from error amplification, this new framework preserves the probability of failure throughout the reduction process. This robustness is achieved by utilizing an ICISIS solver to manipulate quantum states involving cosets of dual lattices; specifically, the method involves applying a Quantum Fourier Transform to expand the state space into giant balls representing all short vectors in the ambient space, followed by operations that isolate and erase specific registers using unitary transformations derived from the ICISIS solver.
To validate the practicality of these theoretical reductions, the speaker presents an adaptation of Regev's folklore SIS solver for a regime where the modulus is a power of two and vector coefficients are binary. By ensuring this adapted solver satisfies necessary conditions regarding solution uniformity and randomness extractability, it becomes possible to construct super-polynomial time algorithms for SLWE that match or exceed the performance of known classical attacks by Bai et al. The analysis reveals that while existing approaches like those from Crypto 2026 rely on complex tree-like structures involving repeated quantum state assembly and measurement (a "Cooperberg approach"), this new reduction captures such complexity within a single ICISIS solver, simplifying the overall quantum circuit to primarily involve Quantum Fourier Transforms and classical operations performed in superposition.
The talk concludes by highlighting two open questions for future research: extending these results beyond moduli that are powers of two to more general cases, and investigating whether the stringent conditions on the SIS solver—specifically solution uniformity and randomness extractability—can be relaxed without compromising security or efficiency. These inquiries aim to further solidify the quantum equivalence between LWE and ISIS families across a broader spectrum of cryptographic parameters, potentially leading to even stronger connections between classical lattice hardness assumptions and their quantum analogues.
Read the full video transcript
All right, so I'm going to talk about
this work named on the quantum
equivalence between SW and ISIS. So this
is a joint work between Andre Chailloux
and myself done at the Cosmic Team of
Inria Paris.
Um well, first I'm going to briefly talk
about the quantum states, briefly
describe the quantum states that I'm
going to use in this talk. So these will
be superpositions of vectors over ZQ
where Q is any positive integer.
And um and they will have this shape
here where where X here is the vectors
that are in superposition and for each X
we have the corresponding amplitude f of
x. So f is the amplitude function and in
this talk it will have only
uh real values
between 0 and 1. And there are two
operations that we do a lot in this
talk. The first one is measuring.
So when I measure such a state, what I
get is a vector x with probability f of
x squared. And when I apply a quantum
transform on such a state,
it
turns it into the same state except that
the
um the the the the the amplitude
function f is turned into f of hat which
is the Fourier transform of f.
Now sometimes I will need to use uh
complex amplitudes, in which case I will
add this complex factor here omega Q to
the x.y where y can be any vector and
omega Q is the
Fourier coefficient in ZQ.
So it doesn't change anything in the
measurement probabilities when I do
that, but it does change the quantum
Fourier transform behavior,
um meaning that it will shift the uh the
the the amplitude by this vector y.
All right, so now that we have done
these uh quantum preliminaries, we can
um we can describe the two classical
problems that we will investigate in
this talk. So the first one is the
learning with errors problem, LWE, which
basically asks to solve a noisy linear
system of of equations. So, you're given
a matrix A and a noisy system ATS plus
E, where S is the secret vector here
that is chosen at random. And E is a
noise vector that is sampled um
uh depending on from a distribution
depending on F, where F is the a
parameter of the problem.
And typically typically it will have it
will have a small uh weight.
And the goal is to find S.
Um so, we can see this problem as uh
lattice problem, where you're given
uh this lattice defined by A, and um and
there is a random point here of the
lattice that is chosen.
And what you're given is a point that is
not in the lattice, but close to this
random point within this this red ball
here. And you need to find the the
secret point.
So, the second problem is the short
integer solution problem,
um SIS or ISIS for the inhomogeneous
version.
So, in the inhomogeneous version, you're
given um
a matrix A and a target vector Y, and
you're asked to find
X such that AX is equal to Y, and also X
is short. So, here we will say that X is
short is if X is inside this set T,
which is a parameter of the problem.
And but typically it means that
it is chosen so that X is a short
vector,
and uh we can also see it as a lattice
problem, where you're given
um a dual lattice here, the dual of the
lattice defined by A.
And um
and and it's actually shifted uh
lattice, so it's a codual lattice
defined by the shift Y.
And you're asked to find simply a small
vector in this lattice.
So, there is also a homogeneous version
of this problem, in which the vector Y,
the target vector, is is set to zero.
In which case you're not given a code
lattice, but only the dual lattice.
So, we're going to use the Regev
reduction in this work, and the Regev
reduction we define it as a reduction
that maps
the short integer solution to the
learning with error. So,
meaning that if you have a
LWE solver, then you can use it to
construct an SIS solver.
All right. So, now I'm going to
summarize the Regev reduction, give you
the the
main idea.
So, this reduction again, it you're like
you're given an LWE solver and you need
to find the corresponding SIS problem.
So, Regev he showed that when you're
given an LWE solver, you can prepare
this state here. That's the main idea of
the algorithm. So, this state here is a
dual superposition, it's a double
superposition, sorry.
Um, and we will break it down. So, first
let's consider this inside
superposition, the one over E. So, the
the vectors here, they are vectors
uh, ATS plus E that are LWE samples. So,
we can think of these vectors, so these
points are all the points in inside this
this red ball where the center is the
ATS here.
And because we have this superposition,
we
have actually like this superposition
over E corresponds to a whole ball here.
A superposition of all the points in the
ball.
And now because we have actually a
superposition over also all the secret
vectors S,
this whole state corresponds of the
superposition of all the points that are
in all these red balls.
And Regev showed that if you apply
quantum Fourier transform on this state,
what you get is this state here, which
is the superposition of all the short
vectors in
um,
in the dual lattice. So here we
importantly we took
F hat such that F hat is the indicator
on T.
So this state is exactly like exactly
that the superposition of all these
short vectors and these short vectors
are actually the solution to the SIS
problem. So we automatically have when
we measure the state a valid SIS
solution and we are done.
So now Chen and Landry in 2021 they
broke down this tradition and they
defined two families of states. The
first one are the
psi S states here. So these states where
each one correspond to one of these ball
and the second one
are these phi Y states. Here we have
only phi zero so phi Y is the
superposition of all the short vectors
in the code dual lattice defined by Y.
So here
because we are in the homogeneous
homogeneous case we don't have a
collective reason have that
the dual lattice.
That's why it's it's phi zero.
And they define two of these problems
SLWE and CLWE that I'm going to define.
So SLWE you can see it as the quantum
equivalent of
or quantum variant of LWE.
So it's
it is very similar but instead of being
given a point here inside this red ball
you're given the whole red ball. So the
superposition of all the possible
points.
And it's very easy to note that SLWE
reduces to to LWE because if you measure
the state what you get is one ATS plus E
one SLW and LWE sorry sample
with probability F of E squared which is
exactly the same distribution as the
classical LWE.
And now the second quantum problem is
the IC LWE problem which is the quantum
variant of
Einsize.
So uh, instead of being asked to give
one vector, one short vector in the code
word that is defined by Y, you're asked
to, uh, give the superposition of all
these short vectors, which corresponds
to this uh, superposition here where
each of these blue little ball, little
dots are one of the, uh, each one of
these is, uh, a valid vector for the
ISIS problem.
And again, like the, uh, ISIS problem,
there is a homogeneous version of it,
um, which we call CLWE, and this is this
is the one that actually got defined by
Chen and Sundaram, and we defined the
inhomogeneous version. And in this
homogeneous version, you simply have
like, you set Y is equal to zero.
Um, so Chen and Sundaram, they, they
refined the reduction using these new
problems. They said that, uh, the SIS
problem reduces to CLWE, which itself
reduces to SLWE, which reduces to LWE.
So, they, they provided this chain of
reduction, and now that we have it, it's
quite nice because we can,
um,
it means that we can use an SLWE solver
to attack the corresponding SIS problem.
But then we ask the following question,
can we do the opposite? Can we,
uh, can can we have like this reverse
reduction, a reduction from SLWE to CLWE
first, and then one from CLWE to SIS?
And we answer this question
affirmatively, or almost, because we
showed that actually the right way of
considering these problems and the
relations between them is to consider
the inhomogeneous versions of these
problems. So, ICLWE and ISIS instead of
CLWE and SIS. And once we have done done
done that, we can show that first, the
forwards reductions, the one that
existed before, they are still there,
um, still exist, and but then we also
have the backwards reduction, we have
the reverse reduction that we're
interested in.
So, we have a reduction from SLWE to
ICLWE and one from ICLWE to ISIS.
Although this
last one here
we for this last one we need to have a
few conditions on the ice ISIS solver
that we use. I will mention this later.
I will describe this later.
Also one nice thing about our new
reductions is is that now they're robust
to noise in the solver.
Meaning that for the original reduction,
the Reg F1 and the Chen and Re 1
they needed to have an SLWE solver that
was
perfect.
So, if
if the SLWE solver had
maybe even a negligible probability of
error, this error could completely blow
up in the reduction making the reduction
feasible. So, they had to proceed to a
careful analysis of so, depending on the
case. So, they they needed to do a
careful analysis of the of of the of the
noise and how it evolves in the
reduction.
So, for us we don't really have that
because we have in general we have a
general way to say that we if we have a
epsilon
probability of failure in the reduction,
then in the in the SLWE solver then this
epsilon probability of failure will be
somehow conserved
in the reduction and and then it will
translate to an
almost epsilon probability of failure
for the ISIS
for the SLWE solver.
All right. So, now we ask a second
question
which is regarding the difference
between SLWE and LWE.
So, we wonder whether we can now that we
have this reverse reduction use it
to attack SLWE. We want to find an ISIS
solver that allows us to attack SLWE in
such a way
what we are really interested in
in in such a way that this algorithm for
SLWE is better than any algorithm for
SLWE that that we know so far.
Um and actually this already have been
um answered positively by by Bio et al.
Uh last year at Crypto.
They presented an algorithm for SLWE and
showed that um that that this algorithm
outperform any LWE algorithm in this
regime. Uh hinting that maybe SLWE is
easier than LWE in this regime. And um
and thanks to our
to our reduction we we recover these
results
uh in what I would call a simpler or
actually much less quantum way and I
will
um I will tell what I mean by that uh
later in the talk.
For now what I will explain is how we do
uh these two reductions here, these two
backwards reductions. I won't uh
describe the two forwards reduction
because like this one is is um very
trivial, the one from ICIS to ICISW. And
the one from ICISW to SLWE is
essentially the same as the one of
Reguef. We just have to change a few
things to to make it work
uh and of course to to do a careful
analysis to show that the
um
the the the probability of failure in
the SLWE solver
uh is preserved.
All right.
Um
So I will I will start with a reduction
from SLWE to to ICISW.
So we need to solve SLWE so we need to
uh to find a secret vector um
ATS S
um given this ball here given this
superposition this SLWE state. And
[snorts] to do that we are given an
ICISW solver meaning that we are given
the possibility of preparing um
all these this state here so the
superposition over all the short vectors
in the code your lattice defined by Y
for every possible Y.
So how it works is that we show that if
we have like this um SLWE state
this red ball and we perform a QFT on
it, we obtain this
giant blue ball, which is the
superposition of all the short vectors
in the whole space, not in the codual
lattice or anything in in the whole
space. Um so, which is this state here
and there is a a phase here, complex
phase that we'll not uh I will not
describe uh for the moment. And we use
the fact that we can partition the whole
space into um into all the different
cosets of of the dual lattice to express
the states as this one here, which is
the superposition over all the phi y
uh states.
And I recall phi y is the superposition
of all the short vectors, but this time
of the codual lattice defined by y.
And now that we have expressed this this
way, what we can do is to um obtain the
vector y corresponding to each one of
these phi y. And we will do that simply
by left multiplying this state here phi
y by A.
And it works because uh all the vectors
in phi y, they are vectors in the codual
lattice defined by y, meaning that A
times X is equal to uh to y for all
these vectors X.
So, we have this state and what we want
to do next is to erase these phi y uh
states.
And to do this, we will use the um ICLWE
solver. So, recall that this ICLWE
solver was given was giving us uh a
mapping from ket y ket 0 to ket y ket
phi y.
And with it, we can construct
efficiently the reverse uh solve the
reverse unitary. So, the one that maps
in the opposite way, so ket y ket phi y
to ket y ket 0. So, now we just have to
swap these two registers, apply this U
dagger, and it will zeroize this phi y
register. So, now that we have zeroizing
zeroized it, we can it's not entangled
anymore, we can just erase it, remove
it, and we are left with this state
here, which is exactly the quantum
Fourier transform of S. So, now we just
perform an inverse quantum Fourier
transform, and we recover S.
And then it's done.
So, now let's let's look at the the
second part of the reduction, so the
part from ICLWE to ISIS, the conditional
part.
So, the goal here is to solve the I ISIS
ICLWE problem, so we are given matrix A
and um
a target vector y, and we need to
prepare actually for all these possible
y's, we need to prepare um
the this phi y state here, which is the
superposition of all the short vectors
in the codeual lattice defined by y.
And to do that, we are given an I ISIS
solver, so we are given some solver A,
such that given an ISIS instance A y and
some random coin r,
um it outputs some vector x here. So,
for simplicity, we will assume
uh in on this slide that x is always a
good solution, meaning that x is in the
codeual lattice, meaning that A times x
is equal to y, and also that x is short,
meaning that x is in T, or equivalently,
f hat of x is nonzero, because again we
took f hat to be the indicator on the
set T.
So, because it's a conditional
reduction, we need two additional
assumptions on the solver. The first one
is called solution uniformity, and this
assumption says that uh for each
valid solution x, there is one and there
is only one random coin that we call RX
mapping to this X.
And the second one in the is the
randomness extractability, it means that
this RX can be recovered from
from the solution X.
So this means that
essentially we have like an efficient
one-to-one
mapping between
X and the associated random coin RX.
And this gives us this unitary here,
mapping get X get zero to get X get RX.
And with that we'll be able to to solve
the problem. So first we start by
preparing a superposition over all the
random coins R.
Next we apply the ISI solver. So what we
get is this state here.
And these
here these vectors here are
all the valid solution to the problem.
So we can rewrite this state as this
one.
Um
where where we we just sum over all the
valid solution X of the problem and we
have here the
the R register becomes RX, the
associated random coin.
And now what we want to do is to remove
this RX register and then we'll do the
same as before, we'll simply use the
reverse unitary here.
So we swap X and RX and we use the
reverse unitary mapping
get X get RX to get X get zero.
And this erase the get zero the get RX
register leaving us with only this state
here, which is exactly phi Y the
superposition of all short vectors in
the code Y lattice defined by Y.
And we're done.
So these two part of the reduction gives
us the following theorem, a bit
simplified.
Given a solution uniform and randomness
extractable extractable ISI solver
running in time T, we can construct a an
SLWE solver running in time polynomial
in T.
So, now the question that one can ask is
whether these two conditions are too
strong. Like,
it's too easy to to to do the reduction
when we have these conditions and it's
still practical.
Um and actually we show that it is
practical.
Um and we we show it by by picking a
folklore SI solver
from Reguev
and it works in a regime where the
modulo Q is a power of two, the matrix A
is a very very wide matrix, and the
shortness condition says that
vector X is short if every coefficient
of X is zero or one.
And this
SI solver runs in in super polynomial
time and we adapt it
um to make it an ISI solver still
running in super polynomial time that is
solution uniform and randomness
extractable. And now that we have these
two conditions fulfilled, we can plug it
into the uh reduction and this
automatically yields a super polynomial
time algorithm for SLWE.
And this recovers actually the best LWE
attack known in this regime, the one I
mentioned at the beginning of the talk
from from Bai et al. from last year. And
um and again I said that it's
done in a much less quantum way and what
I mean by that is that this Bai et al.
algorithm uses a Cooperberg approach to
to to to to solve that problem, meaning
that they um
they they take a lot of states, they
assemble them, they perform some quantum
operation, and then they measure uh them
or they measure some
uh they they they they make a
measurement on the state that they have,
and it
it produces a new state that has better
properties than the one they had uh at
the beginning.
And they do that a lot of time. And by
doing that, they have like a lot of
these new quantum states that they can
reassemble again, uh perform new
measurements again, and so on and so
forth, until in the end they have like
one state that they really want that
have enough property so that they can
extract X from it.
And what we do with our reduction is
that all this complexity, this tree-like
uh structure, we we we we capture it. I
mean, it is captured by the I ISI
solver. So, the ISI solver has this tree
uh like structure, but it's only
classical operations this time. And as
quantum operations, we only have quantum
Fourier transform and um uh uh um
classical operations made in
superposition, which is simpler uh
quantum quantum gates, quantum
operations. So, that's what I mean by
less quantum.
And I will finish this talk by two open
questions. So, the first one is
regarding the ISI solver that we that we
showed. So,
we we wonder whether it's possible to to
have it for a more general moduli, uh
not only powers of Q.
Powers of two, sorry.
And the second question is whether we
can relax the conditions on the SIS
solver.
Um so, this solution and informity and
this randomness extractability, whether
we can relax them and if yes, how much.
Uh and with that, I thank you for your
attention.