Abstract Algebra · Cryptography · Post-Quantum Security

Homomorphic
Encryption
of Commutative Rings

Explore the mathematical foundations of computing on encrypted data — from the algebraic structure of commutative rings to fully homomorphic encryption schemes that preserve ring operations under ciphertext.

The Homomorphic Property

\text{Dec}(\text{Eval}(f,\, \text{Enc}(m_1),\ldots,\text{Enc}(m_t))) = f(m_1,\ldots,m_t)

Ring Structureℤ_q[X]/(Xⁿ+1)

Security BasisRLWE Problem

SchemeBFV / BGV

Quantum SafeLattice-Based

scroll

Chapter I

Commutative Ring Theory

Homomorphic encryption is fundamentally an algebraic construction. To understand it, we must first understand the ring structures that underpin modern cryptographic schemes.

Definition

Ring (R, +, ·)

A ring is a set R equipped with two binary operations — addition (+) and multiplication (·) — satisfying:

• (R, +) is an abelian group with identity 0
• (R, ·) is a monoid with identity 1
• Multiplication distributes over addition

A ring is commutative when $a \cdot b = b \cdot a$ for all $a, b \in R$ .

Definition

Ideal and Quotient Ring

An ideal $I \subseteq R$ is a subring that absorbs multiplication: for all $r \in R$ and $i \in I$ , we have $r \cdot i \in I$ .

The quotient ring $R/I$ consists of cosets $\{a + I : a \in R\}$ with operations inherited from R. This construction is central to building the polynomial rings used in HE.

Definition

Ring Homomorphism

A map $\varphi: R \to S$ is a ring homomorphism if it preserves both operations:

\varphi(a + b) = \varphi(a) + \varphi(b), \quad \varphi(a \cdot b) = \varphi(a) \cdot \varphi(b)

The kernel $\ker(\varphi) = \{r \in R : \varphi(r) = 0\}$ is always an ideal of R. By the First Isomorphism Theorem, $R/\ker(\varphi) \cong \text{Im}(\varphi)$ .

Example

The Cryptographic Ring R_q

The polynomial ring used in BFV and BGV schemes is:

Central Ring

R_q = \mathbb{Z}_q[X]/(X^n + 1)

Here $n$ is a power of 2 (e.g., 1024), $q$ is a large prime, and elements are polynomials of degree $< n$ with coefficients in $\mathbb{Z}_q$ . The relation $X^n \equiv -1$ enables efficient NTT-based multiplication.

Commutative ring structure with homomorphisms φ between rings

Ring Examples

\mathbb{Z}

The integers with standard addition and multiplication. The prototypical commutative ring.

Addition

3 + 5 = 8

Multiplication

3 × 5 = 15

Key Property: Chinese Remainder Theorem

When $X^n + 1$ splits into linear factors mod a prime $q$ , the CRT gives an isomorphism:

R_q \cong \mathbb{Z}_q^n

This enables SIMD batching — encrypting n values simultaneously and operating on all of them in parallel.

Chapter II

Homomorphic Encryption

A homomorphic encryption scheme allows computation on ciphertexts such that decrypting the result yields the same answer as computing on the plaintexts directly.

The Fundamental Property

An encryption scheme (KeyGen, Enc, Dec, Eval) is homomorphic with respect to a function class $\mathcal{F}$ if for every $f \in \mathcal{F}$ :

Homomorphic Property

\text{Dec}_{sk}\!\left(\text{Eval}_{pk}\!\left(f,\, \text{Enc}_{pk}(m_1),\ldots,\text{Enc}_{pk}(m_t)\right)\right) = f(m_1,\ldots,m_t)

The evaluation is performed using only the public key — the server never sees the plaintext messages $m_1, \ldots, m_t$ and does not need the secret key $sk$ .

Alice's Privacy-Preserving Computation

1Alice encrypts her sensitive data:

c = \text{Enc}_{pk}(m)

2Bob computes on the ciphertext:

c' = \text{Eval}(f, c)

3Alice decrypts to get the result:

\text{Dec}_{sk}(c') = f(m)

Types of Homomorphic Encryption

PHEPartially Homomorphic

Supports one operation (+ or ×) an unlimited number of times.

Unlimited depth, one operation·RSA (multiplicative), Paillier (additive)

SHESomewhat Homomorphic

Supports both + and × but only for a limited circuit depth before noise overwhelms.

Limited depth, both operations·Early lattice-based schemes

LHELeveled Homomorphic

Supports circuits up to a predetermined depth L, set at key generation time.

Fixed depth L, both operations·BFV, BGV with fixed levels

FHEFully Homomorphic

Supports arbitrary computations of any depth. Achieved via bootstrapping.

Unlimited depth, all operations·Gentry 2009, TFHE, CKKS

The Ring Learning With Errors Problem

The security of BFV and BGV rests on the computational hardness of the Ring Learning With Errors (RLWE) problem, introduced by Lyubashevsky, Peikert, and Regev in 2010.

RLWE Problem

Given samples $(a_i, b_i) \in R_q \times R_q$ where:

b_i = a_i \cdot s + e_i \pmod{q}

with secret $s \in R_q$ and small error $e_i \leftarrow \chi_\sigma$ , it is computationally hard to distinguish these from uniformly random pairs.

This problem is believed to be hard even for quantum computers, making RLWE-based encryption a leading candidate for post-quantum cryptography. The NIST PQC standardization process selected several RLWE-based schemes.

Why Rings?

The original LWE problem operates over vectors in $\mathbb{Z}_q^n$ , requiring $O(n^2)$ space for keys. Moving to the ring $R_q$ reduces this to $O(n)$ while maintaining comparable security, enabling practical implementations.

Noise Management

Every ciphertext carries a small noise term $e$ . Operations grow the noise:

Addition:‖e₁ + e₂‖ ≈ ‖e₁‖ + ‖e₂‖

Multiplication:‖e₁ · e₂‖ ≈ n · ‖e₁‖ · ‖e₂‖

Bootstrapping:Resets noise to fresh level

Security Parameter

Security level $\lambda$ (bits) determines parameter sizes. For 128-bit security: $n \geq 1024$ , $\log_2 q \approx 27$ . Larger $n$ allows deeper circuits but increases computation time.

Chapter III

Encryption Schemes

Three major ring-based homomorphic encryption schemes, each with distinct approaches to noise management and plaintext representation.

BFV

Brakerski/Fan-Vercauteren (2012)

Scaling-based noise management for integer arithmetic

Ring:

R_q = \mathbb{Z}_q[X]/(X^n+1)

Plaintext:

R_t = \mathbb{Z}_t[X]/(X^n+1)

Ciphertext:

R_q^2

Key Feature

Uses a scaling factor Δ = ⌊q/t⌋ to embed plaintext in the high-order bits of the ciphertext modulus.

Supported Operations

Homomorphic addition
Homomorphic multiplication
Relinearization
Modulus switching

KeyGen

sk = s \leftarrow R_2, \quad pk = (-as + e,\, a) \in R_q^2

Secret key is a small binary polynomial. Public key masks it with random a and error e.

Scheme Comparison

Property	BFV	BGV	CKKS
Plaintext Type	Integers mod t	Integers mod t	Approx. reals
Noise Strategy	Scaling (Δ=⌊q/t⌋)	Mod switching	Rescaling
Best For	Exact arithmetic	Deep circuits	ML / approx.
Bootstrapping	Supported	Supported	Supported

Chapter IV

Interactive Scheme Demos

Walk through live encryption cycles for all three major ring-based HE schemes — BFV for exact integers, BGV with modulus switching, and CKKS for approximate real arithmetic.

BFV — Brakerski/Fan-Vercauteren (2012)

Exact integer arithmetic mod t. Plaintext embedded in high-order bits via Δ = ⌊q/t⌋.

Ring Parameters

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

n (degree)

Polynomial degree

q (ct mod)

Ciphertext modulus

t (pt mod)

Plaintext modulus

Δ = ⌊q/t⌋ = 36 | Security: educational only

Key Generation

Generate a fresh key pair. The secret key s is a small binary polynomial; the public key masks it with random a and error e.

Plaintext Messages

Message m₁

Range: 0 to 6

Message m₂

Range: 0 to 6

Expected sum: 3 + 2 = 5 (mod 7)

🔐

Complete the steps on the left to see the encryption process unfold here.

Start with: Generate Keys →

The Ring Homomorphism in Action

\text{Dec}(\text{Enc}(m_1) + \text{Enc}(m_2)) = m_1 + m_2 \pmod{t}

The encryption map Enc: R_t → R_q² is a ring homomorphism with respect to addition. This is the fundamental property that makes homomorphic encryption possible.

Chapter V

Applications & Impact

Homomorphic encryption over commutative rings is transitioning from theoretical curiosity to practical deployment across industries where data privacy is paramount.

🏥

Healthcare

Privacy-Preserving Medical Analysis

Hospitals can run diagnostic models on encrypted patient data. The model provider never sees the raw records, and the patient never reveals sensitive health information.

Compute f(encrypted_genome) → encrypted_diagnosis

🏦

Finance

Secure Financial Computation

Banks can compute credit scores, fraud detection, and portfolio analysis on encrypted financial data without exposing individual transaction histories.

Σ encrypted_transactions → encrypted_balance

🤖

AI / ML

Private Machine Learning

Train and run ML models on encrypted data. CKKS enables neural network inference where neither the model weights nor the input data are revealed to the other party.

NN(encrypted_input) → encrypted_prediction

🗳️

Governance

Verifiable Electronic Voting

Votes are encrypted and tallied homomorphically. The final count can be verified without ever decrypting individual votes, ensuring both privacy and integrity.

Σ encrypted_votes → encrypted_tally

☁️

Cloud

Secure Cloud Computing

Outsource computation to untrusted cloud providers. The cloud performs operations on encrypted data and returns encrypted results — the cloud learns nothing.

Cloud.Eval(f, Enc(data)) → Enc(f(data))

🔬

Genomics

Genomic Research

Researchers can run genome-wide association studies across encrypted datasets from multiple institutions without sharing raw genomic sequences.

GWAS(Enc(genome₁), ..., Enc(genomeₙ))

Historical Timeline

1978

RSA — first multiplicatively homomorphic scheme

Rivest, Shamir, Adleman

1999

Paillier — additively homomorphic scheme

Pascal Paillier

2009

Gentry's FHE — first fully homomorphic scheme

Craig Gentry

2011

BGV — practical leveled FHE over rings

Brakerski, Gentry, Vaikuntanathan

2012

BFV — improved FHE with scaling

Brakerski; Fan, Vercauteren

2016

CKKS — approximate FHE for real numbers

Cheon, Kim, Kim, Song

2020

TFHE — fast bootstrapping in microseconds

Chillotti et al.

2024

NIST PQC standards include lattice-based schemes

NIST

Gentry's Bootstrapping Theorem (2009)

Any somewhat homomorphic encryption scheme that can evaluate its own decryption circuit (plus one more NAND gate) can be converted into a fully homomorphic encryption scheme.

\mathcal{E}

is SHE and

\text{Dec}_\mathcal{E} \in \mathcal{C}_\mathcal{E}

, then

\mathcal{E}

can be bootstrapped to FHE.

HomomorphicEncryptionof Commutative Rings

Commutative Ring Theory

Homomorphic Encryption

The Fundamental Property

Types of Homomorphic Encryption

The Ring Learning With Errors Problem

Encryption Schemes

KeyGen

Interactive Scheme Demos

Applications & Impact

Privacy-Preserving Medical Analysis

Secure Financial Computation

Private Machine Learning

Verifiable Electronic Voting

Secure Cloud Computing

Genomic Research

Historical Timeline

Homomorphic
Encryption
of Commutative Rings