Cryptanalysis of the Smart-Vercauteren and Gentry-Halevi's Fully Homomorphic Encryption
In this paper, the authors first analyze the security of the fully homomorphic encryption schemes based on principal ideal lattice in [SV10, GH11] by using block lattice reduction algorithm. The result implies that their schemes are insecure for lattice dimensions n=2048, and even for n=8192 if they suppose the random assumption and the geometric series assumption of [Sch03] for a lattice basis. If they suppose the average-case behavior of LLL in [NS06], then their schemes are also insecure for lattice dimension n less than 6000. Moreover, they further analyze how to find the small generator of a principal ideal lattice for the practical parameters in their schemes.