International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: A Simple BGN-type Cryptosystem from LWE

Craig Gentry
Shai Halevi
Vinod Vaikuntanathan
Search ePrint
Search Google
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).
  title={A Simple BGN-type Cryptosystem from LWE},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / BGN Cryptosystem, Evaluating 2-DNF, Encrypted Bilinear Forms, Homomorphic Encryption, Lattice-based Encryption, Learning with Errors},
  note={early version in Eurocrypt 2010, this is an updated version 14704 received 5 Apr 2010},
  author={Craig Gentry and Shai Halevi and Vinod Vaikuntanathan},