Paper 2013/060

On FHE without bootstrapping

Aayush Jain

Abstract

We investigate the use of multivariate polynomials in constructing a fully homomorphic encryption. 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 pseudo random functions and also construct an information theoretically secure variant, rather than basing security on hard problems like Ideal Membership and Gröbner 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- It can evaluate circuits of arbitrary depths without bootstrapping for bounded length input to the algorithm. Second what follows naturally is, an attempt to make it compact we propose some changes to the scheme and analyse the scheme in (Albrecht et. al. Asiacrypt-2011). We try to make it compact but fail and realise that this could give us a Multi Party Computation protocol. Realising that polynomials leads us to non compact schemes we move propose schemes based on matrices. We then propose our candidate for a fully homomorphic encryption without bootstrapping.