Cryptography Reference
In-Depth Information
Example 19.7.2
Table 3 of Micciancio and Regev [
379
] suggests the parameters
(
n,m,q,σ
)
=
(233
,
4536
,
32749
,
2
.
8)
.
Lindner and Peikert [
352
] suggest (using Figure 4 and the condition
m
≥
2
n
+
with
=
128)
(
n,m,q,σ
)
=
(256
,
640
,
4093
,
3
.
3)
.
Exercise 19.7.3
Show that if one can determine
e
then one can solve LWE efficiently.
Exercise 19.7.4
Show that, when
q
is prime, LWE
≤
R
DLWE. Show that DLWE
≤
R
LWE.
We now briefly sketch two lattice attacks on LWE. These attacks can be avoided by
taking appropriate parameters. For other attacks on LWE see [
446
].
Example 19.7.5
(Lattice attack on DLWE using short vectors in kernel lattice modulo
q
.)
Suppose one can find a short vector
w
in the lattice
w
0
(mod
q
)
.
m
:
w
A
∈ Z
≡
Then
wc
we
(mod
q
). If
w
is short enough then one might expect that
we
is a small integer. On the other hand, if
c
is independent of
A
then
wc
(mod
q
)isa
random integer modulo
q
. Hence, one might be able to distinguish the LWE distribution
from the uniform distribution using short enough vectors
w
.
Note that one is not obliged to use all the rows of
A
in this attack, and so one can replace
m
by a much smaller value
m
. For analysis of the best value for
m
, and for parameters
that resist this attack, see Section 5.4.1 (especially equation (10)) of [
379
].
=
w
A
s
+
we
≡
Example 19.7.6
(Reducing LWE to CVP.) We now consider a natural approach to solving
LWE using lattices. Since we always use row lattices, it is appropriate to take the transpose
of LWE. Hence, suppose
c
,
s
and
e
are row vectors (of lengths
m
,
n
and
m
respectively)
such that
c
s
A
T
e
(mod
q
).
Consider the lattice
=
+
=
v
n
.
m
:
v
u
A
T
(mod
q
)forsome
u
∈ Z
≡
∈ Z
L
Then
L
has rank
m
and a basis matrix for it is computed by taking the (row) Hermite normal
form of the (
n
+
m
)
×
m
matrix
A
T
qI
m
where
I
m
is an
m
×
m
identity matrix. One then tries to find an element
v
of
L
that is close
s
A
T
(mod
q
).
to
c
. Hopefully,
v
=
c
−
e
≡
