Cryptanalysis of the Smart-Vercauteren and Gentry-Halevi's Fully Homomorphic Encryption

Download Now Free registration required

Executive Summary

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.

  • Format: PDF
  • Size: 148.2 KB