Fully Homomorphic Encryption with Auxiliary Inputs

In this paper, we propose the first (leveled) fully homomorphic encryption (FHE) that remains secure even when the attacker is equipped with auxiliary inputs – any computationally hard-to-invert function of the secret key. It is more general than the tolerance of Berkoff and Liu’s leakage resilient fully homomorphic encryption, in which the leakage is bounded by an a priori number of bits of the secret key. Specifically, we first compile the dual of Regev’s public-key encryption scheme proposed by Gentry, Peikert and Vaikuntanathan in 2008 into a fully homomorphic encryption using Gentry, Sahai and Waters’ approximate eigenvector method. We then show that it is CPA (chosen-plaintext-attack) secure in the presence of hard-to-invert auxiliary inputs, assuming the hardness of learning with errors (LWE) problem.