Cryptology ePrint Archive: Report 2012/240

Ring Switching in BGV-Style Homomorphic Encryption

Craig Gentry and Shai Halevi and Chris Peikert and Nigel P. Smart

Abstract: The security of contemporary homomorphic encryption schemes over cyclotomic number field relies on fields 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 fields, thus speeding up the homomorphic operations for the lower levels of the circuit. However, implementing such field-switching is nontrivial, since these schemes rely on the field algebraic structure for their homomorphic properties.

A basic field-switching operation was used by Brakerski, Gentry and Vaikuntanathan, over number fields of the form $\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 number field, 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).

Category / Keywords: public-key cryptography / Homomorphic Encryption

Publication Info: SCN 2012

Date: received 29 Apr 2012, last revised 26 Jan 2013

Contact author: shaih at alum mit edu

Available formats: PDF | BibTeX Citation

Note: Jan-2013, major revision: transformation generalized and simplified

Version: 20130127:041319 (All versions of this report)

Discussion forum: Show discussion | Start new discussion