International Association
for Cryptologic Research

BGV-style homomorphic encryption schemes over polynomial rings, rely for their security on rings of very large dimension. This large dimension is needed because of the large modulus-to-noise ratio in the key-switching matrices that are used for the top few levels of the evaluated circuit. However, larger noise (and hence smaller modulus-to-noise ratio) is used in lower levels of the circuit, so from a security standpoint it is permissible to switch to lower-dimension rings. Switching to a smaller ring, if possible, can help speeding up the homomorphic operations for the lower levels of the circuit. However, implementing such ring-switching is nontrivial, since these schemes rely on the ring algebraic structure for their homomorphic properties.

A basic ring-switching operation was introduced by Brakerski, Gentry and Vaikuntanathan, in the context of bootstrapping over polynomial rings of the form $\\Z[X]/(X^{2^n}+1)$. In this work we first extend this technique to work over any cyclotomic ring. Then we build on the extended technique and show how it can be used not only for bootstrapping but also during the computation itself, in conjunction with the ``packed ciphertext\'\' techniques of Gentry, Halevi and Smart.