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: