Cryptanalysis of Homomorphic Encryption Schemes based on the Aproximate GCD Problem

Economies of scale make cloud computing an attractive option for small and medium enterprises. However, loss of data integrity or data theft remain serious concerns. Homomorphic encryption which performs computations in the encrypted domain is a possible solution to address these concerns. Many partially homomorphic encryption schemes that trade off functionality for lower storage and computation cost have been proposed. However, not all these schemes have been adequately investigated from the security perspective. This paper analyses a suite of such proposed schemes based on the hardness of the Approximate GCD problem. We show that two of these schemes are vulnerable to the Orthogonal Lattice attack. The execution time of the attack is a function of various parameters including message entropy. For the recommended set of parameters, the execution time of the attack is no greater than 1 day on a regular laptop.