Towards an efficient LWE-based fully homomorphic encryption scheme

The security of most early fully homomorphic encryption schemes was based on the hardness of the Learning with Errors (LWE) problem. These schemes were inefficient in terms of per gate computations and public-key size. More efficient schemes were later developed based on the hardness of the Ring-LWE (RLWE) problem. While the hardness of the LWE problem is based on the hardness of the approximate shortest vector problem (GapSVP(gamma)) over regular lattices, the hardness of the RLWE problem is based on the hardness of the approximate shortest vector problem over ideal lattices. As of now, it has not been proved that the (GapSVP(gamma)) problem over ideal lattices is as difficult as the corresponding problem over regular lattices. In this work, the authors propose a multi-bit levelled fully homomorphic encryption scheme using multivariate polynomial evaluations whose security depends on the hardness of the LWE problem. In terms of per gate computation cost, this scheme is more efficient than existing LWE-based schemes. Further, for an appropriate choice of parameters, the per computation cost for homomorphic multiplication can be made asymptotically comparable to RLWE-based schemes in a parallel computing environment. For homomorphic multiplication, the scheme uses a polynomial-based technique that does not require relinearization (and key switching).