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 $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).

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

Date: received 2 Jun 2014, last revised 30 Sep 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

Version: 20140930:085538 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]