N.P.: Fully homomorphic encryption with polylog overhead. Full version at http://eprint.iacr.org/2011/566

Abstract. We show that homomorphic evaluation of (wide enough) arithmetic circuits can be accomplished with only polylogarithmic over-head. Namely, we present a construction of fully homomorphic encryp-tion (FHE) schemes that for security parameter λ can evaluate any width-Ω(λ) circuit with t gates in time t · polylog(λ). To get low overhead, we use the recent batch homomorphic evaluation techniques of Smart-Vercauteren and Brakerski-Gentry-Vaikuntanathan, who showed that homomorphic operations can be applied to “packed ” ci-phertexts that encrypt vectors of plaintext elements. In this work, we in-troduce permuting/routing techniques to move plaintext elements across these vectors efficiently. Hence, we are able to implement general arith-metic circuit in a batched fashion without ever needing to “unpack ” the plaintext vectors. We also introduce some other optimizations that can speed up homomor-phic evaluation in certain cases. For example, we show how to use the Frobenius map to raise plaintext elements to powers of p at the “cost” of a linear operation.