*19:17*[Pub][ePrint] On FHE without bootstrapping, by Aayush Jain

In this work we come up with two fully homomorphic schemes.

First, we propose an IND-CPA secure symmetric key homomorphic encryption scheme using multivariate polynomial ring over finite fields. This scheme gives a method of constructing a CPA secure homomorphic encryption scheme from another symmetric deterministic CPA secure scheme. We base the security of the scheme on information theoretic arguments and prove the scheme to be IND-CPA secure, rather than basing security on hard problems like Ideal Membership and Gr\\\"obner basis as seen in most polly cracker based schemes which also use multivariate polynomial rings. This scheme is not compact but has many interesting properties. Second, we also describe another similar symmetric key scheme which is compact, fully homomorphic and doesn\'t require bootstrapping. The scheme is on the lines of the work of Albrecht et.al. (Asiacrypt-2011) and is proven to be bounded CPA secure. Proof is based on Ideal Membership/ Ideal Remainder/Gr\\\"obner basis problem.