Abstract

We analyze the multivariate generalization of Howgrave-Graham’s algorithm for the approximate common divisor problem. In the $m$-variable case with modulus $N$ and approximate common divisor of size $N^{\beta }$, this improves the size of the error tolerated from $N^{{\beta }^{\mathfrak{2}}}$ to $N^{{\beta }^{\left(m+\mathfrak{1}\right)∕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 ${\mathfrak{2}}^{n^{\epsilon }}$ approximation algorithm with $\epsilon <\mathfrak{2}∕\mathfrak{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 number-theoretic analogue of multivariate polynomial reconstruction, and we develop a corresponding lattice-based algorithm for the latter problem. In particular, it specializes to a lattice-based list decoding algorithm for Parvaresh-Vardy and Guruswami-Rudra codes, which are multivariate extensions of Reed-Solomon codes. This yields a new proof of the list decoding radii for these codes.

Keywords

Mathematical Subject Classification 2010

Milestones

Authors