Cryptology ePrint Archive: Report 2020/995

Bootstrapping fully homomorphic encryption over the integers in less than one second

Hilder Vitor Lima Pereira

Abstract: One can bootstrap LWE-based fully homomorphic encryption (FHE) schemes in less than one second, but bootstrapping AGCD-based FHE schemes, also known as FHE over the integers, is still very slow. In this work we propose a fast bootstrapping method for FHE over the integers, closing thus this gap between these two types of schemes. We use a variant of the AGCD problem to construct a new GSW-like scheme that can natively encrypt polynomials, then, we show how the single-gate bootstrapping method proposed by Ducas and Micciancio (EUROCRYPT 2015) can be adapted to FHE over the integers using our scheme, and we implement a bootstrapping that, using around 400 MB of key material, runs in less than one second in a common personal computer.

Category / Keywords: public-key cryptography / Fully Homomorphic Encryption, AGCD problem, ACD problem, Bootstrapping.

Original Publication (in the same form): IACR-PKC-2021

Date: received 17 Aug 2020, last revised 3 Mar 2021

Contact author: hilder vitor at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20210303:122044 (All versions of this report)

Short URL: ia.cr/2020/995


[ Cryptology ePrint archive ]