Homomorphic Encryption Fundamentals

Understanding the core HE schemes, noise management, and bootstrapping. These fundamentals will help you choose the right scheme and parameters for your ML application.

The CKKS Scheme

CKKS (Cheon-Kim-Kim-Song, 2017) is the most important HE scheme for ML because it supports approximate arithmetic on real and complex numbers - exactly what neural networks need.

• Approximate arithmetic: Results have small rounding errors (similar to floating point), which is perfectly acceptable for ML.
• SIMD packing: A single ciphertext can encode thousands of values in parallel slots, enabling efficient vector operations.
• Rescaling: After multiplication, a rescaling operation manages the scale of encoded values, trading multiplicative depth for precision.

The BFV/BGV Schemes

BFV (Brakerski/Fan-Vercauteren) and BGV (Brakerski-Gentry-Vaikuntanathan) support exact arithmetic on integers modulo a plaintext modulus:

• Results are exact (no approximation error)
• Best for integer operations: counting, comparison, lookup tables
• Less natural for neural network inference (which uses real numbers)

Noise and Multiplicative Depth

Every HE ciphertext contains a small amount of noise that grows with each operation:

Bootstrapping

Bootstrapping is the process of "refreshing" a noisy ciphertext by homomorphically evaluating the decryption circuit. It resets the noise level, allowing further computations:

• Converts a Somewhat HE scheme into a Fully HE scheme
• Extremely expensive: 100-1000x slower than a single multiplication
• Best avoided when possible by designing circuits with shallow multiplicative depth
• TFHE scheme uses fast bootstrapping as a core operation (different design philosophy)

Parameter Selection

HE parameters determine the trade-off between security, performance, and capability:

Ring dimension (N):
  - Determines security level and number of SIMD slots
  - Typical values: 4096, 8192, 16384, 32768
  - Larger N = more secure, more slots, but slower

Coefficient modulus (Q):
  - Chain of primes that determines multiplicative depth
  - More primes = deeper circuits but larger ciphertexts
  - Each multiplication "consumes" one prime level

Scale (CKKS only):
  - Precision of encoded real numbers
  - Typical: 2^40 (about 12 decimal digits)

Security level:
  - 128-bit security is standard
  - Parameters must satisfy lattice security estimates
  - Use Homomorphic Encryption Standard parameters