Cryptography Reference
In-Depth Information
We now mention the case when
b
=
b
(in other words,
b
is known exactly). The natural
approach is to consider the polynomial
F
(
x
)
=
a
+
x
, which has a small solution to the
equation
F
(
x
)
≡
0(mod
d
)forsome
d
|
b
. Howgrave-Graham applies the method used in
Section
19.4.2
to solve this problem.
Theorem 19.6.7
(Algorithm 12 and Section 3 of [
269
]) Let
0
<α<
1
and β<α
2
. There
is a polynomial-time algorithm that takes as input a,band outputs all integers d>b
α
such
that there exists an integer x with
<b
β
and d
|
x
|
|
(
a
+
x
)
and d
|
b.
19.7 Learning with errors
The learning with errors problem was proposed by Regev. There is a large literature on
this problem; we refer to Micciancio and Regev [
379
] and Regev [
446
] for background and
references.
with
m>n
.
1
Definition 19.7.1
Let
q
∈ N
(typically prime),
σ
∈ R
>
0
, and
n,m
∈ N
Let
)
n
.The
LWE distribution
is the distribution on (
)
m
×
n
)
m
corre-
s
∈
(
Z
/q
Z
Z
/q
Z
×
(
Z
/q
Z
sponding to choosing uniformly at random an
m
×
n
matrix
A
with entries in
Z
/q
Z
and a
length
m
vector
c
≡
A
s
+
e
(mod
q
)
where the vector
e
has entries chosen independently from a discretised normal distribution
2
on
with mean 0 and standard deviation
σ
.The
learning with errors
problem (
LW E
)
is: given (
A,
c
) drawn from the LWE distribution to compute the vector
s
.The
decision
learning with errors
problem (
DLWE
)is:given
A
as above and a vector
c
Z
)
m
to
determine whether (
A,
c
) is drawn from the uniform distribution or the LWE distribution.
∈
(
Z
/q
Z
It is necessary to argue that LWE is well-defined since, for any choice
s
,thevalue
A
s
(mod
q
) is a possible choice for
e
. But, when
m
is sufficiently large, one value for
s
is much more likely to have been used than any of the others. Hence, LWE is a maximum
likelihood problem. Similarly, DLWE is well-defined when
m
is sufficiently large: if
c
is
chosen uniformly at random and independent of
A
then there is not likely to be a choice for
s
such that
c
−
c
A
s
(mod
q
).
We do not make these arguments precise. It follows that
m
must be significantly larger than
n
for these problems to be meaningful. It is also clear that increasing
m
(but keeping
n
fixed) does not make the LWE problem harder.
We refer to [
379
] and [
446
] for surveys of cryptographic applications of LWE and
reductions, from computational problems in lattices that are believed to be hard, to LWE.
Note that the values
m
,
q
and
σ
in an LWE instance are usually determined by constraints
coming from the cryptographic application, while
n
is the main security parameter.
−
A
s
(mod
q
) is significantly smaller than the other values
c
−
1
For theoretical applications one should not assume a fixed number
m
of rows for
A
. Instead, the attacker is given an oracle that
outputs pairs (
a
,c
) where
a
is a row of
A
and
c
=
as
+
e
(mod
q
).
In other words, the probability that
e
i
is equal to
x
∈ Z
is proportional to
e
−
x
2
/
(2
σ
2
)
.
2