Homomorphic Encryption

Schemes that support unlimited operations of a single type—either addition or multiplication, but not both. PHE is computationally lightweight and practical for specific, bounded use cases.

• RSA Encryption: Supports unlimited modular multiplication on ciphertexts, making it multiplicatively homomorphic.
• Paillier Cryptosystem: Supports unlimited addition of encrypted integers and multiplication by a plaintext constant.
• ElGamal Encryption: Supports multiplicative homomorphism over cyclic groups.
• Use Case: Secure e-voting where encrypted votes are tallied via addition without decrypting individual ballots.
• Performance: Negligible ciphertext expansion and fast execution compared to stronger schemes.

Schemes that support both addition and multiplication but only for circuits of limited depth. Each operation introduces noise that grows until decryption becomes impossible.

• BGN Cryptosystem: Supports one multiplication followed by unlimited additions using bilinear pairings.
• YASHE & B/FV Schemes: Ring-LWE-based schemes that support deeper circuits before noise overwhelms the ciphertext.
• Noise Budget: A finite resource consumed by each operation; multiplication is exponentially more expensive than addition.
• Use Case: Computing simple statistical functions like averages and standard deviations on encrypted medical data.
• Bootstrapping Gap: SHE lacks the recursive self-correction mechanism needed to reset the noise budget.

The holy grail of encrypted computation: schemes that support arbitrary computation on ciphertexts by evaluating circuits of unbounded depth. FHE achieves this through bootstrapping, a technique that homomorphically evaluates the decryption circuit itself to refresh the noise budget.

• Gentry's Blueprint (2009): The first theoretical construction using ideal lattices and a bootstrappable SHE scheme.
• TFHE (Fast Fully HE): Optimized for gate-level boolean circuits with sub-second bootstrapping, ideal for low-latency applications.
• CKKS Scheme: Supports approximate arithmetic on encrypted real numbers, enabling privacy-preserving machine learning inference.
• BGV/BFV Schemes: Integer arithmetic schemes optimized for SIMD-style batching of thousands of operations.
• Use Case: Training a logistic regression model on encrypted patient records in an untrusted cloud environment.

A practical variant of FHE that can evaluate circuits up to a pre-determined multiplicative depth without bootstrapping. By setting the parameters to support exactly the required depth, leveled FHE avoids the enormous computational cost of bootstrapping.

• Parameter Selection: The scheme's modulus chain is sized to accommodate the target circuit depth at setup time.
• Modulus Switching: A noise management technique that scales down ciphertext noise after each multiplication without bootstrapping.
• BGV & BFV in Practice: Most real-world deployments use these schemes in leveled mode for efficiency.
• Use Case: Privacy-preserving inference on a fixed-depth neural network where the architecture is known in advance.
• Limitation: Cannot handle data-dependent loops or recursion where the circuit depth is unknown at encryption time.

A multi-party variant where the secret key is split among multiple parties, and decryption requires a threshold number of participants to collaborate. No single party can decrypt ciphertexts independently.

• Distributed Key Generation: The secret key is generated jointly without any party ever holding the complete key.
• Threshold Decryption Protocol: A minimum of t-out-of-n parties must contribute partial decryption shares to recover the plaintext.
• Use Case: A consortium of hospitals jointly computing on encrypted patient data where no single institution can unilaterally decrypt the results.
• Integration: Can be layered on top of BGV, BFV, or CKKS schemes.
• Security Model: Protects against a dishonest minority of colluding parties attempting to violate data privacy.

A pragmatic architecture that combines symmetric encryption for data with homomorphic encryption for computation keys, enabling efficient processing of large datasets. The client encrypts data with a lightweight symmetric cipher and uses HE only to encrypt the symmetric key.

• PASERK & Transciphering: The symmetric ciphertext is transformed into an HE-compatible format on the server side.
• HERA & Rubato Ciphers: Low-multiplicative-depth symmetric ciphers specifically designed for efficient transciphering to FHE.
• Use Case: Encrypting a terabyte-scale genomic database with AES, then homomorphically computing on specific records by transciphering only the relevant blocks.
• Bandwidth Reduction: Dramatically reduces ciphertext expansion during client-to-server transmission.
• Trade-off: Introduces a transciphering step that adds latency but enables FHE on datasets too large for pure HE encryption.