Paper 2014/408

Bootstrapping BGV Ciphertexts with a Wider Choice of p and q

Emmanuela Orsini, Joop van de Pol, and Nigel P. Smart

Abstract

We describe a method to bootstrap a packed BGV ciphertext which does not depend (as much) on any special properties of the plaintext and ciphertext moduli. Prior “efficient” methods such as that of Gentry et al. (PKC 2012) required a ciphertext modulus q which was close to a power of the plaintext modulus p. This enables our method to be applied in a larger number of situations. Our basic bootstrapping technique makes use of a representation based on polynomials of the group (Zq,+) over the finite field Fp , followed by polynomial interpolation of the reduction mod p map over the coefficients of the algebraic group. This technique is then extended to the full BGV packed ciphertext space, using a method whose depth depends only logarithmically on the number of packed elements. This method may be of interest as an alternative to the method of Alperin-Sheriff and Peikert (CRYPTO 2013). To aid efficiency we utilize the ring/field switching technique of Gentry et al (SCN 2012, JCS 2013).

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. IET Information Security
Keywords
FHEBootstrapping
Contact author(s)
emmanuela orsini @ bristol ac uk
nigel @ cs bris ac uk
Joop VandePol @ bristol ac uk
History
2016-02-22: last of 3 revisions
2014-06-04: received
See all versions
Short URL
https://ia.cr/2014/408
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/408,
      author = {Emmanuela Orsini and Joop van de Pol and Nigel P.  Smart},
      title = {Bootstrapping {BGV} Ciphertexts with a Wider Choice of p and q},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/408},
      year = {2014},
      url = {https://eprint.iacr.org/2014/408}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.