Paper 2023/1589

Optimized Homomorphic Evaluation of Boolean Functions

Nicolas Bon, CryptoExperts (France), DIENS, Ecole normale supérieure, PSL University, CNRS, Inria, Paris, France
David Pointcheval, DIENS, Ecole normale supérieure, PSL University, CNRS, Inria, Paris, France
Matthieu Rivain, CryptoExperts (France)
Abstract

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.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published by the IACR in TCHES 2024
Keywords
FHEBoolean FunctionsTFHE
Contact author(s)
nicolas bon @ cryptoexperts com
david pointcheval @ ens fr
matthieu rivain @ cryptoexperts com
History
2024-06-03: last of 2 revisions
2023-10-13: received
See all versions
Short URL
https://ia.cr/2023/1589
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1589,
      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},
      url = {https://eprint.iacr.org/2023/1589}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.