Paper 2011/110

Fully Homomorphic Encryption over the Binary Polynomials

Gu Chunsheng

Abstract

This paper presents a new fully homomorphic encryption scheme over the binary polynomials. By using the self-loop bootstrappable technique, a ciphertext is refreshed to a new ciphertext with same message of an original ciphertext and smaller error terms. The size of ciphertext is remained fixed and the expansion of ciphertext is O(n) in our scheme. The security of our scheme is based on the hardness of finding an approximate-GCD problem over the binary polynomials, which is given a list of binary polynomials perturbed by the error polynomials with the smaller degree.