Welcome to the resource topic for 2012/225
Title:
When Homomorphism Becomes a Liability
Authors: 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.
ePrint: https://eprint.iacr.org/2012/225
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .