Paper 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
homomorphic encryption
Contact author(s)
zvika @ stanford edu
History
2012-09-01: last of 2 revisions
2012-04-30: received
See all versions
Short URL
https://ia.cr/2012/225
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/225,
      author = {Zvika Brakerski},
      title = {When Homomorphism Becomes a Liability},
      howpublished = {Cryptology ePrint Archive, Paper 2012/225},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/225}},
      url = {https://eprint.iacr.org/2012/225}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.