Paper 2023/1589

Optimized Homomorphic Evaluation of Boolean Functions

Nicolas Bon, CryptoExperts (France), École Normale Supérieure - PSL
David Pointcheval, École Normale Supérieure - PSL
Matthieu Rivain, CryptoExperts (France)

We propose a new framework to homomorphically evaluate Boolean functions using the Torus Fully Homomorphic Encryption (TFHE) scheme. Compared to previous approaches focusing on Boolean gates, our technique can evaluate more complex Boolean functions with several inputs using a single bootstrapping. This allows us to greatly reduce the number of bootstrapping operations necessary to evaluate a Boolean circuit compared to previous works, thus achieving significant improvements in terms of performances. We define theoretically our approach which consists in adding an intermediate homomorphic layer between the plain Boolean space and the ciphertext space. This layer relies on so-called $p$-encodings embedding bits into $\mathbb{Z}_p$. We analyze the properties of these encodings to enable the evaluation of a given Boolean function and provides a deterministic algorithm (as well as an efficient heuristic) to find valid sets of encodings for a given function. We also propose a method to decompose any Boolean circuit into Boolean functions which are efficiently evaluable using our approach. We apply our framework to homomorphically evaluate various cryptographic primitives, and in particular the AES cipher. Our implementation results show significant improvements compared to the state of the art.

Available format(s)
Publication info
FHEBoolean FunctionsTFHE
Contact author(s)
nicolas bon @ cryptoexperts com
david pointcheval @ ens fr
matthieu rivain @ cryptoexperts com
2023-10-13: approved
2023-10-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nicolas Bon and David Pointcheval and Matthieu Rivain},
      title = {Optimized Homomorphic Evaluation of Boolean Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1589},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.