Full text  Click to download. 
Citation  In proceedings of Theory of Cryptography (TCC) '05, Springer LNCS 3378, pp. 325341, 2005.

Authors  Dan Boneh
EuJin Goh Kobbi Nissim 
Let F be a 2DNF 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 multivariate 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 KushilevitzOstrovsky 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 noninteractive 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 un! iversally verifiable computation. Our constructions are based on bilinear maps in groups of composite order.