Paper 2013/340

Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based

Craig Gentry, Amit Sahai, and Brent Waters


We describe a comparatively simple fully homomorphic encryption (FHE) scheme based on the learning with errors (LWE) problem. In previous LWE-based FHE schemes, multiplication is a complicated and expensive step involving "relinearization". In this work, we propose a new technique for building FHE schemes that we call the "approximate eigenvector" method. In our scheme, for the most part, homomorphic addition and multiplication are just matrix addition and multiplication. This makes our scheme both asymptotically faster and (we believe) easier to understand. In previous schemes, the homomorphic evaluator needs to obtain the user's "evaluation key", which consists of a chain of encrypted secret keys. Our scheme has no evaluation key. The evaluator can do homomorphic operations without knowing the user's public key at all, except for some basic parameters. This fact helps us construct the first identity-based FHE scheme. Using similar techniques, we show how to compile a recent attribute-based encryption scheme for circuits by Gorbunov et al. into an attribute-based FHE scheme that permits data encrypted under the same index to be processed homomorphically.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Full version of Crypto 2013 paper
homomorphic encryptionidentity-based encryptionattribute-based encryptionlearning with errorsLWEapproximate gcd
Contact author(s)
craigbgentry @ gmail com
2013-06-09: received
Short URL
Creative Commons Attribution


      author = {Craig Gentry and Amit Sahai and Brent Waters},
      title = {Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based},
      howpublished = {Cryptology ePrint Archive, Paper 2013/340},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.