Attack on Fully Homomorphic Encryption over the Integers

Abstract

Recently, many fully-homomorphic encryption schemes have been constructed. However, the issue of the security of these fully homomorphic encryptions has not been carefully studied. By using lattice reduction algorithm, we firstly present an attack on the fully homomorphic encryption based on approximate GCD over the integers. Our result shows that the FHE in [4] is not secure for some parameter settings. Then, we define approximate matrix GCD problem, which is a generalization of approximate GCD. Finally, we construct an improvement FHE scheme based on approximate matrix GCD to avoid the lattice attack in this paper.