Paper 2020/995

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

Hilder Vitor Lima Pereira

Abstract

One can bootstrap (R)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 fast bootstrapping methods 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 runs in less than one second in a common personal computer. We also perform multi-value bootstrapping on non-binary message spaces achieving running times close to one second with modest memory requirements.