Fully Homomorphic Encryption (FHE)

FHE allows the evaluation of arbitrary circuits (both addition and multiplication gates) directly on encrypted data. This is the defining property that distinguishes it from Partially Homomorphic Encryption (PHE), which supports only one operation type, and Somewhat Homomorphic Encryption (SWHE), which is depth-limited. The result of an FHE computation is itself a ciphertext that, when decrypted, matches the output of the computation as if it had been performed on the raw plaintext data.

Every homomorphic operation, especially multiplication, increases the inherent noise within a ciphertext. Without intervention, this noise eventually overwhelms the signal, rendering decryption impossible. Bootstrapping is the breakthrough technique that enables true FHE by homomorphically evaluating the decryption circuit itself, effectively 'refreshing' the ciphertext and resetting its noise budget to a fixed level. This allows for computations of theoretically unlimited multiplicative depth.

Modern FHE schemes leverage Single Instruction, Multiple Data (SIMD) operations through a technique called ciphertext packing. By encoding a vector of plaintext values into a single ciphertext, a single homomorphic addition or multiplication simultaneously applies the operation to all slots. This dramatically improves amortized throughput, making it feasible to process thousands of encrypted values in parallel, which is critical for the linear algebra operations found in neural networks.

The security of leading FHE schemes (CKKS, BGV, TFHE) is based on the hardness of the Ring Learning With Errors (RLWE) problem. This is a lattice-based computational assumption that is believed to be resistant to attacks by both classical and large-scale quantum computers. As a result, FHE is classified as a post-quantum cryptography primitive, ensuring that data encrypted today remains secure against future cryptanalytic breakthroughs.

Beyond bootstrapping, FHE employs a suite of techniques to control noise growth during computation:

• Modulus Switching: Scales down a ciphertext to a smaller modulus, proportionally reducing absolute noise without the secret key.
• Relinearization: Reduces a ciphertext's size back to two ring elements after multiplication, preventing quadratic growth.
• Rescaling: In the CKKS scheme, this divides a ciphertext by a scale factor after multiplication to maintain a stable scale, analogous to truncating floating-point precision.

An advanced technique in the TFHE scheme, Programmable Bootstrapping not only refreshes the noise of a ciphertext but simultaneously evaluates a univariate function via a lookup table. This allows for the efficient homomorphic evaluation of non-linear activation functions like ReLU or sigmoid in a single step, making TFHE exceptionally fast for evaluating deep neural network inference on encrypted data.

The finite capacity for error accumulation within a ciphertext. Each homomorphic operation—especially multiplication—consumes this budget. Key management techniques:

• Modulus Switching: Scales down ciphertext to proportionally reduce absolute noise
• Rescaling: CKKS-specific operation dividing by scale factor post-multiplication
• Relinearization: Prevents quadratic ciphertext growth after multiplication Once the noise budget is exhausted, decryption becomes unreliable or impossible.