SoK: Can Fully Homomorphic Encryption Support General AI Computation? A Functional and Cost Analysis
Jiaqi Xue, Xin Xin, Wei Zhang, Mengxin Zheng, Qianqian Song, Minxuan Zhou, Yushun Dong, Dongjie Wang, Xun Chen, Jiafeng Xie, Liqiang Wang, David Mohaisen, Hongyi Wu, Qian Lou ∗ * · 2025
Read SoK: Can Fully Homomorphic Encryption Support General AI Computation? A Functional and Cost Analysis by Jiaqi Xue, Xin Xin, Wei Zhang, Mengxin Zheng, Qianqian Song, Minxuan Zhou, Yushun Dong, Dongjie Wang, Xun Chen, Jiafeng Xie, Liqiang Wang, David Mohaisen, Hongyi Wu, Qian Lou ∗ * (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-11604.txt.
Introduction
Jiaqi Xue and co-authors survey whether strong encryption can carry general AI in a 2025 paper. Fully homomorphic encryption lets servers compute on data they cannot read. AI workloads mix plain matrix math with trickier steps like sorting, as in search aided generation. The survey asks whether current encryption methods can run that full mix, and at what price.
One pass checks function: which AI operations the schemes can express at all. A second pass counts cost in time and size. Banks and hospitals, which hold the most sensitive data, watch this field closely. A clear ledger of what is feasible today helps them plan privacy safe AI without wishful thinking.
Catalog record
| CREATOR | Jiaqi Xue, Xin Xin, Wei Zhang, Mengxin Zheng, Qianqian Song, Minxuan Zhou, Yushun Dong, Dongjie Wang, Xun Chen, Jiafeng Xie, Liqiang Wang, David Mohaisen, Hongyi Wu, Qian Lou ∗ * |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 85 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-11604
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
SoK: Can Fully Homomorphic Encryption Support General AI Computation? A Functional and Cost Analysis Jiaqi Xue, Xin Xin, Wei Zhang, Mengxin Zheng, Qianqian Song, Minxuan Zhou, Yushun Dong, Dongjie Wang, Xun Chen, Jiafeng Xie, Liqiang Wang, David Mohaisen, Hongyi Wu, Qian Lou ∗ * Abstract . Artificial intelligence (AI) increasingly powers sensitive applications in domains such as healthcare and finance, relying on both linear operations (e.g., matrix multiplications in large language models) and non-linear operations (e.g., sorting in retrieval-augmented generation). Fully homomorphic encryption (FHE) has emerged as a promising tool for privacy-preserving computation, but it remains unclear whether existing methods can support the full spectrum of AI workloads that combine these operations. In this SoK, we ask: Can FHE support general AI computation? We provide both a functional analysis and a cost analysis. First, we categorize ten distinct FHE approaches and evaluate their ability to support general computation. We then identify three promising candidates and benchmark workloads that mix linear and non-linear operations across different bit lengths and SIMD parallelization settings. Finally, we evaluate five real-world, privacy-sensitive AI applications that instantiate these workloads. Our results quantify the costs of achieving general computation in FHE and offer practical guidance on selecting FHE methods that best fit specific AI application requirements. Our codes are available at https://github.com/UCF-ML-Research/FHE-AI-Generality . Volume: YYYY X DOI: XXXXXXX.XXXXXXX 1. Introduction The rapid advancement of AI has enabled its widespread adoption across privacy-sensitive domains, including healthcare ( Kim and Lauter, 2015 ; Raisaro et al., 2018 ; Zhang et al., 2015 ) and finance ( Armknecht et al., 2015 ; Han et al., 2019 ) . To protect privacy, FHE is a promising tool, as it enables direct computation on encrypted data without decryption, ensuring end-to-end confidentiality. However, AI workloads rely on both linear and non-linear operations, while existing FHE schemes are specialized rather than general: word-wise schemes (e.g., BGV ( Brakerski et al., 2014 ; Yudha et al., 2024 ) , BFV ( Brakerski, 2012 ; Fan and Vercauteren, 2012 ) , CKKS ( Cheon et al., 2017 ) ) are efficient for linear operations but struggle with non-linear ones, whereas bit-wise schemes (e.g., FHEW ( Ducas and Micciancio, 2015 ) , TFHE ( Chillotti et al., 2020 ) ) handle non-linear operations well but incur prohibitively high costs on linear ones. Thus, it remains unclear whether existing FHE can truly support the full spectrum of AI workloads that mix linear and non-linear operations in practice. For example, neural networks ( Gilad-Bachrach et al., 2016 ; Lou et al., 2021 ) alternate linear matrix multiplications with non-linear activation functions, and graph algorithms such as Floyd–Warshall ( Floyd, 1962 ) combine linear aggregation with non-linear comparisons. We refer to such mixed computations as general computation. The ability of an FHE method to support general computation in a non-interactive and efficient manner is what we call computational generality . Although prior research has systematized FHE along dimensions such as performance, toolchain maturity, and developer accessibility ( Viand et al., 2021 ; Gouert et al., 2023 ) , computational generality has received little attention—despite being essential for real AI applications. The open research question is twofold: first, the functionality of different FHE methods in supporting general computation, and second, the cost of executing it when such support is available. Figure 1. Overview of Our FHE Generality Measurements. $*$ $*$ footnotetext: Corresponding Author Email: [email protected]. Given the diverse landscape of FHE methods that are specifically optimized for different applications and workloads, evaluating the FHE’s computational generality is challenging. Many FHE methods are theoretically capable of general computation but remain impractical due to significant computational complexity. For instance, directly using bit-wise FHE for general computation is impractical because of its extremely high computational complexity for linear computation ( Lu et al., 2021 ) , i.e., multiplying two 16-bit integers in TFHE can take up to 30 seconds. On the other hand, using word-wise FHE for non-linear functions with linear approximation appears to be a potential direction for handling general computation, such as polynomial approximation ( Cheon et al., 2020 ; Cheon et al., 2019 ; Lee et al., 2021 ) for CKKS. However, these methods only work on a small interval, such as [-1,1] , inevitably introducing errors around 0. Such errors render approximation-based methods unsuitable for applications where even small errors are intolerable, such as genomics ( Kim and Lauter, 2015 ; Raisaro et al., 2018 ; Zhang et al., 2015 ) and finance ( Armknecht et al., 2015 ; Han et al., 2019 ) . Another line of work for general computation involves scheme switching ( Lu et al., 2021 ; Boura et al., 2020 ) between word-wise and bit-wise FHE, allowing for the evaluation of the linear operations in word-wise and the non-linear operations in the bit-wise FHE without decryption. While this leverages the strengths of both types, switching cost is prohibitively high, especially for input with a large bit-width ( Cheon et al., 2022 ) . Most importantly, additional bootstrapping might be needed after scheme switching ( Al Badawi et al., 2022 ) , which is one of the most computationally expensive operations in the word-wise FHE and is often avoided in practice ( Iliashenko and Zucca, 2021 ) . Additionally, while word-wise BGV/BFV can leverage \mathbb{F}_{p} -based polynomial interpolation ( Tan et al., 2020 ; Iliashenko and Zucca, 2021 ; Morimura et al., 2023 ) to enable exact non-linear operations, their efficacy in general computations remains unverified, because the inherent field disparity between \mathbb{F}_{p} (non-linear) and \mathbb{Z}_{p^{d}} (linear) fundamentally limits seamless integration of mixed operations. To enable them to support general computation in a non-interactive manner, Zhang et al. ( Zhang et al., 2023 ) proposed an encoding switching method, HEBridge. Recently, several functional bootstrapping methods ( Alexandru et al., 2024 ; Lee et al., 2024 ; Liu and Wang, 2023 ) have been proposed to allow arbitrary function computation during the bootstrapping process. Functional bootstrapping refreshes ciphertexts and applies a chosen function simultaneously, effectively removing noise while completing a specific Look-Up Table (LUT) evaluation. Specifically, Lee et al. ( Lee et al., 2024 ) proposed a functional bootstrapping technique that takes an RLWE ciphertext, i.e., CKKS or BFV, as input and outputs the refreshed BFV ciphertext, building upon BFV-style bootstrapping. However, such BFV-style bootstrapping is far from efficient; for instance, it can take about 3 minutes for a single evaluation due to the intrinsically inefficient slot utilization of BFV-style bootstrapping ( Alexandru et al., 2024 ) . To address this issue, Alexandru et al. ( Alexandru et al., 2024 ) presented a general functional bootstrapping technique based on CKKS-style bootstrapping, which has the best throughput among all FHE methods, to improve amortized performance. However, this method suffers from high computational complexity for large input spaces. Their experimental results are limited to 12-bit LUTs because the scaling factor nears the limit for 64-bit modular operations, and the complexity of polynomial evaluation increases significantly, i.e., approximately 1 minute per evaluation for 9-bit LUTs, but about 10 minutes for 12-bit LUTs. To evaluate the computational generality of FHE, we proceed in three stages, as shown in Figure 1 . First, we survey and analyze current FHE methods to determine