International Association
for Cryptologic Research

We propose a general framework to develop fully homomorphic encryption schemes (FHE) without using Gentry\'s technique. Initially, a private-key cryptosystem

is built over $\\mathbb{Z}_n$

($n$ being an RSA modulus). An encryption of $x\\in \\mathbb{Z}_n$

is a randomly chosen vector $e$ such that $\\Phi(e)=x$ where $\\Phi$ is a secret multivariate polynomial.

This private-key cryptosystem is not homomorphic in the sense that the vector sum is not a homomorphic operator. Non-linear homomorphic operators are then

developed. The security relies on the difficulty of solving systems of nonlinear equations (which is a $\\mathcal{NP}$-complete problem). While the security of our scheme has not been reduced to a provably hard instance of this problem,

its security is globally investigated.