Paper 2010/182

A Simple BGN-type Cryptosystem from LWE

Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan

Abstract

We construct a simple public-key encryption scheme that supports polynomially many additions and one multiplication, similar to the cryptosystem of Boneh, Goh, and Nissim (BGN). Security is based on the hardness of the learning with errors (LWE) problem, which is known to be as hard as certain worst-case lattice problems. Some features of our cryptosystem include support for large message space, an easy way of achieving formula-privacy, a better message-to-ciphertext expansion ratio than BGN, and an easy way of multiplying two encrypted polynomials. Also, the scheme can be made identity-based and leakage-resilient (at the cost of a higher message-to-ciphertext expansion ratio).

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. early version in Eurocrypt 2010, this is an updated version
Keywords
BGN CryptosystemEvaluating 2-DNFEncrypted Bilinear FormsHomomorphic EncryptionLattice-based EncryptionLearning with Errors
Contact author(s)
shaih @ alum mit edu
History
2010-04-09: received
Short URL
https://ia.cr/2010/182
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/182,
      author = {Craig Gentry and Shai Halevi and Vinod Vaikuntanathan},
      title = {A Simple {BGN}-type Cryptosystem from {LWE}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2010/182},
      year = {2010},
      url = {https://eprint.iacr.org/2010/182}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.