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
Search WWH ::




Custom Search