Cryptography Reference
In-Depth Information
The same algorithm finds any integer within X of V that has a suciently
large common divisor with N. One does not need the integer tobethe divisor.
This generalized perspective did not appear in [
24
], [
25
], [
40
], or [
41
], but did
appear in papers a few years later, as discussed below.
For comparison, the problem of decoding Reed{Solomon codes is the problem
of finding a polynomial f no larger than X = x
nt1
sharing many values
with a received polynomial V (interpolated from the received word); i.e., the
problem of nding a polynomial (namely V f) that is within X of V and
that has a large common divisor with (x
1
)(x
n
). Except for a trivial
replacement of integers with polynomials, this problem is a special case of the
problem stated in the previous paragraph, and the decoding algorithm displayed
in this section|correcting approximately n
p
n(nt 1) errors|is a special
case of the Howgrave-Graham algorithm.
The first announcement of this decoding effectiveness was by Guruswami and
Sudan in [
35
] in 1998. With hindsight it is easy to see that [
35
] constructs the
same lattice as Howgrave-Graham, finds the same short vector Q in the lattice,
and finds the same roots of Q. Like Coppersmith, and unlike Howgrave-Graham,
[
35
] identifies the lattice through linear constraints. Unlike Coppersmith, [
35
]
states these constraints locally: the lattice is exactly the set of polynomials of
degree below ` that vanish to multiplicity at least k at various points. This local
perspective allowed Guruswami and Sudan to generalize, varying multiplicities
separately at each point; but this generalization is not necessary for any of the
decoding problems that I am considering, and it makes the algorithm very slow.
[
35
] uses linear algebra to solve a large two-dimensional interpolation problem,
finding a short vector Q in the specified lattice; it is much more ecient to first
solve a simpler one-dimensional interpolation problem (computing V ), and then
write down basis vectors for the same lattice (namely A
k
, A
k1
F, etc.).
Boneh in [
14
], motivated by the Guruswami{Sudan results, stated a CRT list-
decoding algorithm with quantitatively analogous error-correcting capabilities.
Boneh also stated an algorithm for the more general problem of finding any
polynomial value having a large gcd with N; this obviously includes the multiple-
of-N problems and the divisor-of-N problems. The algorithm in [
14
] constructs
the same lattice as the Howgrave-Graham algorithm (in the same way), finds
the same Q, and finds the same roots; the only difference is that the Howgrave-
Graham algorithm throws away more of the outputs. The very large overlap
between the algorithms was not pointed out in [
14
].
In 2003 I posted the first draft of a survey paper [
9
] giving a unified algorithm
statement for univariate polynomials over Q. I showed that a unified parameter
optimization produced, as special cases, the quantitative results that had been
obtained by Coppersmith, Howgrave-Graham, Boneh, et al. for various applica-
tions. I took a slightly broader perspective, allowing a large gcd for polynomial
values onrational inputs, although at the time I did not see any way to use this
extra generality; subsequent applications include [
54
], [
10
], and [
20
].
I discussed CRT decoding in [
9
, Section 7], and said that replacing Q with a
rational function eld in the same algorithm would decode Reed{Solomon codes
