Determine if "Optimized Homomorphic Evaluation of Boolean Functions" can be ported to HEIR

[j2kun]

https://eprint.iacr.org/2023/1589

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 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.