### Evaluating 2-DNF Formulas on Ciphertexts

**Authors:** Dan Boneh, Eu-Jin Goh, and Kobbi Nissim.

**Abstract:**

Let Ψ be a 2-DNF formula on boolean variables
x_{1},…,x_{n} ∈ {0,1}. We present a
homomorphic public key encryption scheme that allows the public
evaluation of Ψ given an encryption of the variables
x_{1},…,x_{n}. In other words, given the encryption of the bits
x_{1},…,x_{n}, anyone can create the encryption of
Ψ(x_{1},…,x_{n}). 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 of the system:

In a database of size n, the total
communication in the basic step of the Kushilevitz-Ostrovsky
PIR protocol is reduced from √n to ∛n.
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 still efficient.
A protocol for universally verifiable computation.
**Reference:**

In the Proceedings of Theory of Cryptography Conference 2005.

BibTex: bib

**Full Paper:**

Last updated on 2 Apr 2006 pdf, ps

**Slides:**

Theory of Cryptography Conference 2005, Stanford Security Forum

**Related Papers:**

NA.