Paper 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published by the IACR in PKC 2021
Keywords
Fully Homomorphic EncryptionAGCD problemACD problemBootstrapping.
Contact author(s)
hilder vitor @ gmail com
History
2021-04-13: last of 3 revisions
2020-08-18: received
See all versions
Short URL
https://ia.cr/2020/995
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/995,
      author = {Hilder Vitor Lima Pereira},
      title = {Bootstrapping fully homomorphic encryption over the integers in less than one second},
      howpublished = {Cryptology ePrint Archive, Paper 2020/995},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/995}},
      url = {https://eprint.iacr.org/2020/995}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.