Tenth Algorithmic Number Theory Symposium ANTSX

Approximate common divisors via lattices
Henry Cohn and Nadia Heninger
Abstract: We analyze the multivariate generalization of HowgraveGraham's
algorithm for the approximate common divisor problem. In the
mvariable case with modulus N and approximate common divisor of
size N^beta, this improves the size of the error tolerated from
N^{beta^2} to N^{beta^{(m+1)/m}}, under a commonly used
heuristic assumption. This gives a more detailed analysis of the
hardness assumption underlying the recent fully homomorphic
cryptosystem of van Dijk, Gentry, Halevi, and Vaikuntanathan. While
these results do not challenge the suggested parameters, a
2^{n^{epsilon}} approximation algorithm with epsilon<2/3
for lattice basis reduction in n dimensions could be used to break
these parameters. We have implemented the algorithm, and it
performs better in practice than the theoretical analysis suggests.
Our results fit into a broader context of analogies between
cryptanalysis and coding theory.
The multivariate approximate common divisor problem is the
numbertheoretic analogue of multivariate polynomial
reconstruction, and we develop a corresponding latticebased
algorithm for the latter problem. In particular, it specializes to
a latticebased list decoding algorithm for ParvareshVardy and
GuruswamiRudra codes, which are multivariate extensions of
ReedSolomon codes. This yields a new proof of the list decoding
radii for these codes.
Files available: paper (PDF)
XHTML 1.1 valid, CSS valid