Homomorphic Encryption

This is the core mathematical property: operations performed on ciphertexts correspond to specific operations on the plaintexts. For a function f and an encryption scheme E, if E(x) ⊕ E(y) = E(x + y) for some operations ⊕ and +, the scheme is homomorphic. This allows a third party (e.g., a cloud server) to compute f(E(data)) and return an encrypted result that, when decrypted by the data owner, equals f(data).

• Additive Homomorphism: Supports addition (e.g., Paillier cryptosystem).
• Multiplicative Homomorphism: Supports multiplication (e.g., RSA with unpadded messages).
• Fully Homomorphic: Supports both addition and multiplication an unlimited number of times, enabling arbitrary computations.

A fundamental security requirement for any modern encryption scheme, including HE. Semantic security (IND-CPA - Indistinguishability under Chosen Plaintext Attack) means that an adversary who sees a ciphertext cannot learn any partial information about the underlying plaintext, even if they can choose plaintexts to be encrypted. This guarantee holds even when the adversary performs computations on the ciphertexts. Without this, the ability to compute on ciphertexts could leak information through the ciphertext's structure or metadata.

HE schemes introduce significant computational and storage overheads.

• Ciphertext Expansion: Encrypted data (ciphertexts) are much larger than the original plaintexts, often by orders of magnitude (e.g., a 1 KB plaintext may become a 1 MB ciphertext). This impacts storage and communication bandwidth.
• Noise Growth: Most practical HE schemes (like BGV, BFV, CKKS) are Somewhat or Leveled Fully Homomorphic. They embed 'noise' in ciphertexts for security. Each homomorphic operation increases this noise. Multiplication causes particularly rapid noise growth. Once noise exceeds a threshold, decryption fails. Techniques like bootstrapping (a computationally expensive homomorphic decryption of the ciphertext) are required to 'refresh' the ciphertext and enable further computations, enabling Fully Homomorphic Encryption (FHE).

Computation on HE-encrypted data is not programmatic but circuit-based. The function f to be computed must be expressed as a sequence of supported homomorphic operations (gates in a circuit), typically over Boolean or arithmetic circuits. This requires significant upfront engineering:

• Circuit Depth: The maximum number of sequential multiplications determines the required 'level' of a leveled HE scheme or the frequency of bootstrapping.
• Data Encoding: Real numbers or complex data must be encoded into the plaintext space of the HE scheme (e.g., integers modulo t). Schemes like CKKS allow approximate arithmetic on real numbers by treating the plaintext space as complex numbers with fixed precision.

HE enables a powerful delegated computation model. The data owner can:

1. Encrypt data locally.
2. Send only the ciphertexts to an untrusted server (e.g., public cloud).
3. The server performs the agreed-upon computations without interaction with the data owner and without decryption keys.
4. The server returns the encrypted result.

The data owner decrypts the result locally. This model is non-interactive for the core computation phase, simplifying architecture compared to interactive protocols like Secure Multi-Party Computation (MPC). It is ideal for scenarios like private cloud analytics or secure outsourcing of machine learning inference.

HE has evolved through distinct generations of schemes, each with different capabilities and trade-offs:

• Partially Homomorphic (PHE): Supports only one type of operation indefinitely (e.g., Paillier: addition; RSA: multiplication). Efficient and used in specific applications like private voting or encrypted database sums.
• Somewhat Homomorphic (SWHE): Supports both addition and multiplication but only for a limited number of multiplications (low circuit depth).
• Leveled Fully Homomorphic (Leveled FHE): Supports circuits of an a-priori bounded depth without bootstrapping. Sufficient for many fixed-function applications (e.g., a specific ML model).
• Fully Homomorphic (FHE): Supports arbitrary-depth circuits via bootstrapping. Pioneered by Craig Gentry's breakthrough in 2009. Modern libraries like Microsoft SEAL, OpenFHE, and Concrete implement schemes like BGV, BFV, and CKKS, which are leveled FHE but can be made fully homomorphic with bootstrapping.

While federated learning shares model updates instead of raw data, Homomorphic Encryption adds a stronger layer of security. Clients can encrypt their local model updates (gradients) before sending them to the central server. The server can then homomorphically aggregate these encrypted updates into a single encrypted global update. This prevents the server from performing model inversion attacks or learning anything about an individual client's data from their update. It complements secure multi-party computation protocols for robust, privacy-guaranteed federated averaging.

• Mechanism: The server computes the encrypted sum of client updates without decrypting them, then sends the aggregated ciphertext back for decryption by a trusted coordinator or via distributed decryption.

Multiple organizations can jointly compute statistics or train models on the union of their encrypted datasets without revealing their individual contributions. Each party encrypts their data with a shared public key. Homomorphic operations are performed on the combined encrypted dataset. This enables cross-silo collaboration on sensitive data—such as joint disease research between competing pharmaceutical companies—where legal and competitive barriers prevent data sharing.

• Operation: Supports encrypted sums, averages, and covariance matrices, which are foundational for many ML algorithms.
• Contrast with Federated Learning: Here, the computation happens on a static, encrypted union of datasets, not via iterative update sharing.

Homomorphic Encryption allows a model developer to evaluate the performance of a model on an encrypted test set owned by a third party. The test data owner encrypts their labels and features. The developer runs the model on the encrypted features, and a homomorphic comparison can be used to compute encrypted accuracy, precision, or recall metrics. This enables benchmarking and auditing of models on sensitive, real-world datasets without the dataset custodian having to reveal the data or the model owner revealing their proprietary model.

• Process: The final performance metric (e.g., an encrypted count of correct predictions) is decrypted to reveal only the aggregate result, not individual test outcomes.

Despite its strong privacy guarantees, Homomorphic Encryption introduces significant computational overhead and ciphertext expansion, making it impractical for training large, modern neural networks from scratch. Current practical applications focus on:

• Limited Model Complexity: Linear models, shallow neural networks, and decision trees are more feasible than large transformers.
• Inference vs. Training: Privacy-preserving inference is a more immediate, performance-viable use case than full training.
• Hybrid Approaches: Often used in conjunction with other techniques like Trusted Execution Environments (TEEs) or Secure Multi-Party Computation (MPC) for specific, high-value operations within a larger secure pipeline.
• Active Research Areas: Fully Homomorphic Encryption (FHE) schemes and compiler stacks (e.g., FHE compilers) are rapidly evolving to improve performance and developer accessibility.

A cryptographic protocol that enables a group of distrusting parties to jointly compute a function over their private inputs while revealing nothing but the final output. No single party learns the other parties' secret data. SMPC often works by secret-sharing data across participants.

• Core Principle: Distributed trust through cryptographic protocols.
• Example: Two hospitals can compute the average patient treatment cost without revealing their individual patient records.
• Contrast with HE: SMPC is typically an interactive protocol requiring communication between parties during computation. HE is often non-interactive; a single party can perform computations on encrypted data alone.

A secure, isolated area within a main processor (e.g., Intel SGX, ARM TrustZone) that guarantees the confidentiality and integrity of code and data loaded inside it. Code executing in a TEE is protected even from a compromised operating system or hypervisor.

• Hardware-Based: Relies on CPU extensions for memory encryption and remote attestation.
• Primary Use: Creating secure 'enclaves' for processing sensitive data in the cloud.
• Contrast with HE: A TEE is a hardware-based isolation technique that trusts the CPU manufacturer. HE is a pure cryptographic technique that requires no trusted hardware, only the secret key.

The process of creating artificial datasets that mimic the statistical properties and patterns of real-world data. This synthetic data can be used for model training and testing without exposing the original sensitive records.

• Methods: Generative Adversarial Networks (GANs), diffusion models, and variational autoencoders.
• Privacy Goal: Break the link between the generated data points and real individuals.
• Contrast with HE: Synthetic data replaces the original dataset with a proxy. HE encrypts the original dataset, allowing computation on the exact data in its protected form.