Homomorphic Encryption (HE)

Supports unlimited operations of a single type—either addition or multiplication, but not both. This limitation makes PHE schemes extremely fast and practical for specific, narrow use cases.

• Additive PHE (e.g., Paillier): Allows encrypted values to be summed. Ideal for federated Secure Aggregation where only the sum of model updates is needed.
• Multiplicative PHE (e.g., ElGamal): Allows encrypted values to be multiplied. Useful for private information retrieval.
• Performance: Operations are computationally lightweight compared to fully homomorphic schemes, often completing in milliseconds.

Supports both addition and multiplication, but only for a limited number of operations. The depth of the arithmetic circuit is bounded by the scheme's parameters.

• Noise Growth: Each operation, especially multiplication, increases the inherent noise within the ciphertext. Once noise exceeds a threshold, decryption fails.
• Bootstrap-Free: SHE schemes are used when the computational circuit's multiplicative depth is known in advance, avoiding the extreme cost of bootstrapping.
• Example: The BGN scheme, which allows one multiplication followed by unlimited additions.

Enables arbitrary computation on encrypted data by supporting an unlimited number of both additions and multiplications. This is the holy grail of encrypted computation.

• Bootstrapping: A revolutionary technique introduced by Gentry that refreshes the ciphertext noise homomorphically. It evaluates the decryption circuit itself under encryption, resetting the noise level to enable infinite computation.
• Lattice-Based Security: Modern FHE schemes (CKKS, BGV, TFHE) rely on the hardness of the Ring Learning With Errors (RLWE) problem, providing post-quantum security guarantees.
• Computational Overhead: FHE operations are typically 1,000x to 1,000,000x slower than plaintext computation, making hardware acceleration critical.

A practical variant of FHE that supports arbitrary, pre-determined circuits without bootstrapping. The scheme parameters are set to accommodate a specific multiplicative depth.

• No Bootstrapping Overhead: By eliminating bootstrapping, leveled FHE is significantly faster than pure FHE for circuits of known depth.
• Parameter Selection: Larger circuit depths require larger encryption parameters, increasing ciphertext size and computational cost linearly.
• Federated Learning Fit: Ideal for neural network inference where the model architecture and layer count are fixed, allowing precise parameterization.

A critical optimization that encodes multiple plaintext values into a single ciphertext, enabling Single Instruction, Multiple Data (SIMD) parallelism on encrypted data.

• Batching: In schemes like CKKS and BGV, a vector of up to 2^15 values can be packed into one ciphertext. Operations are performed element-wise on the entire vector simultaneously.
• Throughput Amplification: Packing can amortize the computational cost, making FHE thousands of times more efficient for vectorized operations like matrix multiplications in neural networks.
• Rotation Operations: Requires homomorphic rotation operations to cyclically shift packed values for cross-slot interaction.

The fundamental engineering challenge in HE is controlling the inherent noise that grows with each operation, particularly multiplication.

• Modulus Switching: A noise-reduction technique that scales down the ciphertext modulus after a multiplication, reducing the absolute noise magnitude without bootstrapping.
• Scale Invariance: Used in the CKKS scheme to maintain a consistent scale factor for approximate fixed-point arithmetic, crucial for machine learning workloads.
• Noise Budget: A finite resource consumed by each operation. Monitoring the remaining budget is essential to prevent decryption failure.

The strongest form of HE, supporting arbitrary computation (unlimited additions and multiplications) on ciphertexts. FHE enables a server to execute any algorithm on encrypted data without ever decrypting it. The primary challenge remains computational overhead, with operations typically being 1,000x to 1,000,000x slower than plaintext equivalents.

• Bootstrapping: A noise-reduction technique that enables unlimited depth circuits
• Schemes: CKKS (approximate arithmetic), BGV/BFV (exact integer arithmetic), TFHE (fast boolean gates)
• Use case: Training a full neural network on encrypted patient records

A restricted form of HE that supports only one operation type (addition or multiplication) an unlimited number of times. PHE is significantly faster than FHE and practical for specific protocols.

• Additive PHE (Paillier): Enables secure aggregation of model updates; the server sums encrypted gradients without seeing individual contributions
• Multiplicative PHE (ElGamal): Enables private set intersection and anonymous credential systems
• Use case: Federated Averaging where the central server only needs to sum encrypted client updates

A middle-ground scheme that supports limited-depth circuits (both addition and multiplication) before noise renders the ciphertext undecryptable. SHE avoids the extreme cost of bootstrapping in FHE while enabling more complex functions than PHE.

• Leveled HE: A variant where the circuit depth is known in advance and parameters are set accordingly
• Noise budget: Each multiplication increases noise; exceeding the budget corrupts the result
• Use case: Evaluating a fixed-depth inference model (e.g., a shallow CNN) on encrypted medical images

A complementary cryptographic paradigm where multiple parties jointly compute a function over their private inputs without revealing them to each other. Unlike HE, which protects data from a single untrusted server, SMPC distributes trust across participants.

• Secret sharing: Data is split into random shares distributed among parties; no single share reveals anything
• Garbled circuits: A two-party protocol where a function is encoded as an encrypted boolean circuit
• Hybrid HE+SMPC: HE handles linear operations efficiently; SMPC handles non-linear activations (ReLU, sigmoid) that are expensive under HE

A hardware-based isolation approach that creates an encrypted enclave within the CPU where code and data are protected from the host OS, hypervisor, and even physical attackers. TEEs offer a pragmatic alternative to HE for performance-sensitive workloads.

• Intel SGX/TDX, AMD SEV-SNP: Hardware implementations with remote attestation
• Threat model: TEEs trust the silicon vendor; HE trusts only mathematics
• Hybrid TEE+HE: Use TEEs for bulk computation and HE for the most sensitive operations or when hardware trust is unacceptable
• Use case: Processing encrypted patient data in a cloud enclave with attested integrity

A statistical privacy guarantee that bounds what an adversary can learn about any individual from a computation's output. DP complements HE by protecting the result of decryption, not just the computation process.

• Epsilon (ε): Quantifies the privacy loss; lower values mean stronger privacy
• HE+DP pipeline: HE protects data during computation; DP noise is added before decryption to prevent inference attacks on the output
• Use case: A hospital decrypts a federated model only after DP noise ensures individual patient contributions cannot be reverse-engineered