International Association
for Cryptologic Research

We show that an encryption scheme cannot have a simple decryption circuit and be homomorphic at the same time. Specifically, if a scheme can homomorphically evaluate the majority function, then its decryption circuit cannot be a linear function of the secret key (or even a succinct polynomial), even if decryption error is allowed.

An immediate corollary is that known schemes that are based on the hardness of decoding in the presence of noise with low hamming weight cannot be fully homomorphic. This applies to known schemes such as LPN-based symmetric or public key encryption.

An additional corollary is that the recent candidate fully homomorphic encryption, suggested by Bogdanov and Lee (ePrint \'11, henceforth BL), is insecure. In fact, we show two attacks on the BL scheme: One by applying the aforementioned general statement, and another by directly attacking one of the components of the scheme.