Since the development of the first Fully Homomorphic Encryption (FHE) scheme in 2009 by Craig Gentry, there have been several generations of FHE schemes, each excelling in an area of encrypted computations, and a trove of real-world applications built on them.
The BFV and BGV schemes represent the first practical generation, most suitable for performing shallow arithmetic computations over encrypted vectors of integers:
Applications such as Private Information Retrieval (PIR) and Private Set Intersection (PSI) fit this template and have seen successful deployment in practice. For instance, Duality’s Query Engine product uses BFV, which is bundled in our Zero-Footprint Investigations (ZFI) product. Another example comes from Apple, which recently published a PIR scheme based on BFV for a Live Caller ID Lookup app extension.
Hybrid cryptosystems such as FHEW (also called DM) and TFHE (also called CGGI) introduced a paradigm shift for encrypted computations: bootstrapping is performed after each operation in a very efficient manner. While initially, these schemes were designed for Boolean inputs, there have later been extensions to higher precision integers. Furthermore, these schemes support functional bootstrapping (also known as programmable bootstrapping), which means that an arbitrary look-up table can be evaluated on the encrypted scalar inputs at the same time as bootstrapping. This approach makes such schemes easy to use for a variety of applications, such as privacy-preserving inference in small neural networks, encrypted smart contracts in web-3 applications, private allocation of resources on 5G networks, etc. Nevertheless, the scalability of this approach is severely limited due to the lack of vectorized operations.
Another major milestone was the CKKS scheme which enabled efficient computations over encrypted real or complex vectors. The CKKS scheme supports a relatively efficient bootstrapping procedure, showcasing the best bootstrapping throughput over all FHE schemes. While natively, it supports arithmetic operations, the efficiency of the bootstrapping procedure and the support of fixed-point numbers allowed expanding the effectively supported computations also to non-polynomial functions through polynomial interpolation procedures, when the input range is sufficiently narrow (and known). Therefore, the CKKS scheme is now widely adopted for privacy-preserving training and inference of machine learning models. For example, the majority of the iDASH competition winners used CKKS in their FHE-based solutions for secure collaboration on sensitive medical data.
Despite numerous breakthroughs and adoption in practice, the use of FHE to solve arbitrary problems over large datasets has been limited up to now. Part of the reason for this is that the FHEW/TFHE schemes support the evaluation of arbitrary look-up tables through low-latency functional bootstrapping, but their throughput is 2-3 orders of magnitude lower than CKKS bootstrapping. This brings limitations in, for instance, the size of the dataset one can compute over or the number of neurons in a neural network layer that one evaluates, thus limiting the applicability of FHE-protected neural networks. At the same time, CKKS achieves the best throughput among all schemes, but has not been able to support general functional bootstrapping until now. This translates to loss in precision or large overhead for evaluating, e.g., activation functions such as ReLU, which currently need to be polynomially approximated over narrow intervals to achieve both efficiency and precision. Can we achieve the best of both worlds?
Our researchers have solved this problem! Duality team members, in collaboration with Andrey Kim, a major contributor to the OpenFHE library and a co-author of the CKKS scheme, released a paper with a vectorized hybrid cryptosystem to achieve this goal. (See https://eprint.iacr.org/2024/1623 for details and a full description of this advance.)
Concretely, this cryptosystem and its advanced bootstrapping design, based on BFV and CKKS, supports batched functional bootstrapping. This means it enables the evaluation of arbitrary look-up tables over thousands of numbers, solving major limitations of prior approaches. This method has a throughput that is 3 orders of magnitude higher than the FHEW/TFHE functional bootstrapping method. In absolute terms, these latest advances are more efficient compared to FHEW/TFHE when the number of slots reaches the order of thousands (or even hundreds for some cases). Furthermore, compared to other batched functional bootstrapping methods based on BFV, our new method achieves a 6.6x higher throughput.
These advances embodied in Duality’s new method greatly impact real-world encrypted computations! The functional bootstrapping method described here makes broad classes of Secure AI applications feasible on homomorphically encrypted data, with on the order of 3x performance improvement compared to the state of the art. Batch processing applications that need to compute on large privacy-sensitive datasets, such as neural networks inference and training, encrypted SQL, Web3 applications, Large Language Model (LLM) inference and training, and many others, all benefit from these new methods. This functional bootstrapping capability will be added in the near future to OpenFHE, open for all to explore.
For more context and intuition on the new batch functional bootstrapping method, see the talk by Yuriy Polyakov given in the FHE.org seminar series. For technical details, see the paper by Andreea Alexandru, Andrey Kim and Yuriy Polyakov.
For more information and collaboration initiatives, reach out to info@dualitytech.com.
