On Fully Homomorphic Encryption, Approximate Lattice Problem and LWE

Abstract

First, we introduce a new concept of approximate lattice problem (ALP), which is an extension of learning with errors (LWE) and similar to the closest vector problem in lattice. Next, we present two ALP-based public key encryption schemes. Then, we construct a fully homomorphic encryption scheme (FHE) based on approximate principal ideal lattice problem with related modulus (APIP-RM), whose security depends on the hardness of solving the APIP-RM problem. Finally, we design a new fully homomorphic encryption scheme (FHE) based on approximate lattice problem with unrelated modulus (ALP-UM), whose security relies on the hardness of solving the ALP-UM problem.