Fully Homomorphic Encryption (FHE)

Unlike Partially Homomorphic Encryption (PHE) or Somewhat Homomorphic Encryption (SHE), FHE supports an unbounded number of sequential operations on ciphertexts. This is achieved through a critical self-repair mechanism called bootstrapping.

• The Noise Problem: Every homomorphic operation (especially multiplication) injects statistical noise into the ciphertext. If noise exceeds a threshold, decryption fails.
• Bootstrapping: FHE evaluates its own decryption circuit homomorphically, using an encrypted secret key. This resets the noise level to a fixed baseline without exposing the plaintext.
• Result: Arbitrarily complex circuits (Turing-complete computation) can be executed without ever decrypting the data.

FHE schemes natively support algebraic operations between encrypted and unencrypted values, optimizing workflows where one operand is public.

• Mechanism: A plaintext scalar is encoded into the ciphertext space and added to or multiplied by the encrypted data directly.
• Efficiency: These operations generate significantly less noise than ciphertext-ciphertext multiplication, making them computationally cheaper.
• Use Case: Multiplying an encrypted salary column by a public tax rate, or adding a public bias term to an encrypted neural network layer.

Modern FHE schemes based on Ring Learning With Errors (RLWE) allow packing multiple plaintext values into a single ciphertext, enabling Single Instruction, Multiple Data (SIMD) parallelism.

• Slot Algebra: A ciphertext is treated as an array of independent slots. Homomorphic addition or multiplication operates on all slots simultaneously.
• Rotation: Special Galois keys enable cyclic rotation of slot values, allowing cross-slot communication without decryption.
• Throughput: This batching technique can amortize the cost of computation over thousands of logical operations, drastically improving throughput for vectorized workloads like encrypted database queries.

A specialized technique distinct from noise-refreshing bootstrapping. Circuit bootstrapping converts a homomorphic encryption of a bit into a refreshed ciphertext suitable for use in programmable look-up tables (LUTs).

• Function Evaluation: Enables the evaluation of arbitrary non-linear functions (e.g., ReLU, sigmoid) on encrypted data by decomposing them into table look-ups.
• Mechanism: It evaluates a decryption circuit followed by an encoding function, effectively mapping a noisy ciphertext to a clean ciphertext representing the output of a chosen function.
• Relevance: Critical for implementing complex machine learning activation functions directly over encrypted data without approximation.

Extensions of FHE that distribute trust among multiple parties, preventing any single entity from decrypting the final result.

• Threshold FHE: The secret key is split into shares distributed among participants. A minimum threshold of parties must collaborate to decrypt the output, ensuring no single party can access the plaintext.
• Multi-Key FHE: Allows computation on ciphertexts encrypted under different public keys. The resulting ciphertext can only be decrypted by a joint protocol involving all original key-holders.
• Application: Enables secure collaborative analytics across competing organizations without a trusted third party.

FHE schemes provide Indistinguishability under Chosen-Plaintext Attack (IND-CPA) as a baseline security guarantee.

• Semantic Security: An adversary cannot distinguish between the encryptions of two different plaintexts of their choosing, even with access to the public key.
• Probabilistic Encryption: FHE uses random nonces or error terms during encryption, ensuring that encrypting the same plaintext twice produces distinct, unlinkable ciphertexts.
• Limitation: Standard FHE does not guarantee IND-CCA (Chosen-Ciphertext Attack) security, as the malleability inherent to homomorphic evaluation allows ciphertext modification. This is an accepted trade-off for computation capability.