Paper 2021/1135

FDFB: Full Domain Functional Bootstrapping Towards Practical Fully Homomorphic Encryption

Kamil Kluczniak
Leonard Schild,

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.

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in TCHES 2023
Fully Homomorphic EncryptionBootstrappingOblivious Neural Network Inference
Contact author(s)
kamil kluczniak @ gmail com
2023-01-03: revised
2021-09-07: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.