Given two integers, we can compute their greatest common divisor
efficiently using Euclid's algorithm. Howgrave-Graham formulated
an approximate version of this question, asking ``What if instead of
exact multiples of some common divisor, we only know approximations?''
This problem has many applications in cryptography, particularly
partial key recovery for RSA. In this talk, I will show how to extend
Howgrave-Graham's algorithm from two approximate multiples to many
approximate multiples. 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^{2/3}$ approximation algorithm for lattice basis reduction in
$n$ dimensions could be used to break these parameters.

Joint work with Henry Cohn