## Cryptology ePrint Archive: Report 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).

Category / Keywords: public-key cryptography / FHE, Bootstrapping

Date: received 2 Jun 2014, last revised 2 Jun 2014

Contact author: nigel at cs bris ac uk,Emmanuela Orsini@bristol ac uk,Joop VandePol@bristol ac uk

Available format(s): PDF | BibTeX Citation

Short URL: ia.cr/2014/408

[ Cryptology ePrint archive ]