FHE time complexity
2025-07-13 blogpage sketch fhe
Information here taken from a side document at https://www.lesswrong.com/posts/pj6TZ2Z2faSJziXF5/the-pragmatic-side-of-cryptographically-boxing-ai
This is a good starter, but not a reliable reference.
Time complexity would be different for each HE scheme. I believe this source is about a generic case.
Fully Homomorphic Encryption (FHE) allows for computations on encrypted data without decrypting it. This is usually done in the following way:
Key Generation
Key Sharing (this is an optional step, only used when encryption is shared by multiple parties)
Encryption
Homomorphic Operations (addition and multiplication of ciphertexts)
Decryption
This is caused by noise accumulation during homomorphic operations. This is mitigated by a noise budget, which when exceeded causes decryption to fail. This in turn is solved by “Bootstrapping”, a technique that refreshes ciphertexts while maintaining their homomorphic properties. However, this operation is heavily computationally expensive. The current best bootstrapping techniques were able to reduce the number of homomorphic multiplications to O(log2), where λ is the security parameter, which is lower than the previous SOTA performance of Õ(4). This however is still incredibly computationally expensive. The time complexity and computational overhead of each step of performing FHE is detailed below:
| Operation | Time Complexity | Computational Overhead |
|---|---|---|
| Key Generation | O(λ^3) to O(λ^4) | Very high overhead. One-time cost in many protocols. |
| Encryption | O(m * λ) to O(λ^4) | High overhead. m is the message length. Results in significant ciphertext expansion. |
| Homomorphic Addition | O(n) | Moderate overhead compared to other FHE operations, but still significantly slower than plaintext addition as the operation is done on ciphertext instead of plaintext. |
| Homomorphic Multiplication | O(n log n) to O(n^2) | Very high overhead. Significantly slower than plaintext multiplication. Complexity depends on the specific FHE scheme. |
| Noise Management (Bootstrapping) | O(log2) or higher | Very high overhead. Critical for maintaining correctness during computations. Substantially increases overall computational cost. |
| Decryption | O(m * λ) | Moderate to high overhead. m is the message length. Generally less intensive than encryption but still significant. |
| Overall | O(λ^4 * 2^L) | Where L is the circuit depth. A large part of the exponential complexity comes from bootstrapping. |
Outgoing Internal References (0)
Outgoing Web References (1)
-
www.lesswrong.com/posts/pj6TZ2Z2faSJziXF5/the-pragmatic-side-of-cryptographically-boxing-ai
- https://www.lesswrong.com/posts/pj6TZ2Z2faSJziXF5/the-pragmatic-side-of-cryptographically-boxing-ai
