You are looking at a specific version 20210421:032723 of this paper. See the latest version.

Paper 2021/490

Optimizing Bootstrapping and Evaluating Large FHE Gates in the LWE-based GSW-FHE

Chao Liu and Anyu Wang and Zhongxiang Zheng

Abstract

Fully homomorphic encryption (FHE) allows us to perform computations directly over encrypted data and can be widely used in some highly regulated industries. Gentry's bootstrapping procedure is used to refresh noisy ciphertexts and is the only way to achieve the goal of FHE up to now. In this paper, we optimize the LWE-based GSW-type bootstrapping procedure. Our optimization decreases the lattice approximation factor for the underlying worst-case lattice assumption from $\tilde{O}(N^{2.5})$ to $\tilde{O}(N^{2})$, and is time-efficient by a $O(\lambda)$ factor. Our scheme can also achieve the best factor in prior works on bootstrapping of standard lattice-based FHE by taking a larger lattice dimension, which makes our scheme as secure as the standard lattice-based PKE. Furthermore, in this work we present a technique to perform more operations per bootstrapping in the LWE-based FHE scheme. Although there have been studies to evaluate large FHE gates using schemes over ideal lattices, (i.e. using FHEW or TFHE), we are the first to study how to perform complex functions homomorphically over standard lattices.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Major revision. ACISP 2021
Keywords
Fully homomorphic encryptionGSW-FHELWE-basedLarge FHE gates
Contact author(s)
liu_chao @ mail sdu edu cn,anyuwang @ mail tsinghua edu cn
History
2021-04-21: revised
2021-04-19: received
See all versions
Short URL
https://ia.cr/2021/490
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.