SEAL: Homomorphic Encryption from Scratch

Imagine a computer that does math on data it cannot read. This is Homomorphic Encryption (HE). A cloud provider can do calculations on your encrypted data and return encrypted results. The provider never sees your real numbers.

This post explains SEAL (Simple Encrypted Arithmetic Library) from the start. It covers the math, the parameters, and the code. Each section starts with a simple explanation. Then it gives the technical details.

What is homomorphic encryption?

Imagine a locked diary that holds your private numbers. With regular encryption, you must unlock the diary (decrypt) to add the numbers. Then you do the math while the diary is open. Then you lock it again (encrypt). While the diary is open, other people can see your data.

Homomorphic encryption is different. You do math while the diary stays locked. You can add and multiply the numbers inside the locked diary. When you unlock it, the results are correct. You never open the diary during the computation.

This matters because it protects privacy. A cloud provider can compute on your encrypted health records, financial data, or personal data. The provider never sees the real values. You get the results. The provider learns nothing.

In mathematics, a homomorphism keeps the structure of the data. For encryption, this means that an operation on ciphertexts matches the same operation on plaintexts:

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

There are three levels of homomorphic encryption:

• Partially homomorphic: supports only addition (Paillier) or only multiplication (ElGamal).
• Somewhat homomorphic: supports a limited number of operations before the noise becomes too large.
• Fully homomorphic (FHE): supports any arithmetic, both addition and multiplication.

SEAL implements FHE. Each operation adds noise to the ciphertext. If the noise becomes too large, decryption fails. The parameters you choose set the number of operations you can do.

// 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

Ring-LWE: the security base

The security of SEAL comes from a math problem that is hard to solve. Even quantum computers cannot solve it quickly. The problem is called Ring-LWE (Learning With Errors over polynomial rings).

Imagine a locked box with noise inside. You can hear the noise, but you cannot find what makes it. The noise hides the secret.

In Ring-LWE, the noise is a set of small random errors that the system adds to the data. An attacker can know most of the information. The attacker still cannot find the secret in a practical time.

The LWE problem: A random matrix A is public. A vector b = As + e mod q is also public. Here s is the secret and e is small random noise. The task is to find s. Researchers believe this is hard, even for quantum computers.

Ring-LWE: This version uses polynomials instead of vectors and matrices. It is more efficient for FHE because polynomial multiplication is faster than matrix multiplication.

The polynomial ring has this definition:

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 is X^N = -1 (mod X^N + 1). Each time X^N appears, you replace it with -1. This keeps the degree of all polynomials less than N.

The +1 is necessary. The polynomial X^N + 1 is a cyclotomic polynomial. It gives three benefits:

• Security: it gives the Ring-LWE hardness guarantees.
• Speed: it allows the NTT (Number Theoretic Transform), which makes multiplication fast.
• Batching: it allows SIMD operations, which 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

SEAL parameters

SEAL has three main parameters. They control security, speed, and the number of operations you can do. Think of them as knobs on a control panel:

• poly_modulus_degree: the ring size. A larger value gives more security but is slower.
• coeff_modulus: the noise budget. A larger value allows more operations.
• plain_modulus: the number range (BFV only). It sets which numbers you can encrypt.

poly_modulus_degree (N):

• It must be a power of 2: 4096, 8192, 16384, or 32768.
• It sets the ring size and the security level.
• A larger N gives higher security but slower operations.
• It also sets the batching capacity. SEAL 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:

• It is a product of primes: q = q1 × q2 × ... × qk.
• Each prime is usually about 60 bits.
• More primes give more noise budget but larger ciphertexts.
• The security requirements limit the total bit size.

// 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):

• It must be prime and coprime with coeff_modulus.
• It sets the 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!");
}

Plaintext and plain modulus

Many people confuse these two terms. The plain modulus and the plaintext sound similar, but they are different things.

Think of a shipping container. The plain modulus is the size of the container. It sets the size of the item that fits inside. The plaintext is the item you put in the container.

Plaintext appears at specific points in the encryption workflow:

• Before encryption: you create a Plaintext object that holds your data.
• After decryption: the result is a Plaintext object.
• With batching: you encode vectors into Plaintext, then decode them again.

// 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"

R_t and R_q: two spaces

SEAL uses two different spaces for data. One space is small and efficient. It holds your real data. The other space is very large. It gives security.

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

R_q (ciphertext space) is like a large underground vault. It must be very large for security. The noise and the encryption overhead need large numbers.

R_t is the plaintext ring (BFV only):

• t is plain_modulus. It is a prime, for example 1024 or 2^20.
• The coefficients are modulo t.
• It is small: usually 20 to 60 bits.
• It sets the range of values you can encrypt.

R_q is the ciphertext ring (BFV and CKKS):

• q is coeff_modulus. It is a product of primes, for example q1 × q2 × q3.
• The coefficients are modulo q.
• It is large: usually 180 to 300 bits.
• It gives 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!

Scale factor (CKKS only)

CKKS works with real numbers such as 3.14159. But polynomials use only integers. You cannot encrypt a decimal directly.

The solution is the scale factor. You multiply your decimal by a large number, for example 2^40. This gives an integer. After the computation, you divide by the same number to get your decimal again.

The scale factor (usually 2^40) changes reals into integers:

• Encoding: real × scale gives an integer. Then you encrypt it.
• Decoding: integer ÷ scale gives a real. You do this after decryption.
• Precision: 2^40 gives about 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!

For this reason, CKKS needs rescaling after each 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

BFV and CKKS schemes

SEAL has two schemes. Each scheme fits different uses.

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

CKKS is like a scientific calculator. It works with decimals and gives approximate answers. 2.5 + 2.3 can give 4.7999 instead of 4.8. Use it when small rounding errors are acceptable, such as machine learning, averages, or sensor data.

BFV (Brakerski-Fan-Vercauteren):

• It does exact integer arithmetic.
• It needs the plain_modulus parameter.
• It uses BatchEncoder for batching.
• The input type is vector<uint64_t>.
• Best for: counting, voting, and exact queries.

CKKS (Cheon-Kim-Kim-Song):

• It does approximate real-number arithmetic.
• It has no plain_modulus. It uses scaling instead.
• It uses CKKSEncoder for encoding.
• The input type is vector<double>.
• Best for: ML, signal processing, and 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}

Summary

This post makes four main points:

1. Homomorphic encryption lets you compute on encrypted data. The data stays private during the computation.
2. Ring-LWE gives the security. The noise makes it impractical to recover the secret.
3. Parameters control the trade-offs. poly_modulus_degree sets security. coeff_modulus sets the noise budget. plain_modulus sets the value range.
4. Choose BFV for exact integers and CKKS for approximate reals. The correct scheme depends on your use case.

SEAL is available on GitHub: microsoft/SEAL

Homomorphic encryption needs more computing power than regular computation. But it allows uses that were not possible before. When data must stay private, HE is a good choice.