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