Paper 2012/240

Field Switching in BGV-Style Homomorphic Encryption

Craig Gentry, Shai Halevi, 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, a 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 ring-switching operation was used by Brakerski, Gentry and Vaikuntanathan, over rings 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).

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

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Major revision. SCN 2012, Springer LNCS vol. 7485
DOI
10.1007/978-3-642-32928-9_2
Keywords
Homomorphic EncryptionRing-LWE
Contact author(s)
shaih @ alum mit edu
History
2013-09-13: last of 6 revisions
2012-04-30: received
See all versions
Short URL
https://ia.cr/2012/240
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/240,
      author = {Craig Gentry and Shai Halevi and Chris Peikert and Nigel P.  Smart},
      title = {Field Switching in BGV-Style Homomorphic Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2012/240},
      year = {2012},
      doi = {10.1007/978-3-642-32928-9_2},
      note = {\url{https://eprint.iacr.org/2012/240}},
      url = {https://eprint.iacr.org/2012/240}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.