You are looking at a specific version 20140930:085538 of this paper. See the latest version.

Paper 2014/408

Bootstrapping BGV Ciphertexts With A Wider Choice of p and q.

Emmanuela Orsini and 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. Also unlike previous methods our depth grows only as $O(\log p + \log \log q)$ as opposed to the $\log q$ of previous methods. Our basic bootstrapping technique makes use of a representation of the group $\Z_q^+$ over the finite field $\F_p$ (either based on polynomials or elliptic curves), 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
Preprint. MINOR revision.
Keywords
FHEBootstrapping
Contact author(s)
nigel @ cs bris ac uk,Emmanuela Orsini @ bristol 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
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.