Paper 2021/1135

FDFB: Full Domain Functional Bootstrapping Towards Practical Fully Homomorphic Encryption

Kamil Kluczniak
Leonard Schild, schild.leonard@gmail.com
Abstract

Computation on ciphertexts of all known fully homomorphic encryption (FHE) schemes induces some noise, which, if too large, will destroy the plaintext. Therefore, the bootstrapping technique that re-encrypts a ciphertext and reduces the noise level remains the only known way of building FHE schemes for arbitrary unbounded computations. The bootstrapping step is also the major efficiency bottleneck in current FHE schemes. A promising direction towards improving concrete efficiency is to exploit the bootstrapping process to perform useful computation while reducing the noise at the same time. We show a bootstrapping algorithm, which embeds a lookup table and evaluates arbitrary functions of the plaintext while reducing the noise. Depending on the choice of parameters, the resulting homomorphic encryption scheme may be either an exact FHE or homomorphic encryption for approximate arithmetic. Since we can evaluate arbitrary functions over the plaintext space, we can use the natural homomorphism of Regev encryption to compute affine functions without bootstrapping almost for free. Consequently, our algorithms are particularly suitable for arithmetic circuits over a finite field with many additions and scalar multiplication gates. We achieve significant speedups when compared to binary circuit-based FHE. For example, we achieve 280-1200x speedups when computing an affine function of size 784 followed by any univariate function when compared to FHE schemes that compute binary circuits. With our bootstrapping algorithm, we can efficiently convert between arithmetic and boolean plaintexts and extend the plaintext space using the Chinese remainder theorem. Furthermore, we can run the computation in an exact and approximate mode where we trade-off the size of the plaintext space with approximation error. We provide a tight error analysis and show several parameter sets for our bootstrapping. Finally, we implement our algorithm and provide extensive tests. We demonstrate our algorithms by evaluating different neural networks in several parameter and accuracy settings.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in TCHES 2023
Keywords
Fully Homomorphic EncryptionBootstrappingOblivious Neural Network Inference
Contact author(s)
kamil kluczniak @ gmail com
History
2023-01-03: revised
2021-09-07: received
See all versions
Short URL
https://ia.cr/2021/1135
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1135,
      author = {Kamil Kluczniak and Leonard Schild},
      title = {FDFB: Full Domain Functional Bootstrapping Towards Practical Fully Homomorphic Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1135},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1135}},
      url = {https://eprint.iacr.org/2021/1135}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.