×

Ring switching in BGV-style homomorphic encryption. (English) Zbl 1310.94147

Visconti, Ivan (ed.) et al., Security and cryptography for networks. 8th international conference, SCN 2012, Amalfi, Italy, September 5–7, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-32927-2/pbk). Lecture Notes in Computer Science 7485, 19-37 (2012).
Summary: The security of BGV-style homomorphic encryption schemes over polynomial rings relies 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, thus 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 used by Z. Brakerski, C. Gentry and V. Vaikuntanathan [“Fully homomorphic encryption without bootstrapping.” In: ITCS 2012, Innovations in Theoretical Computer Science (2012)], over polynomial rings of the form \(\mathbb{Z}[X]/(X^{2^n}+1)\), in the context of bootstrapping. In this work we generalize and extend this technique to work over any cyclotomic ring 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 C. Gentry, S. Halevi and N. P. Smart [Eurocrypt 2012, Lect. Notes Comput. Sci. 7237, 465–482 (2012; Zbl 1297.94071)].
For the entire collection see [Zbl 1246.68059].

MSC:

94A60 Cryptography

Citations:

Zbl 1297.94071
PDFBibTeX XMLCite
Full Text: DOI