An encryption scheme is called Fully Homomorphic Encryption (FHE) scheme if it allows an unlimited number of evaluation operations on the encrypted data and resulting output is within the ciphertext space. After almost 30 years from the introduction of privacy homomorphism concept [Rivest et al. 1978a], Gentry presented the first feasible proposal in his seminal PhD thesis to a long term open problem, which is obtaining an FHE scheme [Gentry 2009]. Gentry’s proposed scheme gives not only an FHE scheme, but also a general framework to obtain an FHE scheme. Hence, a lot of researchers have attempted to design a secure and practical FHE scheme after Gentry’s work.
Although Gentry’s proposed ideal lattice-based FHE scheme [Gentry 2009] is very promising, it also had a lot of bottlenecks such as its computational cost in terms of applicability in real life and some of its advanced mathematical concepts make it complex and hard to implement. Therefore, many new schemes and optimization have followed his work in order to address aforementioned bottlenecks. The security of new approaches to obtain a new FHE scheme is mostly based on the hard problems on lattices.
deep'blog 