Homomorphic Encryption

Homomorphic schemes are categorized by their computational capabilities:

• Somewhat Homomorphic Encryption (SHE): Supports a limited number of addition and multiplication operations before the ciphertext becomes too noisy to decrypt correctly. Practical but constrained.
• Leveled Homomorphic Encryption (LHE): Supports circuits (computations) of a predetermined, bounded depth. The encryption parameters are set in advance based on the maximum required complexity.
• Fully Homomorphic Encryption (FHE): The theoretical ideal. Supports an unlimited number of arbitrary operations (additions and multiplications) on ciphertexts. Modern FHE schemes (e.g., CKKS, TFHE) achieve this via bootstrapping, a computationally intensive operation that 'refreshes' a noisy ciphertext, allowing for indefinite computation.

The primary trade-off for HE's strong security guarantees is significant computational and storage overhead.

• Ciphertext Expansion: Encrypted data can be 100x to 10,000x larger than the original plaintext, impacting storage and network transfer.
• Operational Latency: Homomorphic operations are orders of magnitude slower than their plaintext equivalents. A simple multiplication can be ~1,000,000x slower.
• Specialized Algorithms: Efficient implementation requires specialized math libraries (e.g., Microsoft SEAL, OpenFHE, PALISADE) and often hardware acceleration (GPUs, FPGAs, or dedicated ASICs) for production viability.

Modern HE schemes provide semantic security (IND-CPA security), meaning that an adversary who sees a ciphertext cannot learn any information about the underlying plaintext, even if they can choose the plaintexts to be encrypted. This is a stronger guarantee than deterministic encryption and is foundational for privacy. The security is based on hard mathematical problems, typically variants of the Learning With Errors (LWE) problem or Ring-LWE, which are believed to be resistant to quantum computer attacks.

HE enables specific, high-value privacy-preserving applications:

• Encrypted Machine Learning Inference: A client encrypts their data (Enc(user_data)) and sends it to a cloud service hosting an ML model. The cloud performs inference homomorphically, returning Enc(prediction). The cloud never sees the data or the result; only the client can decrypt the prediction.
• Encrypted Database Query/Vector Search: A server holds an encrypted database. A client can submit an encrypted query (Enc(query)), and the server can perform a search or similarity comparison homomorphically, returning encrypted results. This is the core of Privacy-Preserving RAG for retrieving from sensitive knowledge bases.

Bootstrapping is the critical technique that transforms a Leveled HE scheme into a Fully Homomorphic Encryption scheme.

• The Problem of Noise: Each homomorphic operation adds 'noise' to the ciphertext. Too much noise causes decryption failure.
• The Solution: Bootstrapping is a homomorphic evaluation of the scheme's own decryption circuit. It takes a 'noisy' ciphertext and outputs a 'fresh' ciphertext of the same plaintext but with reduced noise.
• The Cost: This is the most computationally expensive operation in FHE, often taking seconds per ciphertext on modern hardware. Research focuses heavily on optimizing bootstrapping.

HE is one tool among several in the privacy-preserving toolkit, each with different trade-offs:

• vs. Secure Multi-Party Computation (MPC): MPC involves interactive protocols between multiple parties, while HE is often non-interactive (client-server). HE typically has higher computation but lower communication overhead.
• vs. Federated Learning (FL): FL shares model updates (gradients), not raw data. HE can be combined with FL for secure aggregation, ensuring the server only sees encrypted aggregates of client updates.
• vs. Trusted Execution Environments (TEEs): TEEs (e.g., Intel SGX) rely on hardware isolation. HE is a purely cryptographic solution, avoiding trust in hardware manufacturers or cloud providers, but is computationally more intensive.

HE is often combined with other cryptographic techniques like Secure Multi-Party Computation (MPC) and Garbled Circuits in a hybrid privacy-preserving ML system. For example, non-linear activation functions in neural networks (like ReLU), which are inefficient under pure HE, can be computed using MPC, while linear layers (matrix multiplications) are computed efficiently under HE. This optimizes the overall system for performance and security.

Beyond ML models, HE allows for secure statistical analysis on encrypted datasets. Enterprises or researchers can compute aggregates, means, variances, and perform SQL-like queries on encrypted data stored in an untrusted database. This enables collaborative analytics across competitors or regulated institutions (e.g., for pandemic research) without sharing the underlying sensitive records, governed by a strictly enforced privacy budget.

• Example: Calculating the average salary in an encrypted HR database without revealing any individual's salary.

Fully Homomorphic Encryption (FHE) is the most powerful form of homomorphic encryption, allowing an unlimited number of arbitrary computations (addition and multiplication) to be performed on ciphertext. This enables complex functions like neural network inference to run entirely on encrypted data.

• Key Challenge: Historically high computational overhead, though modern libraries (e.g., Microsoft SEAL, OpenFHE) have made significant strides in performance.
• Use Case: Running a proprietary fraud detection model on a client's encrypted financial transaction data stored in a public cloud.

Partially Homomorphic Encryption (PHE) supports an unlimited number of operations, but only of one type—either addition or multiplication. It is far more computationally efficient than FHE.

• Examples: The Paillier cryptosystem is additively homomorphic, enabling encrypted sums and averages. The RSA cryptosystem (under certain conditions) is multiplicatively homomorphic.
• Use Case: Securely aggregating encrypted salary data from multiple employees to compute a company-wide average without decrypting individual salaries.

Somewhat Homomorphic Encryption (SHE) supports both addition and multiplication but only for a limited number of operations (a bounded circuit depth). Exceeding this depth causes noise in the ciphertext to grow uncontrollably, making decryption impossible.

• Bootstrapping: A technique used to "refresh" a ciphertext, reducing its noise and effectively converting an SHE scheme into an FHE one, albeit at a significant computational cost.
• Practicality: SHE schemes are often used for specific, predefined computations where the operation depth is known and limited.

Encrypted vector search is the application of homomorphic encryption (or other cryptographic techniques like order-preserving encryption) to perform similarity search over a database of encrypted vector embeddings.

• Core Mechanism: Enables the computation of distances (e.g., cosine similarity, Euclidean distance) between an encrypted query vector and encrypted database vectors directly in ciphertext space.
• Critical for PP-RAG: This is the foundational technology that allows a privacy-preserving RAG system to retrieve relevant document chunks from an encrypted knowledge base without the server ever seeing the query or the stored data in plaintext.

Functional Encryption (FE) is an advanced cryptographic paradigm where decrypting a ciphertext with a specific secret key yields only the result of a predefined function on the underlying plaintext, and nothing else.

• Contrast with HE: In homomorphic encryption, the data processor performs computations but learns nothing. In FE, the result recipient learns the specific output of a function but gains no other information about the input.
• Example Scenario: A government agency could issue a key that decrypts an encrypted tax return to reveal only whether the filer's income exceeds a threshold (the function output), without revealing the exact income amount.

A Trusted Execution Environment (TEE) is a hardware-based secure area within a main processor (CPU) that guarantees code and data loaded inside are protected with respect to confidentiality and integrity. It provides an alternative, non-cryptographic approach to secure computation.

• How it Works: Sensitive data is decrypted only within the secure enclave (e.g., Intel SGX, AMD SEV, ARM TrustZone). The host OS, hypervisor, and cloud provider cannot access it.
• Trade-off vs. HE: TEEs offer much higher performance than FHE but rely on hardware trust and must defend against side-channel attacks. They are often used in conjunction with cryptographic techniques for defense-in-depth.