Fundamentals of Fully Homomorphic Encryption


Amina Bassit

Computer Vision over Homomorphically Encrypted Data

CVPR 2025 Tutorial

June 12, 2025

The blind spot of traditional encryption

Decryption causes costly damages that are hard to recover from.

Modern encryption provides Protection in use


Securing data in use is now a business must.

FHE can help AI models achieve trustworthiness



FHE enables AI models to process encrypted data without decryption.

Evolution of FHE schemes

Learning with Errors (LWE)

LWE problem prevents attackers from breaking FHE schemes' security

The Hardness Foundation of LWE-Based FHE

Private Key

$\mathbf{s} = \begin{bmatrix}10 \\ 82 \\ 50 \\ 51\end{bmatrix}$
Breaking FHE $\Leftrightarrow$ Solving LWE problem: recovering private key from public key.
System Problem Complexity Solution
$b=As$ in $\mathbb{R}$ System of Linear Equations P Gaussian Elimination
$b=As+e$ in $\mathbb{R}$ Least Squares Problem P Least Squares Estimator
$b=As+e \mod q$ in $\mathbb{Z}_q$ Learning with Errors Problem NP-hard No known efficient algorithm (not even quantum)
$b(X)=A(X)s(X)+e(X) \mod q$ in $\mathbb{Z}_q[X]/(X^N+1)$ Ring Learning with Errors Problem NP-hard No known efficient algorithm (not even quantum)

Pipeline of Homomorphic Evaluation of Encrypted Data



Using CKKS scheme as an example
Encoding/Decoding
Key generation
Encryption/Decryption
Evaluation

Data Encoding and decoding

Ex: CKKS encoding operates in the cyclotomic ring $\mathbb{Z}_q[X]/(X^N+1)$

Key generation

    Example of CKKS Keys
  • Private key: $sk = s(X)$
    • $s(X)\in \mathbb{Z}[X]/(X^N+1)$ sampled from $\mathbb{Z}[X]/(X^N+1)$ with coefficients in $\{-1,0,1\}$.
  • Public key: $pk=(a(X),b(x))$
    • $a(X)$ sampled at random from $\mathbb{Z}_q[X]/(X^N+1)$
    • $b(X) = -a(X) \cdot s(X)+e(X) \mod q$ where $e(X)$ is a small error sampled.
  • Evaluation keys: $evK$
    • Multiplication keys for ciphertext size reduction.
    • Rotation keys to enable rotate and conjugate.

Security parameters selection

Encryption and Decryption

Ex: CKKS ciphertext is composed of two polynomials.
  • Encryption
    • $\left[\!\left[ m \right]\!\right]=(c_0(X),c_1(X))$
      • $c_0(X) = b(X) \cdot r(X) + m(X) \mod q$
      • $c_1(X) = a(X) \cdot r(X) \mod q$
      • $r(X)$ sampled at random from $\mathbb{Z}_q[X]/(X^N+1)$
  • Decryption
    • $\tilde{m}(X) = \text{round} (c_0(X) + c_1(X) \cdot s(X) \mod q) $

Bootstrapping enables unlimited HE operations over encrypted data


Bootstrapping is very slow and need to be avoided

FHE Schemes support basic HE capabilities



Data Packing and SIMD operations

Choosing the right packing scheme significantly reduces latency.

Existing FHE schemes

Security Plaintext SIMD Bootstrapping
Ring LWE Integer CRT packing Reduce noise after n ops 🐌
Security Plaintext SIMD Bootstrapping
Ring LWE Integer CRT packing Reduce noise after n ops 🐌
Security Plaintext SIMD Bootstrapping
LWE & Ring LWE Binary ✘ Reset noise after op ⚡
Security Plaintext SIMD Bootstrapping
Torus LWE Binary ✘ Reset noise per op ⚡⚡
Security Plaintext SIMD Bootstrapping
Ring LWE Real & Complex Polynomial rings Increase modulus level after n ops 🐌

Functions natively supported by FHE



Vector operations
Squared Euclidean distance
Polynomial evaluation
Matrix operations

Vector operations Under Encryption


Squared Euclidean distance Under Encryption

    • Squared Euclidean distance $$\text{SED}(\mathbf{x},\mathbf{y}) = \sum_{i=1}^{d} (x_i - y_i)^2$$
    • Encrypted SED $$ct = \left[\!\left[ \mathbf{x} \right]\!\right] - \left[\!\left[ \mathbf{y} \right]\!\right] = \left[\!\left[ x_1 -y_1, \cdots, x_d -y_d \right]\!\right]$$ $$ct' = ct \times ct = \left[\!\left[ (x_1 -y_1)^2, \cdots, (x_d -y_d)^2 \right]\!\right]$$ $$\left[\!\left[ \text{SED}(\mathbf{x},\mathbf{y}) \right]\!\right] = \sum_{i=1}^{\log_2(d)} \text{rot}(ct', 2^i)$$

Inner product Under Encryption

    • For normalized $\mathbf{\tilde{x}}$ and $\mathbf{\tilde{y}}$, cosine becomes inner product (IP): $$< \mathbf{\tilde{x}},\mathbf{\tilde{y}}> = \sum_{i=1}^{d} \tilde{x_i} \tilde{y_i}$$
    • Encrypted IP $$ct = \left[\!\left[ \mathbf{\tilde{x}} \right]\!\right] \times \left[\!\left[ \mathbf{\tilde{y}} \right]\!\right] = \left[\!\left[ (\tilde{x_1} \tilde{y_1}, \cdots, \tilde{x_d} \tilde{y_d}) \right]\!\right]$$ $$\left[\!\left[ < \mathbf{\tilde{x}},\mathbf{\tilde{y}}>\right]\!\right] = \sum_{i=1}^{\log_2(d)} \text{rot}(ct, 2^i)$$

Polynomial evaluation Under Encryption

    • Polynomial evaluation $$P(X) = a_0 + a_1 X + a_2 X^2 + \cdots + a_n X^n$$
    • Viewed as an inner product $P(X) = <\mathbb{a}, \mathbb{X}>$
      • $\mathbb{a} = (a_0, a_1, \cdots, a_n)$
      • $\mathbb{X} = (1, X^1, \cdots, X^n)$
    • Encrypted polynomial evaluation
      • Pt-Ct multiplication $ct = \mathbb{a} \times \left[\!\left[ \mathbb{X} \right]\!\right]$
      • Ct-Ct multiplication $ct = \left[\!\left[ \mathbb{a} \right]\!\right] \times \left[\!\left[ \mathbb{X} \right]\!\right]$
      $$\left[\!\left[ P(X) \right]\!\right] = \sum_{i=0}^{n} a_i \cdot \text{rot}(ct, i)$$

Matrix operations Under Encryption

Matrix-vector multiplication
Complexity
  • Additions: $2$
  • Multiplications: $n$ rows
  • Rotations: $3$
Latency
Medium latency that depends on the matrix dimension.
Applications
Neural Networks

Matrix operations Under Encryption

Matrix-Matrix multiplication
Complexity
  • Additions: $2$
  • Multiplications: $n \times m$
  • Rotations: $0$
Latency
High latency that depends on the dimensions of the matrices.
Application
Transformers

Takeaways

FHE offers data protection throughout its entire lifecycle.

Right security parameters
Adequate packing scheme
Minimize #Multiplications and #Rotations
Apply bootstrapping to avoid exhausting ciphertexts