Homomorphic Encryption

The homomorphism property is the core mathematical operation that defines the scheme. It allows specific algebraic operations (e.g., addition, multiplication) to be performed directly on ciphertexts, with the decrypted result matching the outcome of the same operations performed on the plaintexts. Formally, for an encryption function E and operations ⊕ (on ciphertexts) and ⊗ (on plaintexts): E(m₁) ⊕ E(m₂) = E(m₁ ⊗ m₂). This property enables the encrypted computation that makes HE unique.

Semantic security (IND-CPA - Indistinguishability under Chosen Plaintext Attack) is the standard security guarantee for modern HE schemes. It ensures that an adversary, even with access to the public encryption key, cannot learn any information about the plaintext from the ciphertext. Crucially, this security must be maintained even after performing homomorphic operations. This property is non-negotiable for privacy-preserving machine learning, as it prevents the server from inferring sensitive data from the encrypted model updates or inputs.

HE schemes have a finite computational capacity defined by a noise budget. Each homomorphic operation consumes this budget. Once exhausted, ciphertexts can no longer be decrypted correctly. The maximum sequence of operations is called the multiplicative depth. Bootstrapping is a computationally intensive technique that resets the noise budget, allowing for theoretically unlimited computations (Fully Homomorphic Encryption). For federated learning, schemes like CKKS are often used in a levelled mode, where the aggregation circuit depth is known and bootstrapping is avoided for efficiency.

HE schemes are categorized by the operations they support natively:

• Partially Homomorphic Encryption (PHE): Supports either addition or multiplication indefinitely (e.g., Paillier is additively homomorphic).
• Somewhat Homomorphic Encryption (SHE): Supports both addition and multiplication, but only for a limited depth/circuit.
• Fully Homomorphic Encryption (FHE): Supports both operations for an unlimited number of steps, enabled by bootstrapping. In federated averaging, additive homomorphism is sufficient for summing encrypted model gradients or weights, making PHE schemes like Paillier a viable, efficient choice for this specific task.

HE operates within structured mathematical spaces:

• Plaintext Space: The set of all possible unencrypted data values (e.g., integers modulo t, real/complex numbers approximated as polynomials).
• Ciphertext Space: The set of all possible encrypted values (typically polynomials with integer coefficients modulo q, where q >> t). The relationship between these spaces is crucial. For example, the CKKS scheme encodes vectors of real or complex numbers into plaintext polynomials, enabling efficient packed homomorphic operations (Single Instruction, Multiple Data - SIMD) on entire vectors at once, which is critical for performing linear algebra on encrypted neural network parameters.

The primary practical constraint of HE is its immense computational and communication overhead. Ciphertexts are orders of magnitude larger than plaintexts (e.g., kilobytes/megabytes vs. bytes), and homomorphic operations are vastly slower than their plaintext equivalents. This overhead is quantified by:

• Ciphertext Expansion Factor: Size(ciphertext) / Size(plaintext).
• Computational Slowdown: Time(encrypted operation) / Time(plaintext operation). For on-device learning, this overhead is a key consideration. The client's encryption and the server's aggregation are computationally expensive, often limiting the size of models or the precision of updates that can be practically used in a privacy-preserving federated learning pipeline.

HE enables the core privacy promise of federated learning. Clients can encrypt their local model updates (gradients or weights) before sending them to the aggregation server. The server performs the federated averaging operation directly on the encrypted updates, producing an encrypted global model. Only the final aggregated result is decrypted, ensuring the server never sees any individual client's sensitive data.

• Mitigates Gradient Leakage: Prevents the central server from reconstructing training data from model updates.
• Enables Cross-Silo FL: Allows organizations like hospitals or banks to collaborate on model training with cryptographic guarantees that their proprietary datasets remain confidential.

HE allows a client to submit an encrypted query to a cloud-based AI model and receive an encrypted prediction. The model provider performs inference on the encrypted input without ever decrypting it, protecting both the client's private data and the provider's proprietary model weights.

• Confidential Client Data: A medical app can send encrypted patient data for diagnosis without exposing it to the service provider.
• IP Protection for Models: The model owner's intellectual property (the trained weights) remains encrypted during computation, preventing model stealing or inspection.

In Retrieval-Augmented Generation (RAG) systems, HE can secure the retrieval step. A user's encrypted query can be matched against an encrypted vector database to find relevant context, all without decrypting the query or the database entries. This is critical for enterprise RAG systems handling sensitive internal documents.

• Semantic Search on Ciphertext: Enables privacy-preserving similarity search over encrypted embeddings.
• End-to-End Confidentiality: Ensures proprietary knowledge bases remain encrypted even during the retrieval process, supporting sovereign AI infrastructure.

HE allows a machine learning model to be trained directly on an encrypted dataset. A data owner can encrypt their sensitive dataset and outsource the training computation to a third-party cloud service. The service performs gradient descent and other operations on the ciphertext, returning an encrypted trained model.

• Outsourced Compute for Regulated Data: Enables use of high-performance cloud GPUs for training on financial or healthcare data that cannot leave an on-premise vault in plaintext.
• Combats Membership Inference: By training on encrypted data, it becomes cryptographically hard for an adversary to determine if a specific record was in the training set.

HE is often used in conjunction with Secure Multi-Party Computation (SMPC) to build more efficient privacy-preserving ML protocols. HE can handle linear operations efficiently on ciphertexts, while MPC protocols manage non-linear functions (like activations) and secure decryption among multiple parties.

• Hybrid Cryptographic Protocols: Combines the strengths of HE (efficient linear algebra) and MPC (flexibility for non-linear ops).
• Distributed Trust Models: Allows a computation to be distributed across several non-colluding servers, where no single server can decrypt the data alone, enhancing Byzantine robustness.

Despite its strong guarantees, HE has significant overheads that shape its application:

• Computational Overhead: Operations on ciphertexts are orders of magnitude slower than on plaintexts.
• Ciphertext Expansion: Encrypted data is much larger than its plaintext equivalent, increasing communication costs.
• Supported Operations: Most practical Somewhat Homomorphic Encryption (SHE) or Leveled HE schemes support a limited number of multiplications before requiring a costly "bootstrapping" operation. This restricts the depth of computable neural networks.

These constraints make HE most applicable to specific, high-value components of an ML pipeline (like secure aggregation) rather than end-to-end encrypted training of large models.

The process of performing machine learning model inference (prediction) on encrypted input data. This allows a client to get a prediction from a model hosted by an untrusted server without revealing their sensitive query or the server revealing its proprietary model weights.

• Client-Server Scenario: The client encrypts their data and sends it to the server. The server runs the encrypted data through its model (using HE operations) and returns an encrypted prediction. The client decrypts the result.
• Contrast with Private Training: HE is more computationally feasible for inference than full training, as inference is a forward pass only. Specialized HE schemes like CKKS are used for approximate arithmetic on encrypted real numbers common in neural networks.
• Use Case: A hospital could query a cloud-based diagnostic model with an encrypted patient MRI scan, preserving patient confidentiality.

An advanced cryptographic paradigm where decrypting a ciphertext yields the result of a specific function on the underlying plaintext, rather than the plaintext itself. It is a generalization of Homomorphic Encryption and Attribute-Based Encryption.

• Core Idea: A secret key is tied to a specific function f. When this key is used to decrypt a ciphertext encrypting data x, the result is f(x), and no other information about x is revealed.
• Contrast with HE: In HE, anyone can perform any computation on ciphertexts, but only the holder of the secret key can decrypt the final result. In FE, the function is fixed at key generation, and only the result of that function is ever revealed.
• Potential FL Application: A server could issue function keys for "model update aggregation" to clients. Clients encrypt updates, and the server can compute the aggregated update directly from the ciphertexts without learning individual contributions.