Homomorphic Encryption

A scheme that supports an unlimited number of operations but only of a single type (either addition or multiplication) on encrypted data. It is the simplest and most computationally efficient form.

• Examples: RSA (multiplicative), Paillier (additive), ElGamal (multiplicative).
• Use Case: Secure voting systems using Paillier for tallying encrypted votes via addition, or basic encrypted database queries.

A scheme that supports a limited number of both addition and multiplication operations. The limitation arises because "noise" grows with each operation; exceeding a threshold makes decryption impossible.

• Key Concept: Bootstrapping is a technique to "refresh" ciphertext by homomorphically decrypting it, reducing noise and allowing further computations.
• Use Case: Circuits with a known, bounded depth of computation, such as evaluating a specific polynomial function on encrypted data.

A scheme that supports an unlimited number of both addition and multiplication operations on ciphertext. This is the "gold standard," enabling arbitrary computations on encrypted data.

• Pioneering Work: First realized by Craig Gentry in 2009 using lattice-based cryptography and the bootstrapping technique.
• Modern Schemes: BGV, BFV, CKKS, and TFHE are contemporary FHE schemes optimized for different data types (integers, approximate numbers, Boolean circuits).
• Primary Challenge: Significant computational overhead, making it orders of magnitude slower than plaintext computation.

A specialized FHE scheme (Cheon-Kim-Kim-Song) designed for efficient arithmetic on encrypted real or complex numbers by trading perfect precision for manageable performance.

• Core Property: Performs computations with controlled numerical error, similar to floating-point arithmetic. This is acceptable for many machine learning tasks (e.g., neural network inference).
• Dominant Use Case: Privacy-preserving inference and training for models involving matrix multiplications and activation functions on encrypted data.

The foundational mathematical framework for virtually all modern, efficient FHE schemes. Security is based on the computational hardness of problems like Learning With Errors (LWE) or Ring-LWE.

• Why Lattices?: They naturally support the addition and multiplication operations needed for homomorphism while providing security believed to be resistant to quantum attacks.
• Noise Management: Operations on lattice-based ciphertexts introduce error; the entire engineering of FHE revolves around controlling this growth.

FHE enables several critical security paradigms for AI by keeping data encrypted throughout the ML pipeline.

• Encrypted Inference: A client encrypts their data, sends it to a cloud service with a model, and receives an encrypted prediction. The service never sees the raw input or output.
• Encrypted Training: Multiple parties can collaboratively train a model on the union of their encrypted datasets without revealing their private data to each other or a central coordinator.
• Complementary Techniques: Often used alongside Secure Multi-Party Computation (MPC) and Differential Privacy for layered security guarantees.

This application allows users to query a cloud-hosted AI model with encrypted input and receive an encrypted result. The service provider never sees the user's raw data, and the user never needs to download the model. The core workflow involves:

• Client-side encryption: The user encrypts their query (e.g., a medical image, financial transaction) locally.
• Encrypted computation: The cloud service runs the model's inference (e.g., a convolutional neural network) on the ciphertext.
• Secure result return: The encrypted prediction is sent back to the client for decryption. This protects client data confidentiality and model intellectual property, making it ideal for sensitive applications like medical diagnosis or proprietary business analytics.

While standard federated learning shares only model updates, not raw data, it can still be vulnerable to inference attacks on the gradients. Homomorphic encryption provides a stronger guarantee through secure aggregation. In this enhanced protocol:

• Each client device encrypts its local model update before sending it to the central server.
• The server performs homomorphic addition on all encrypted updates to compute a new encrypted global model.
• Only after aggregation is the final model decrypted (or sent for decryption by a key holder). This process ensures the coordinating server cannot inspect any individual client's update, providing mathematical privacy guarantees against curious servers and eavesdroppers, which is essential for compliance with regulations like GDPR.

Homomorphic encryption enables complex analytical queries to be run on encrypted databases. A data owner can encrypt an entire dataset and upload it to an untrusted cloud server. Authorized analysts can then submit encrypted queries (e.g., SQL operations like SELECT, WHERE, COUNT, SUM). The server executes these operations on the encrypted records and returns an encrypted result. This allows for:

• Secure business intelligence: Calculating aggregate statistics (average sales, cohort analysis) on sensitive financial or customer data.
• Private genomic studies: Running association tests on encrypted DNA sequences.
• Encrypted search: Performing keyword search over encrypted documents. Schemes like CKKS (Cheon-Kim-Kim-Song) are optimized for these approximate arithmetic operations on real numbers.

Despite its promise, homomorphic encryption faces significant engineering hurdles that limit immediate, widespread adoption:

• Computational Overhead: Operations on ciphertext are orders of magnitude (100x to 10,000x) slower than on plaintext and require more memory.
• Ciphertext Expansion: Encrypted data can be 10x to 100x larger than the original plaintext, increasing storage and bandwidth costs.
• Supported Operations: Most practical schemes (BGV, BFV, CKKS) are Somewhat Homomorphic Encryption (SHE) or Leveled Homomorphic Encryption (LHE), meaning they support a limited number of sequential multiplications before noise must be managed. Bootstrapping is a technique to reset noise but is computationally expensive.
• Precision vs. Privacy Trade-off: Schemes for real numbers (CKKS) introduce controlled approximation error, requiring careful parameter tuning to balance accuracy with security.

Homomorphic encryption is one tool in the privacy-preserving machine learning toolkit, often used in conjunction with other methods:

• Secure Multi-Party Computation (MPC): Allows multiple parties to jointly compute a function over their inputs while keeping those inputs private. Often more efficient for specific circuits but requires continuous communication.
• Differential Privacy: Adds calibrated statistical noise to query outputs or training data to prevent inference about individuals. It's often complementary to HE, providing a different privacy guarantee on the output.
• Trusted Execution Environments (TEEs): Use hardware-based secure enclaves (e.g., Intel SGX, AMD SEV) to isolate computation. While faster than HE, they rely on hardware trust and have a larger attack surface. The choice between these techniques depends on the specific threat model, performance requirements, and trust assumptions of the application.

Private inference refers to the execution of a machine learning model (inference) on encrypted input data, ensuring the data remains confidential from the model owner or service provider.

• Core Technologies: Primarily enabled by homomorphic encryption and secure MPC. The client encrypts their data, sends it to the server, which runs the model, and returns an encrypted result for the client to decrypt.
• Critical for: Deploying models as a service (MLaaS) for highly sensitive domains like healthcare diagnostics or financial risk assessment, where the query data itself is a trade secret or personal identifier.
• Challenge: The computational overhead of performing non-linear activation functions (like ReLU) under encryption remains a major research focus.