Bootstrapping BGV ciphertexts with a wider choice of p and q

Emmanuela A Orsini, Joop van de Pol, Nigel P Smart

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

2 Citations (Scopus)

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 Zq+ over the finite field Fp (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).
Original languageEnglish
Title of host publicationPublic-Key Cryptography - PKC 2015
EditorsJonathan Katz
PublisherSpringer Berlin Heidelberg
Pages673-698
Number of pages26
ISBN (Electronic)9783662464472
ISBN (Print)9783662464465
DOIs
Publication statusPublished - 30 Mar 2015
Event18th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2015 - Gaithersburg, United States
Duration: 30 Mar 20151 Apr 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer Berlin Heidelberg
Volume9020
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference18th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2015
CountryUnited States
CityGaithersburg
Period30/03/151/04/15

Fingerprint Dive into the research topics of 'Bootstrapping BGV ciphertexts with a wider choice of p and q'. Together they form a unique fingerprint.

Cite this