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 $\log \log q$ as opposed to the $\log q$ of previous methods. The 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). 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)
- 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
-
CC BY