Cryptography Reference
In-Depth Information
Boneh, Durfee and Howgrave-Graham [
74
] considered using Coppersmith's method to
factor integers of the form
N
p
r
q
when
r
is large. They observed that if one knows
r
and an approximation
p
to
p
then there is a small root of the polynomial equation
=
x
)
r
0(mod
p
r
)
=
(
p
+
≡
F
(
x
)
and that
p
r
is a large factor of
N
. One can therefore apply the technique of Section
19.4.2
.
The algorithm is to repeat the above for all
p
in a suitably chosen set. An analysis of the
complexity of the method is given in [
74
]. It is shown that if
r
≥
log(
p
) then the algorithm
=
log
2
(
p
) then the algorithm is asymptotically
faster than using the elliptic curve method. One specific example mentioned in [
74
] is that
if
p,q
runs in polynomial-time and that if
r
2
512
and
r
p
r
q
should be factored more quickly by their method
≈
=
23 then
N
=
than with the elliptic curve method.
When
r
is small it is believed that moduli of the form
N
p
r
q
are still hard to factor.
=
2
768
For 3076 bit moduli, taking
r
=
3 and
p,q
≈
should be such that the best-known
attack requires at least 2
128
bit operations.
Exercise 19.4.11
The integer 876701170324027 is of the form
p
3
q
where
|
p
−
5000
|
<
10. Use the method of this section to factor
N
.
19.4.4 Chinese remaindering with errors
Boneh [
70
], building on work of Goldreich, Ron and Sudan, used ideas very similar to
Coppersmith's method to give an algorithm for the following problem in certain cases.
Definition 19.4.12
Let
X,p
1
,...,p
n
,r
1
,...,r
n
∈ Z
≥
0
be such that
p
1
<p
2
<
···
<p
n
and 0
n
be an integer. The
Chinese remaindering
with errors problem
(or
CRT list decoding problem
) is to compute an integer 0
≤
r
i
<p
i
for all 1
≤
i
≤
n
.Let1
≤
e
≤
≤
x<X
(if it exists) such that
x
≡
r
i
(mod
p
i
)
for all but
e
of the indices 1
≤
i
≤
n
.
Note that it is not assumed that the integers
p
i
are coprime, though in many applications
they will be distinct primes or prime powers. Also note that there is not necessarily a
solution to the problem (for example, if
X
and/or
e
are too small).
Exercise 19.4.13
A naive approach to this problem is to run the Chinese remainder algo-
rithm for all subsets
S
e
). Determine the complexity
of this algorithm. What is the input size of a Chinese remainder with errors instance when
0
⊆{
p
1
,...,p
n
}
such that #
S
=
(
n
−
≤
r
i
<p
i
? Show that this algorithm is not polynomial in the input size if
e>
log(
n
).
[
x
] such that
all solutions
x
to the Chinese remaindering with errors problem instance are roots of
F
(
x
)
over
The basic idea of Boneh's method is to construct a polynomial
F
(
x
)
∈ Z
=
i
=
1
p
i
and let 0
Z
. This is done as follows. Define
P
≤
R<P
be the solution to
the Chinese remainder instance (i.e.,
R
≡
r
i
(mod
p
i
) for all 1
≤
i
≤
n
). For an integer
x
