SEAL: Homomorphic Encryption from Scratch

What if you could compute on data without ever seeing it? That's the promise of Homomorphic Encryption (HE). With HE, a cloud provider can run calculations on your encrypted data and return encrypted results. They never see your actual numbers.

This guide walks through SEAL (Simple Encrypted Arithmetic Library) from the ground up. We'll cover the math, the parameters, and the code. Each section starts simple, then goes deep.

01. What is Homomorphic Encryption?

Imagine you have a locked diary with your private numbers. With regular encryption, to add numbers you must unlock the diary (decrypt), do the math while it's open, then lock it again (encrypt). While it's open, anyone nearby can see your data.

Homomorphic encryption is different. It lets you do math while the diary stays locked. You can add numbers inside the locked diary, multiply them, and get correct results when you finally unlock it. The diary never needs to be opened for computation.

Why does this matter? Privacy. A cloud provider can compute on your encrypted health records, financial data, or personal information without ever seeing the actual values. You get results. They get nothing.

In mathematics, a homomorphism preserves structure. For encryption, this means operations on ciphertexts correspond to operations on plaintexts:

• Encrypt(a) + Encrypt(b) = Encrypt(a + b)
• Encrypt(a) × Encrypt(b) = Encrypt(a × b)

There are different levels of homomorphic encryption:

• Partially Homomorphic: Supports only addition (Paillier) or only multiplication (ElGamal)
• Somewhat Homomorphic: Supports limited operations before noise becomes too large
• Fully Homomorphic (FHE): Supports arbitrary arithmetic (addition and multiplication)

SEAL implements FHE. Each operation adds noise to the ciphertext. Too much noise breaks decryption. Parameter selection determines how many operations you can perform.

// STEP 1: Create encryption parameters
EncryptionParameters parms(scheme_type::bfv);
parms.set_poly_modulus_degree(8192);
parms.set_coeff_modulus(CoeffModulus::BFVDefault(8192));
parms.set_plain_modulus(PlainModulus::Batching(8192, 20));

// STEP 2: Create context (validates parameters)
SEALContext context(parms);

// STEP 3: Generate keys
KeyGenerator keygen(context);
SecretKey secret_key = keygen.secret_key();
PublicKey public_key;
keygen.create_public_key(public_key);

// STEP 4: Encrypt a number
Encryptor encryptor(context, public_key);
Plaintext pt("123");
Ciphertext ct;
encryptor.encrypt(pt, ct);  // ct = Encrypt(123)

// STEP 5: Compute on encrypted data (THE MAGIC!)
Evaluator evaluator(context);
evaluator.add_inplace(ct, ct);  // ct = Encrypt(123 + 123) = Encrypt(246)

// STEP 6: Decrypt to see result
Decryptor decryptor(context, secret_key);
Plaintext result;
decryptor.decrypt(ct, result);  // result = 246

02. Ring-LWE: The Security Foundation

SEAL's security is based on a math problem that's hard to solve, even for quantum computers. It's called Ring-LWE (Learning With Errors over polynomial rings).

Think of it like this: I give you a locked box with some noise inside. You can hear the noise, but you can't figure out what's making it. The noise obscures the secret.

In Ring-LWE, the "noise" is small random errors added to the data. Even knowing most of the information, finding the secret is computationally infeasible.

The LWE Problem: Given a random matrix A (public) and a vector b = As + e mod q (public), where s is the secret and e is small random noise, find s. This is believed to be hard even for quantum computers.

Ring-LWE: Instead of vectors and matrices, we use polynomials. This is more efficient for FHE because polynomial multiplication is faster than matrix multiplication.

The polynomial ring is defined as:

R_q = ℤ_q[X]/(X^N + 1)

Where:
- ℤ_q: coefficients are integers modulo q
- [X]: polynomials with variable X  
- /(X^N + 1): reduce modulo X^N + 1
- N: poly_modulus_degree (must be power of 2)

The key rule: X^N = -1 (mod X^N + 1). This means whenever we see X^N, we replace it with -1. This limits all polynomials to degree less than N.

The "+1" is crucial. Using X^N + 1 (a cyclotomic polynomial) provides:

• Security: Ring-LWE hardness guarantees
• Efficiency: Enables NTT (Number Theoretic Transform) for fast multiplication
• Batching: Enables SIMD operations (process N values in parallel)

// Example: Reduce 5x^6 + 3x^2 + 2 mod (X^4 + 1, 7)

// Step 1: Reduce polynomial (X^4 = -1)
// x^6 = x^4 * x^2 = (-1) * x^2 = -x^2
// 5x^6 = 5 * (-x^2) = -5x^2
// -5x^2 + 3x^2 = -2x^2

// Step 2: Reduce coefficients mod 7
// -2 mod 7 = 5

// Result: 5x^2 + 2

03. SEAL Parameters Explained

SEAL has three main parameters that control security, performance, and how many operations you can do. Think of them as knobs on a control panel:

• poly_modulus_degree: The "ring size" knob. Bigger = more secure but slower.
• coeff_modulus: The "noise budget" knob. More = more operations allowed.
• plain_modulus: The "number range" knob (BFV only). Defines what numbers you can encrypt.

poly_modulus_degree (N):

• Must be a power of 2: 4096, 8192, 16384, 32768
• Controls ring size and security level
• Larger N = higher security but slower operations
• Also determines batching capacity (can process N values in parallel)

// Security levels by poly_modulus_degree:
// 4096  → ~128-bit security (limited operations)
// 8192  → 128-bit security (standard)
// 16384 → 192-bit security
// 32768 → 256-bit security

coeff_modulus:

• Product of primes: q = q1 × q2 × ... × qk
• Each prime is typically ~60 bits
• More primes = more noise budget (but larger ciphertexts)
• Total bit size is constrained by security requirements

// For 128-bit security with N=8192:
parms.set_coeff_modulus(CoeffModulus::BFVDefault(8192));
// Returns ~180 bits total (3 primes of ~60 bits each)

plain_modulus (BFV only):

• Must be prime and coprime with coeff_modulus
• Defines plaintext range: integers in [0, t-1]
• For batching: use PlainModulus::Batching(N, bit_size)

// ~20-bit prime enables batching with 8192 slots
parms.set_plain_modulus(PlainModulus::Batching(8192, 20));
// Each slot can hold values 0 to ~1 million

// 128-bit secure BFV setup
EncryptionParameters parms(scheme_type::bfv);

// Ring size: 8192 (128-bit security, 8192 batching slots)
parms.set_poly_modulus_degree(8192);

// Noise budget: ~180 bits total
parms.set_coeff_modulus(CoeffModulus::BFVDefault(8192));

// Plaintext range: ~20-bit primes, enables batching
parms.set_plain_modulus(PlainModulus::Batching(8192, 20));

// Validate all parameters
SEALContext context(parms);

// Check if valid
if (!context.parameters_set()) {
    throw std::invalid_argument("Invalid parameters!");
}

04. Plaintext vs Plain Modulus

This trips up a lot of people. Plain modulus and plaintextsound similar but are completely different things.

Think of it like a shipping container. The plain modulus is the size of the container. It defines how big of an item you can fit. The plaintextis the actual item you put inside the container.

Plaintext appears at specific points in the encryption workflow:

• Before encryption: You create a Plaintext object containing your data
• After decryption: The result comes back as a Plaintext object
• With batching: You encode vectors into Plaintext, then decode back

// Plain Modulus: the PARAMETER (container size)
parms.set_plain_modulus(1024);  // Values must be 0-1023

// Plaintext: the DATA (actual item)
Plaintext pt("123");  // The number 123

// Full flow:
// 1. Create plaintext with your data
Plaintext pt("123");

// 2. Encrypt plaintext → ciphertext
Ciphertext ct;
encryptor.encrypt(pt, ct);  // ct = Enc(123)

// 3. Compute on ciphertext
evaluator.add_inplace(ct, ct);  // ct = Enc(246)

// 4. Decrypt ciphertext → plaintext
Plaintext result;
decryptor.decrypt(ct, result);  // result = "246"

05. R_t vs R_q: Two Different Spaces

SEAL uses two different "spaces" for data. One is small and efficient (for your actual data), the other is astronomically large (for security).

R_t (plaintext space) is like a small filing cabinet. It only needs to hold your actual numbers. If your numbers are 0-1000, a cabinet with 1000 slots is enough.

R_q (ciphertext space) is like a massive underground vault. It needs to be enormous to provide security. The noise and encryption overhead require huge numbers.

R_t = plaintext ring (BFV only):

• t = plain_modulus (a prime, e.g., 1024 or 2^20)
• Coefficients are modulo t
• Small: typically 20-60 bits
• Purpose: defines the range of values you can encrypt

R_q = ciphertext ring (both BFV and CKKS):

• q = coeff_modulus (product of primes, e.g., q1 × q2 × q3)
• Coefficients are modulo q
• Huge: typically 180-300 bits
• Purpose: provides security and room for noise

// R_t: Plaintext space (BFV only)
parms.set_plain_modulus(PlainModulus::Batching(8192, 20));
// t ≈ 2^20 (a prime)
// Plaintexts: R_t = ℤ_t[X]/(X^8192 + 1)
// Range: [0, ~1,000,000]

// R_q: Ciphertext space (both BFV and CKKS)
parms.set_coeff_modulus(CoeffModulus::BFVDefault(8192));
// q ≈ 2^180 (product of 3 primes)
// Ciphertexts: R_q = ℤ_q[X]/(X^8192 + 1)
// Range: [0, 2^180 - 1]  ← ASTRONOMICAL!

06. Scale Factor (CKKS Only)

CKKS works with real numbers like 3.14159. But here's the problem: polynomials only understand integers. You can't directly encrypt a decimal.

The solution is the scale factor. Multiply your decimal by a large number (like 2^40) to turn it into an integer. After computation, divide by the same number to get your decimal back.

The scale factor (typically 2^40) converts reals to integers:

• Encoding: real × scale → integer (then encrypt)
• Decoding: integer ÷ scale → real (after decrypt)
• Precision: 2^40 gives ~12 decimal digits of precision

The multiplication problem: When you multiply two scaled values, the scales also multiply:

Enc(3.14 × 2^40) × Enc(2.86 × 2^40)
= Enc(3.14 × 2.86 × 2^80)
= Enc(8.98 × 2^80)  ← Scale doubled!

This is why CKKS requires rescaling after multiplication:

// Set scale factor
double scale = pow(2.0, 40);  // 2^40 ≈ 1 trillion

// Encode real numbers with scale
vector<double> vec = {3.14159, 2.71828};
Plaintext pt;
ckks_encoder.encode(vec, scale, pt);  // Multiply by scale

// Encrypt
Ciphertext ct;
encryptor.encrypt(pt, ct);

// After multiplication: MUST rescale
evaluator.multiply(ct1, ct2, ct_result);
evaluator.rescale_to_next_inplace(ct_result);  // Divide by scale

// Decode after decryption
vector<double> result;
decryptor.decrypt(ct, pt);
ckks_encoder.decode(pt, result);  // Divide by scale

07. BFV vs CKKS Schemes

SEAL offers two schemes, each designed for different use cases:

BFV is like a regular calculator. It works with whole numbers and gives exact answers. 2 + 2 always equals 4, never 3.9999. Use it when you need precise counting: votes, inventory, database queries.

CKKS is like a scientific calculator. It works with decimals and gives approximate answers. 2.5 + 2.3 might equal 4.7999 instead of 4.8. Use it when small rounding errors don't matter: machine learning, averages, sensor data.

BFV (Brakerski-Fan-Vercauteren):

• Exact integer arithmetic
• Requires plain_modulus parameter
• Uses BatchEncoder for batching
• Input type: vector<uint64_t>
• Best for: counting, voting, exact queries

CKKS (Cheon-Kim-Kim-Song):

• Approximate real-number arithmetic
• No plain_modulus (uses scaling instead)
• Uses CKKSEncoder for encoding
• Input type: vector<double>
• Best for: ML, signal processing, scientific computing

// ========== BFV EXAMPLE (Exact Integers) ==========
EncryptionParameters bfv_parms(scheme_type::bfv);
bfv_parms.set_poly_modulus_degree(8192);
bfv_parms.set_coeff_modulus(CoeffModulus::BFVDefault(8192));
bfv_parms.set_plain_modulus(PlainModulus::Batching(8192, 20));

SEALContext bfv_context(bfv_parms);
BatchEncoder batch_encoder(bfv_context);  // For integers

// Encode and encrypt integers
vector<uint64_t> vec = {1, 2, 3, 4, 5, 6, 7, 8};
Plaintext pt;
batch_encoder.encode(vec, pt);
encryptor.encrypt(pt, ct);

// Result is EXACT
// {1,2,3,4,5,6,7,8} + {1,2,3,4,5,6,7,8} = {2,4,6,8,10,12,14,16}

// ========== CKKS EXAMPLE (Approximate Reals) ==========
EncryptionParameters ckks_parms(scheme_type::ckks);
ckks_parms.set_poly_modulus_degree(8192);
ckks_parms.set_coeff_modulus(
    CoeffModulus::Create(8192, {60, 40, 40, 60})
);
// Note: NO plain_modulus for CKKS!

SEALContext ckks_context(ckks_parms);
CKKSEncoder ckks_encoder(ckks_context);  // For reals

// Set scale for precision
double scale = pow(2.0, 40);  // ~12 decimal digits

// Encode and encrypt reals
vector<double> vec = {1.5, 2.3, 3.7, 4.1};
Plaintext pt;
ckks_encoder.encode(vec, scale, pt);
encryptor.encrypt(pt, ct);

// Result is APPROXIMATE
// {1.5, 2.3, 3.7, 4.1} + {0.5, 0.7, 0.3, 0.9} ≈ {2.0, 3.0, 4.0, 5.0}

Wrapping Up

If you take away a few things from this post:

1. Homomorphic encryption enables computation on encrypted data. The data stays private throughout the computation.
2. Ring-LWE provides the security. The noise makes it computationally infeasible to recover the secret.
3. Parameters control the trade-offs. poly_modulus_degree for security, coeff_modulus for noise budget, plain_modulus for value range.
4. Choose BFV for exact integers, CKKS for approximate reals. The right scheme depends on your use case.

SEAL is available on GitHub:microsoft/SEAL

Homomorphic encryption is still computationally expensive compared to regular computation, but it unlocks use cases that were previously impossible. When privacy is non-negotiable, HE delivers.