Fast key generation for Gentry-style homomorphic encryption

Abstract The key issue of original implementation for Gentry-style homomorphic encryption scheme is the so called slow key generation algorithm. Ogura proposed a key generation algorithm for Gentry-style somewhat homomorphic scheme that controlled the bound of the evaluation circuit depth by using the relation between the evaluation circuit depth and the eigenvalues of the primary matrix. However, their proposed key generation method seems to exclude practical application. In order to address this problem, a new key generation algorithm based on Gershgorin circle theorem was proposed. The authors choose the eigenvalues of the primary matrix from a desired interval instead of selecting the module. Compared with the Ogura's work, the proposed key generation algorithm enables one to create a more practical somewhat homomorphic encryption scheme. Furthermore, a more aggressive security analysis of the approximate shortest vector problem (SVP) against lattice attacks is given. Experiments indicate that the new key generation algorithm is roughly twice as efficient as the previous methods.