Cryptology ePrint Archive: Report 2010/182

A Simple BGN-type Cryptosystem from LWE

Craig Gentry and 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).

Category / Keywords: public-key cryptography / BGN Cryptosystem, Evaluating 2-DNF, Encrypted Bilinear Forms, Homomorphic Encryption, Lattice-based Encryption, Learning with Errors

Publication Info: early version in Eurocrypt 2010, this is an updated version

Date: received 5 Apr 2010

Contact author: shaih at alum mit edu

Available formats: PDF | BibTeX Citation

Version: 20100409:144751 (All versions of this report)

Discussion forum: Show discussion | Start new discussion