Fully Homomorphic Encryption (FHE)

The fundamental property guaranteeing that decryption of the evaluated ciphertext yields the exact same result as if the operation had been performed on the original plaintexts.

• Addition: Dec(Enc(a) ⊕ Enc(b)) = a + b
• Multiplication: Dec(Enc(a) ⊗ Enc(b)) = a × b
• Circuit Evaluation: Any arbitrary function f can be evaluated: Dec(Eval(f, Enc(x))) = f(x)

This property holds for both level homomorphic schemes (bounded depth) and fully homomorphic schemes (unbounded depth via bootstrapping).

FHE schemes must provide indistinguishability under chosen-plaintext attack, meaning an adversary cannot distinguish between encryptions of two different plaintexts of their choosing.

• Ciphertexts are probabilistic: encrypting the same plaintext twice produces different ciphertexts
• No information about the plaintext leaks through the ciphertext structure
• Achieved through noise-based hardness assumptions like Ring-LWE (Learning With Errors)

This guarantees that even if an attacker observes all encrypted computations, they learn nothing about the underlying data.

The critical breakthrough discovered by Craig Gentry in 2009 that enables unbounded computation on encrypted data.

• Each homomorphic operation increases ciphertext noise
• When noise exceeds a threshold, decryption fails
• Bootstrapping homomorphically evaluates the decryption circuit itself, producing a fresh ciphertext with reduced noise
• This enables fully homomorphic encryption rather than merely somewhat homomorphic

Modern schemes optimize bootstrapping through techniques like TFHE's programmable bootstrapping which simultaneously evaluates a lookup table.

A stronger security property ensuring that evaluated ciphertexts reveal nothing about the computation that was performed, not just the underlying data.

• Without circuit privacy, the structure of the evaluated function f may leak through the output ciphertext
• Achieved through noise flooding or sanitization techniques that add extra noise to obscure the computation trace
• Critical for applications where the algorithm itself is proprietary (e.g., financial models, biometric matching)

This property is distinct from semantic security and is not automatically provided by all FHE schemes.

An extension enabling computation on ciphertexts encrypted under different public keys, producing a result decryptable only through collaboration among all key-holders.

• Each party encrypts their input with their own key
• A multi-key evaluation protocol combines ciphertexts
• Decryption requires a distributed decryption protocol involving all parties
• Enables privacy-preserving collaborative analytics without a trusted third party

Key schemes: BGV-based MK-FHE, TFHE with threshold decryption, and CKKS multi-key variants.

Techniques that encode multiple plaintext values into a single ciphertext, enabling SIMD-style parallel computation and dramatically improving amortized efficiency.

• CKKS packing: Encodes a vector of real/complex numbers into one ciphertext using the canonical embedding
• BGV/BFV batching: Uses the Chinese Remainder Theorem to pack integers into plaintext slots
• Enables thousands of simultaneous operations per ciphertext multiplication
• Critical for practical performance in neural network inference and database queries

Without packing, FHE overhead would be prohibitive for most real-world workloads.