Paper 2011/114

Fully Homomorphic Encryption, Approximate Lattice Problem and LWE

Gu Chunsheng


In this paper, we first introduce a new concept of approximate lattice problem (ALP), which is an extension of learning with errors (LWE). Next, we propose two ALP-based public key encryption schemes. Then, we construct two new fully homomorphic encryption scheme (FHE) based on respectively approximate principal ideal lattice problem with related modulus (APIP-RM) and approximate lattice problem with related modulus (ALP-RM). Moreover, we also extend our ALP-RM-based FHE to the ALP problem with unrelated modulus (ALP-UM). Our work is different from previous works in three aspects: (1)We extend the LWE problem to the ALP problem. This ALP problem is similar to the closest vector problem in lattice. We believe that this problem is independent of interest. (2)We construct a new FHE by using a re-randomizing method, which is different from the squashing decryption in previous works. (3)The expansion rate is merely O(k) with k a security parameter in Our FHE, which can be improved to O(logk) by using dimension reduction [BV11], whereas all previous schemes are at least O(k*logk) [BV11, Gen11, LNV11]. Our method can also decrease a factor k of the expansion rate in their schemes.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Fully Homomorphic EncryptionApproximate Lattice ProblemApproximate Principal Ideal Lattice ProblemLWEApproximate GCDInteger Factoring
Contact author(s)
guchunsheng @ gmail com
2011-07-04: last of 10 revisions
2011-03-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Gu Chunsheng},
      title = {Fully Homomorphic Encryption, Approximate Lattice Problem and LWE},
      howpublished = {Cryptology ePrint Archive, Paper 2011/114},
      year = {2011},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.