Approximate Greatest Common Divisor Lattices

Abstract

We will consider the use of lattices and the LLL algorithm to find the Approximate Greatest Common Divisor of a collection of integers.  We will then discuss the 2009 cryptosystem “Fully Homomorphic Encryption over the Integers” (van Dijk et al) which is based on the Approximate Greatest Divisor problem, analysing its security justification by considering how to estimate the lengths of vectors in a random lattice.