Paper 2013/060

On FHE without bootstrapping

Aayush Jain


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.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Fully Homomorphic EncryptionMultivariate PolynomialsBootstrappingSymmetric Key Cryptography
Contact author(s)
aayushjainiitd @ gmail com
2013-05-22: last of 7 revisions
2013-02-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Aayush Jain},
      title = {On FHE without bootstrapping},
      howpublished = {Cryptology ePrint Archive, Paper 2013/060},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.