2024-07-18 | Nicolas Bon, David Pointcheval, Matthieu Rivain
This paper proposes a new framework for homomorphically evaluating Boolean functions using the Torus Fully Homomorphic Encryption (TFHE) scheme. The key idea is to introduce an intermediate homomorphic layer that encodes bits into a small ring $ Z_p $, enabling the evaluation of complex Boolean functions with a single bootstrapping operation. This significantly reduces the number of bootstrappings needed compared to previous approaches, improving performance. The framework involves defining p-encodings, which map Boolean values to subsets of $ Z_p $, ensuring that the encoded values do not overlap. The authors analyze the properties of these encodings and provide algorithms to find valid sets of encodings for a given Boolean function. They also propose a method to decompose any Boolean circuit into efficiently evaluable functions using their approach. The framework is applied to evaluate cryptographic primitives like AES, achieving significant speedups compared to existing implementations. The paper also introduces a new strategy for homomorphic Boolean evaluation, leveraging p-encodings and homomorphic operations to evaluate Boolean functions efficiently. The approach allows for the evaluation of functions with any number of inputs using a single bootstrapping, and it includes techniques for encoding switching and constructing gadgets for Boolean functions. The work demonstrates the effectiveness of the framework through experimental results, showing improved performance over previous methods.This paper proposes a new framework for homomorphically evaluating Boolean functions using the Torus Fully Homomorphic Encryption (TFHE) scheme. The key idea is to introduce an intermediate homomorphic layer that encodes bits into a small ring $ Z_p $, enabling the evaluation of complex Boolean functions with a single bootstrapping operation. This significantly reduces the number of bootstrappings needed compared to previous approaches, improving performance. The framework involves defining p-encodings, which map Boolean values to subsets of $ Z_p $, ensuring that the encoded values do not overlap. The authors analyze the properties of these encodings and provide algorithms to find valid sets of encodings for a given Boolean function. They also propose a method to decompose any Boolean circuit into efficiently evaluable functions using their approach. The framework is applied to evaluate cryptographic primitives like AES, achieving significant speedups compared to existing implementations. The paper also introduces a new strategy for homomorphic Boolean evaluation, leveraging p-encodings and homomorphic operations to evaluate Boolean functions efficiently. The approach allows for the evaluation of functions with any number of inputs using a single bootstrapping, and it includes techniques for encoding switching and constructing gadgets for Boolean functions. The work demonstrates the effectiveness of the framework through experimental results, showing improved performance over previous methods.