# Evaluating 2-DNF Formulas on Ciphertexts

**Authors:**

*D. Boneh, E. Goh, and K. Nissim*

** Abstract: **

Let F be a 2-DNF formula on boolean variables x1,...,xn.
We present a homomorphic public key encryption system
that allows the public evaluation of F given an encryption of the
variables x1,...,xn. In other words, given the encryption of
the bits x1,...,xn, anyone can create the encryption of
F(x1,...,xn). More generally, we can evaluate
*quadratic* multi-variate polynomials on ciphertexts provided the
resulting value falls within a small set. We present a number of
applications for this system. First, it leads to improved
PIR algorithms: In a database of size n, the total
communication in the basic step of the Kushilevitz-Ostrovsky
PIR protocol is reduced from n^(1/2) to n^(1/3).
Second, it gives an efficient election system based on
homomorphic encryption where voters do not need to include
non-interactive zero knowledge proofs that their ballots are
valid. The election system is proved secure without random
oracles but is still efficient. Third, it gives a protocol
for universally verifiable computation. Our constructions
are based on bilinear maps in groups of composite order.

** Reference:**

In proceedings of Theory of Cryptography (TCC) '05, LNCS 3378,
pp. 325-341, 2005

**Full paper:**
pdf