Cryptology ePrint Archive: Report 2012/225

When Homomorphism Becomes a Liability

Zvika Brakerski

Abstract: We show that an encryption scheme cannot have a simple decryption function and be homomorphic at the same time, even with added noise. Specifically, if a scheme can homomorphically evaluate the majority function, then its decryption cannot be weakly-learnable (in particular, linear), even if large decryption error is allowed. (In contrast, without homomorphism, such schemes do exist and are presumed secure, e.g. based on LPN.)

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

Using these techniques, we show 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 that uses homomorphism, and another that directly attacks a component of the scheme.

Category / Keywords: public-key cryptography / homomorphic encryption

Date: received 24 Apr 2012, last revised 1 Sep 2012

Contact author: zvika at stanford edu

Available format(s): PDF | BibTeX Citation

Version: 20120901:225611 (All versions of this report)

Short URL: ia.cr/2012/225

Discussion forum: Show discussion | Start new discussion