Fully Homomorphic Encryption (FHE) promises a computing paradigm where sensitive data can be processed in the cloud without ever being decrypted. Early FHE schemes focused strictly on exact arithmetic over integers or modular rings. However, real-world applications—such as machine learning inference, similarity search, and database queries—rely heavily on real numbers and floating-point arithmetic.
To bridge this gap, approximate homomorphic encryption schemes (most notably CKKS and HEAAN) were developed. As Kyoohyung Han et al. note in Bootstrapping for Approximate Homomorphic Encryption, traditional exact arithmetic schemes are fundamentally ill-suited for floating-point computations. Approximate schemes solve this by embedding the encryption noise directly into the least significant bits of the plaintext message, effectively treating cryptographic noise as part of the standard rounding error.
However, this design choice introduces a fundamental trade-off between computational efficiency and strict numerical precision. Every homomorphic operation causes the inherent noise within the ciphertext to grow. In approximate schemes, this noise accumulation directly eats into the significant digits of the underlying data, leading to progressive precision degradation. As highlighted by Huili Chen et al. in AHEC: End-to-end Compiler Framework for Privacy-preserving Machine Learning Acceleration, while approximate HE is highly effective for workloads that tolerate minor inaccuracies, it fails to support applications requiring absolute numerical exactness.
The Mechanics of Precision Degradation
To understand why precision degrades, one must look at how approximate schemes handle arithmetic operations and hardware constraints.
Multiplication and Circuit Depth
In approximate HE, multiplying two ciphertexts multiplies their error bounds. Over deep computational circuits, the precision of the fractional part rapidly vanishes. The authors of META-BTS: Bootstrapping Precision Beyond the Limit demonstrate that complex computations involving many sequential multiplications cause severe precision degradation, limiting the practical depth of the circuit unless costly bootstrapping operations are performed to refresh the ciphertext's noise budget.
Polynomial Approximations
FHE natively supports only additions and multiplications (polynomial operations). Non-polynomial functions—such as activation functions in neural networks, distance metrics, or the modular reduction step in bootstrapping—must be approximated using polynomials. As Luke Sperling et al. explain in HEFT: Homomorphically Encrypted Fusion of Biometric Templates, these polynomial approximations introduce structural numerical errors that compound with the cryptographic noise, significantly degrading downstream task performance compared to plaintext execution.
Data Conversion and Word Size
Real numbers must be scaled and converted to fixed-point or integer representations before encryption. H. Wang et al. point out in SFPDML: Securer and Faster Privacy-Preserving Distributed Machine Learning Based on MKTFHE that this floating-point-to-integer conversion introduces rounding errors that techniques like zooming can only partially mitigate.
Furthermore, adapting these schemes to standard hardware architectures introduces a hardware-level bottleneck. As Rashmi Agrawal 0001 et al. observe in High-precision RNS-CKKS on fixed but smaller word-size architectures: theory and application, maintaining high precision typically requires massive word sizes. When forced onto ubiquitous 32-bit or 64-bit hardware architectures, implementations suffer from significant precision loss or require multi-precision arithmetic, which prevents the effective use of hardware-level optimization techniques like Residue Number System (RNS) decomposition and the Number Theoretic Transform (NTT) (Andrey Kim et al.).
Impact on Downstream Applications
The practical consequence of this noise accumulation is a measurable drop in performance across various domains.
Machine Learning and Large Language Models
Machine learning models are naturally robust to small perturbations, making them the primary target for approximate HE. Miran Kim et al. showed in Secure Outsourced Matrix Computation and Application to Neural Networks that minor precision loss does not necessarily harm classification accuracy on simple tasks like MNIST. However, for more complex architectures and high-speed optimizations, the drop becomes prominent.
Cheng Hong notes in Recent advances of privacy-preserving machine learning based on (Fully) Homomorphic Encryption that high-speed optimizations like programmable bootstrapping introduce a distinct trade-off between the latency of encrypted operations and the precision of the resulting predictions. This accuracy degradation extends to large language models; Jiawen Zhang et al. demonstrate in SecPE: Secure Prompt Ensembling for Private and Robust Large Language Models that FHE-induced approximation errors lead to a slight decrease in prompt ensembling accuracy compared to plaintext execution. Similar performance impacts from approximation noise are noted in federated learning environments by Zizhen Liu et al. and Hanguan Wen et al..
Transciphering
Transciphering attempts to alleviate the massive bandwidth overhead of FHE by sending data encrypted with a standard symmetric cipher (like AES) and decrypting it homomorphically on the cloud server. However, symmetric decryption requires bit-perfect precision. As Nir Drucker et al. emphasize in E2E near-standard and practical authenticated transciphering, the inherent noise introduced by approximate schemes can corrupt the decryption process, making it exceptionally challenging to perform exact bit-level operations within a noisy homomorphic domain.
Databases and Search
In database queries and similarity searches, precision errors can break indexing and retrieval logic entirely. Song Bian 0001 et al. state in HE3DB: An Efficient and Elastic Encrypted Database Via Arithmetic-And-Logic Fully Homomorphic Encryption that achieving high-precision homomorphic comparisons is a critical bottleneck, often forcing systems to resort to inefficient bit-by-bit encryption to avoid errors. Similarly, Duhyeong Kim et al. show in GraSS: Graph-based Similarity Search on Encrypted Query that relying on approximate HE for distance metrics introduces precision errors in indexing logic, necessitating a transition to exact encryption schemes when absolute accuracy in sensitive search operations is required.
Mitigation Pathways
To make approximate HE viable for high-precision tasks, recent research focuses on algorithmic fixes that manage or restore precision without sacrificing the performance gains of approximate schemes.
- Advanced Bootstrapping: Bootstrapping refreshes a ciphertext's noise budget but traditionally introduces its own approximation errors. To combat this, Youngjin Bae et al. proposed Meta-BTS, a method that repeatedly applies a standard bootstrapping procedure to scale precision beyond conventional limits without requiring changes to the underlying HE parameters.
- Composite Scaling: To circumvent hardware constraints, Rashmi Agrawal 0001 et al. introduced composite scaling for the RNS-CKKS scheme. By grouping multiple RNS primes together, they achieve high-precision arithmetic on smaller, fixed word-size architectures, bridging the gap between theoretical precision needs and real-world hardware deployment.
- Co-design with Differential Privacy: Other approaches accept the noise but manage its security implications. Baiyu Li et al. demonstrate in Securing Approximate Homomorphic Encryption Using Differential Privacy that the precision supported by HE libraries interacts directly with security guarantees against passive adversaries, showing that higher-precision libraries are better suited to safely mask approximation noise using differential privacy techniques.
Key Foundational Work
A Full RNS Variant of Approximate Homomorphic Encryption (2018) — contributed 4 concept elements to this direction.
AHEC: End-to-end Compiler Framework for Privacy-preserving Machine Learning Acceleration (2020) — contributed 2 concept elements to this direction.
Secure Outsourced Matrix Computation and Application to Neural Networks (2018) — contributed 1 concept elements to this direction.