Fully Homomorphic Encryption (FHE)

The foundational semantic security guarantee for FHE schemes. Indistinguishability under Chosen-Plaintext Attack ensures that an adversary cannot distinguish between encryptions of two different plaintexts, even when allowed to encrypt arbitrary messages of their choosing.

• Relies on probabilistic encryption: the same plaintext encrypts to different ciphertexts each time
• Guarantees that ciphertexts reveal no partial information about the underlying data
• Achieved by injecting fresh randomness during encryption
• Forms the baseline requirement for any homomorphic encryption scheme used in production

Every FHE ciphertext contains a finite amount of cryptographic noise that grows with each homomorphic operation. When noise exceeds a critical threshold, decryption fails and produces garbage output.

• Addition increases noise additively (relatively cheap)
• Multiplication increases noise multiplicatively (rapid growth)
• The noise budget dictates the multiplicative depth of a computable circuit
• Exceeding the budget requires bootstrapping to refresh the ciphertext

The ratio of encrypted data size to original plaintext size. FHE ciphertexts are substantially larger than their plaintext counterparts, creating significant storage and bandwidth overhead.

• Typical expansion factors range from 100x to 10,000x depending on scheme and parameters
• A single encrypted 64-bit integer may occupy several kilobytes
• Relinearization prevents quadratic growth after multiplication
• SIMD packing amortizes this overhead by encoding thousands of values in one ciphertext

FHE schemes are built on lattice-based cryptography, which is believed to resist attacks from both classical and large-scale quantum computers. This contrasts with traditional public-key cryptosystems like RSA and ECC.

• Security rests on the hardness of Ring Learning With Errors (RLWE) and related lattice problems
• No known quantum algorithm efficiently solves these lattice problems
• NIST's post-quantum standardization process has validated lattice-based approaches
• Provides long-term data confidentiality even against future quantum adversaries

A stronger security property ensuring that the evaluated function itself remains hidden from the party performing the computation. Without circuit privacy, the server learns the structure of the model being evaluated.

• Protects proprietary model architectures during encrypted inference
• Achieved by adding noise to the output ciphertext after evaluation
• Prevents the server from inferring which polynomial approximation was used
• Critical for model marketplace scenarios where the model is a trade secret

An advanced technique in the TFHE scheme that simultaneously refreshes noise and evaluates an arbitrary function via lookup table. This transforms bootstrapping from a pure noise-management operation into a computational primitive.

• Evaluates any univariate function in a single step during noise refresh
• Enables efficient non-linear activations (ReLU, sigmoid) in encrypted neural networks
• Operates via blind rotation of encrypted values
• Eliminates the need for separate polynomial approximation of activation functions

A client encrypts their sensitive query (e.g., a medical image or financial record) and sends it to a cloud-hosted model. The server performs the forward pass using only homomorphic addition and multiplication on the ciphertext, returning an encrypted prediction that only the client can decrypt. The server never sees the raw input.

• Use Case: A hospital queries a proprietary diagnostic model without exposing patient scans to the model owner.
• Key Requirement: The model's non-linear activation functions must be replaced with polynomial approximations compatible with FHE arithmetic.

FHE allows a data owner to contribute encrypted records to a centralized training process. The model owner performs gradient descent directly on the encrypted data, updating model weights without ever accessing the underlying plaintext. This is distinct from federated learning, as the raw data remains encrypted during the entire computation, not just during transmission.

• Challenge: Training on encrypted data is computationally intensive due to the noise budget management required for deep circuits.
• Advantage: Provides a provable privacy guarantee under the IND-CPA security standard, stronger than differential privacy alone.

Multiple institutions can jointly compute aggregate statistics or train a model on their combined encrypted datasets without revealing individual records to each other. FHE enables this by allowing a central compute node to perform operations on ciphertexts from all parties, producing an encrypted result that requires a threshold of parties to decrypt.

• Example: A consortium of banks computes an encrypted fraud detection model across their combined transaction histories.
• Enabling Technology: Multi-Party FHE distributes the decryption key, preventing any single entity from unilaterally accessing the final output.

A client can query a database or a model's embedding lookup table without revealing which record or token they are requesting. FHE enables the server to perform a homomorphic equality check across the entire encrypted index, returning only the encrypted result corresponding to the client's secret query.

• Application: A user queries a language model's embedding layer for a specific token without the server learning which token was requested.
• Mechanism: The query is encoded as an encrypted one-hot vector, and the lookup is computed as a homomorphic dot product over the entire table.

The CKKS scheme is the dominant FHE scheme for machine learning because it natively supports approximate fixed-point arithmetic on real numbers. This aligns with the inherent noise tolerance of neural networks. CKKS enables efficient SIMD packing, where multiple data samples are batched into a single ciphertext for parallel homomorphic evaluation.

• Operation: After each homomorphic multiplication, rescaling is performed to maintain a stable scale and manage noise, analogous to truncating floating-point precision.
• Optimization: A transpiler automatically converts a high-level neural network definition into an optimized CKKS circuit, abstracting away cryptographic complexity.

The TFHE scheme introduces programmable bootstrapping, which simultaneously refreshes a ciphertext's noise budget and evaluates a lookup table function. This allows the homomorphic evaluation of arbitrary non-linear functions, such as ReLU or sigmoid, in a single step without polynomial approximation.

• Mechanism: A blind rotation operation evaluates an encrypted lookup table on the ciphertext, outputting the result with a reset noise budget.
• Trade-off: TFHE operates on individual bits or small integers, making it ideal for decision trees and quantized models but less efficient for large tensor operations compared to CKKS.

Every homomorphic encryption ciphertext contains a finite amount of cryptographic noise that grows with each operation, particularly multiplication. The noise budget is the threshold before decryption fails. Managing this budget is the central engineering challenge in FHE. Techniques include:

• Modulus Switching: Scales down the ciphertext modulus to proportionally reduce absolute noise without bootstrapping.
• Relinearization: Reduces ciphertext size after multiplication to prevent quadratic growth.
• Bootstrapping: The ultimate reset mechanism for indefinite computation. Understanding noise dynamics is critical for optimizing circuit depth and parameter selection.

FHE schemes natively support only addition and multiplication over encrypted data. To evaluate non-linear functions like ReLU, sigmoid, or max pooling in neural networks, these must be replaced with low-degree polynomial approximations. Common techniques include:

• Chebyshev polynomials for minimizing maximum approximation error.
• Taylor series expansions for simple approximations.
• Minimax approximation for optimal error bounds over a specific interval. The degree of the polynomial directly impacts the multiplicative depth and noise growth, creating a trade-off between accuracy and computational cost.

The primary real-world application of FHE in machine learning. A client encrypts their input data and sends it to a server hosting a pre-trained model. The server performs homomorphic evaluation of the model on the encrypted data, producing an encrypted prediction. The client decrypts the result locally. This ensures:

• Input privacy: The server never sees the client's raw data.
• Model privacy (with circuit privacy extensions): The client learns only the prediction.
• Compliance: Enables ML on sensitive data under regulations like GDPR and HIPAA.