Cryptography Reference
In-Depth Information
M
1
/
3
In other words, if
d
=
2 then it is sufficient that
X
≈
to find the small solution
M
1
/
6
. This is the result of
Hastad. Of course, LLL often works better than the worst-case bound, so small solutions
x
0
may be found even when
x
0
does not satisfy the condition of the Theorem.
using the above method. If
d
=
3 then it is sufficient that
X
≈
=
Example 19.1.6
Let
M
10001 and consider the polynomial
x
3
10
x
2
F
(
x
)
=
+
+
5000
x
−
222
.
One can check that
F
(
x
) is irreducible, and that
F
(
x
) has the small solution
x
0
=
4 modulo
<M
1
/
6
M
. Note that
|
x
0
|
so one expects to be able to find
x
0
using the above method.
Suppose
X
=
10 is the given bound on the size of
x
0
. Consider the basis matrix
M
0
0
0
0
MX
0
0
B
=
.
MX
2
0
0
0
−
5000
X
10
X
2
X
3
222
Running LLL on this matrix gives a reduced basis, the first row of which is
(444
,
10
,
−
2000
,
−
2000)
.
The polynomial corresponding to this vector is
20
x
2
2
x
3
.
G
(
x
)
=
444
+
x
−
−
Running Newton's root-finding method on
G
(
x
) gives the solution
x
0
=
4.
19.1.2 The full Coppersmith method
The method in the previous section allows one to find small roots of modular poly-
nomials, but it can be improved further. Looking at the proof of Theorem
19.1.5
one
sees that the requirement
for s
uccess is essentially det(
L
)
<M
n
(more precisely, it is
2
d/
4
M
d/
(
d
+
1)
X
d/
2
<M/
√
d
1). There are two strategies to extend the utility of the
method (i.e., to allow bigger values for
X
). The first is to increase the dimension
n
by
adding rows to
L
that contribute less than
M
to the determinant. The second is to increase
the power of
M
on the right hand side. One can increase the dimension without increasing
the power of
M
by using the so-called “
x
-shift” polynomials
xF
(
x
)
,x
2
F
(
x
)
,...,x
k
F
(
x
);
Example
19.1.7
gives an example of this. One can increase the power of
M
on the right hand
side by using powers of
F
(
x
) (since if
F
(
x
0
)
+
0(mod
M
) then
F
(
x
0
)
k
0(mod
M
k
)).
≡
≡
Example 19.1.7
Consider the problem of Example
19.1.6
. The lattice has dimension 4 and
determinant
M
3
X
3
. The condition for LLL to output a sufficiently small vector is
2
3
/
4
M
3
X
6
1
/
4
M
√
4
,
≤
