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" ciphertexts that encrypt vectors of plaintext elements. In this work, we introduce permuting/routing techniques to move plaintext elements across these vectors efficiently. Hence, we are able to implement general arithmetic circuit in a batched fashion without ever needing to "unpack" the plaintext vectors.
We also introduce some other optimizations that can speed up homomorphic 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.Category / Keywords: public-key cryptography / Homomorphic encryption, Bootstrapping, Batching, Automorphism, Galois group, Permutation network Publication Info: extended abstract in Eurocrypt 2012 Date: received 19 Oct 2011, last revised 5 Apr 2012 Contact author: shaih at alum mit edu Available format(s): PDF | BibTeX Citation Version: 20120405:191805 (All versions of this report) Discussion forum: Show discussion | Start new discussion