Homomorphic Encryption: Computing on Ciphertext

A Bengaluru hospital wants a third-party AI startup to run a diabetes-risk model over its patient records — blood glucose trends, BMI, family history, prescription data. The startup has a good model. The hospital has good data. Under India's Digital Personal Data Protection Act, 2023, the hospital cannot simply export raw patient records to an external processor without consent, purpose limitation, and a defensible security posture — and even with consent, "we sent our patients' medical histories to a startup's cloud account" is not a sentence any hospital's legal team wants to sign off on. The startup, for its part, doesn't actually want the liability of holding raw health data either.

The obvious fix — "encrypt the records before sending them" — normally just moves the problem. Standard encryption (AES, RSA) is built so that ciphertext is computationally opaque: you cannot average a column of AES-encrypted glucose readings any more than you can average a column of random noise. To run the risk model, someone has to decrypt first. That someone becomes the single point of trust and the single point of failure — exactly the party the hospital was trying to avoid trusting.

Homomorphic encryption (HE) is the answer to a narrower, sharper question: can an encryption scheme be built so that specific mathematical operations on the ciphertexts correspond to the same operations on the underlying plaintexts — so that a party holding only ciphertext, and never the key, can still produce a ciphertext that decrypts to the correct answer? If yes, the hospital encrypts locally, ships ciphertext, the startup's model runs entirely on ciphertext, and only an encrypted risk score comes back — which only the hospital, holding the secret key, can open. The startup never sees a glucose reading. The cloud in between never sees one either. This is not a hypothetical; it is the design goal behind real deployments in healthcare analytics, encrypted database queries, and private financial aggregation, and it is the subject of this chapter.

What "computing on ciphertext" actually means

Strip away the cryptographic machinery and homomorphic encryption is a statement in abstract algebra: encryption is a function Enc that maps a plaintext space (M, ⊕) — a set of messages with some operation ⊕ defined on them, usually addition or multiplication — into a ciphertext space (C, ⊗) with its own operation ⊗. The scheme is homomorphic with respect to ⊕ if, for every pair of messages m₁, m₂:

Enc(m1) ⊗ Enc(m2)  =  Enc(m1 ⊕ m2)

Read the equation carefully — it is doing more work than it looks like. The left side is computed by someone who has never seen m₁ or m₂ and has no key: they only have two ciphertexts and the operation ⊗. The right side is the ciphertext you would have gotten by encrypting the combined plaintext directly. The equation says these are the same ciphertext (or, in randomized schemes, ciphertexts that decrypt to the same plaintext). Decrypting the left side therefore recovers m₁ ⊕ m₂ without decryption ever having touched m₁ or m₂ individually. This is precisely a group homomorphism in the algebraic sense you meet in ring and group theory: Enc doesn't just scramble messages, it preserves structure across the map from (M, ⊕) to (C, ⊗).

This immediately tells you what HE is not. It is not "encryption that happens to let a server sneak a look at your data while computing." The server performs group operations — modular multiplication, polynomial addition, whatever ⊗ is for that scheme — on elements it cannot distinguish from random. It never runs Dec. It cannot run Dec; it does not hold the secret key. Correctness of the final answer is a theorem about algebra, not a claim about the server's behavior.

Three tiers: how much homomorphism you get

Not every scheme supports every operation, and this distinction is where most of the engineering difficulty in the field actually lives.

Partially Homomorphic Encryption (PHE) supports exactly one operation — either addition or multiplication — an unlimited number of times, cheaply. Unpadded (textbook) RSA is multiplicatively homomorphic. ElGamal is multiplicatively homomorphic. The Paillier cryptosystem (1999) is additively homomorphic. You get one algebraic operation for free, forever, but you cannot mix in the other one.

Somewhat Homomorphic Encryption (SHE) supports both addition and multiplication, but only up to a bounded circuit depth — typically a handful of sequential multiplications — before accumulated "noise" in the ciphertext overwhelms the signal and decryption stops working. You get real arithmetic circuits, but with a fuel gauge that runs out.

Fully Homomorphic Encryption (FHE) supports both operations an unbounded number of times on arbitrary circuits — which means, since AND/OR/NOT gates can be built from addition and multiplication over the right ring, arbitrary computation on ciphertext. This was an open problem from 1978 (when Rivest, Adleman, and Dertouzos first posed it, in the same paper lineage as RSA) until Craig Gentry's 2009 lattice-based construction, which solved the noise-accumulation problem with a technique called bootstrapping, covered below. FHE is what makes "run any risk model on encrypted patient data" possible in principle — at a computational cost that is still the field's central engineering constraint.

Worked example 1: RSA's accidental multiplicative homomorphism

Take the standard textbook RSA parameters used in most first cryptography courses: primes p = 61, q = 53, so n = pq = 3233 and φ(n) = 60·52 = 3120. Choose public exponent e = 17 (coprime to 3120), and the matching private exponent d = 2753, satisfying ed ≡ 1 (mod φ(n)) — check: 17 × 2753 = 46801 = 15 × 3120 + 1. RSA encryption is Enc(m) = m^e mod n; decryption is Dec(c) = c^d mod n.

Encrypt two messages, m₁ = 65 and m₂ = 15:

n, e, d = 3233, 17, 2753          # p=61, q=53 (textbook RSA)
m1, m2 = 65, 15

c1 = pow(m1, e, n)                 # Enc(m1)
c2 = pow(m2, e, n)                 # Enc(m2)
c_prod = (c1 * c2) % n             # ciphertext-space operation

recovered = pow(c_prod, d, n)      # Dec(c1 * c2 mod n)
print(c1, c2, c_prod, recovered)

Trace it by hand. c1 = 65¹⁷ mod 3233 = 2790. c2 = 15¹⁷ mod 3233 = 3031. Multiply the ciphertexts and reduce: c1 · c2 = 8,456,490, and 8,456,490 mod 3233 = 2195. Decrypt that product: 2195²⁷⁵³ mod 3233 = 975. Now check against direct plaintext multiplication: 65 × 15 = 975, and since 975 < 3233 no reduction is even needed. The printed line is 2790 3031 2195 975, and the last two numbers match exactly as the homomorphism predicts: Dec(Enc(m1) · Enc(m2) mod n) = m1 · m2 mod n, with no decryption ever applied to c1 or c2 individually.

Why does this work algebraically, in one line? c1 · c2 ≡ m1^e · m2^e ≡ (m1·m2)^e (mod n), because exponentiation distributes over multiplication. Raising to the d-th power and using ed ≡ 1 (mod φ(n)) together with Euler's theorem gives ((m1·m2)^e)^d ≡ m1·m2 (mod n). The homomorphism isn't a special trick bolted onto RSA — it falls straight out of the fact that modular exponentiation is itself a group homomorphism from (ℤ_n*, ×) to itself.

This is also exactly why real-world RSA is never deployed this way. Every production RSA implementation pads the message first — RSA-OAEP being the modern standard — specifically to destroy this multiplicative structure, because an attacker who can get a target to decrypt a chosen ciphertext, combined with the ability to multiply ciphertexts freely, can forge signatures and mount chosen-ciphertext attacks. The same algebraic property that makes RSA a beautiful two-line demonstration of homomorphism is a vulnerability the moment RSA is used for anything security-critical without padding. Homomorphism, in other words, is not automatically a feature — it is a property you either want and design for deliberately, or actively engineer away.

Worked example 2: Paillier's additive homomorphism

Paillier (1999) is a PHE scheme built specifically to be additively homomorphic, and it is the workhorse behind private-sum applications — Google's Private Join and Compute protocol, for instance, uses additive homomorphic encryption of exactly this kind so that two organizations can compute a joint total (say, total ad-attributed revenue) without either side seeing the other's individual records. Here is the full mechanism on small numbers, small enough to trace by hand.

Pick primes p = 7, q = 11. Then n = 77, n² = 5929, and use the simplified generator g = n + 1 = 78. Let λ = lcm(p−1, q−1) = lcm(6, 10) = 30. Encryption of message m with fresh randomness r (coprime to n) is:

Enc(m, r) = g^m · r^n mod n²

and decryption, using the standard Paillier reduction function L(x) = (x − 1) / n and the precomputed constant μ = L(g^λ mod n²)⁻¹ mod n, is:

Dec(c) = L(c^λ mod n²) · μ mod n

import math

p, q = 7, 11
n = p * q                          # 77
n2 = n * n                         # 5929
g = n + 1                          # 78 (simplified generator)
lam = (p - 1) * (q - 1) // math.gcd(p - 1, q - 1)   # lcm(6, 10) = 30

def L(x):
    return (x - 1) // n

mu = pow(L(pow(g, lam, n2)), -1, n)   # 18

def encrypt(m, r):
    return (pow(g, m, n2) * pow(r, n, n2)) % n2

def decrypt(c):
    return (L(pow(c, lam, n2)) * mu) % n

c1 = encrypt(15, 4)                # Enc(15) with randomness r=4
c2 = encrypt(22, 9)                # Enc(22) with randomness r=9
c_sum = (c1 * c2) % n2             # ciphertext-space "addition"

print(c1, c2, c_sum, decrypt(c_sum))

Trace it: μ works out to 18. c1 = Enc(15, 4) = 478. c2 = Enc(22, 9) = 81. The cloud-side operation is ordinary multiplication of ciphertexts modulo n²: c_sum = (478 × 81) mod 5929 = 38,718 mod 5929 = 3144. Decrypting that single number gives L(3144³⁰ mod 5929) × 18 mod 77 = 37. The printed line is 478 81 3144 37, and 37 is exactly 15 + 22 — recovered from a ciphertext product, never from decrypting 478 or 81 individually. This is the additive mirror image of the RSA example: because Paillier encryption embeds the message in the exponent of g, multiplying ciphertexts adds exponents, which adds plaintexts. It is the same abstract-algebra move — pushing an operation from the plaintext group into a corresponding operation on the ciphertext group — applied to a different underlying structure, which is exactly why RSA gives you multiplication for free and Paillier gives you addition for free, and neither gives you both.

The misconception worth killing

The single most common misreading of this topic is assuming that the party doing the computing — the cloud, the untrusted server — must be decrypting the data at some point to "do math" on it, and that homomorphic encryption is just a convenient wrapper that hides an underlying decrypt-compute-recrypt cycle from the user. It is not. Look again at what the cloud server actually executes in both worked examples: a modular multiplication of two integers. That is the entire computational step. The server never calls a decryption function, never sees m1 or m2, and structurally cannot recover them from c1 and c2 alone without solving the same hard problem (integer factorization for RSA, the composite residuosity problem for Paillier) that makes the scheme secure in the first place. The correctness of the final decrypted answer is guaranteed by algebra — the homomorphism proof you traced above — not by any privileged access the server has at any point in the pipeline.

A second, closely related misconception is treating "homomorphic encryption" as one scheme that does everything — add, multiply, unlimited times, cheaply. It doesn't exist in that form and probably can't at low cost: RSA and Paillier are each locked to exactly one operation forever (PHE); getting both operations costs you either a hard bound on how much computation you can do before the ciphertext becomes garbage (SHE) or a genuinely expensive machine (FHE) built to periodically "clean" ciphertexts as they compute. Knowing which tier a scheme sits in — one operation forever, both operations for a while, or both operations forever at a price — is the first design question in any real system, not an afterthought.

Mechanism

Noise, bootstrapping, and why FHE is expensive

PHE schemes like RSA and Paillier give you their one operation cleanly, forever — the algebra above never degrades no matter how many times you multiply ciphertexts together. SHE and FHE schemes pay for supporting both addition and multiplication with a resource that has no analogue in plaintext computation: noise. Lattice-based FHE schemes (the family Gentry's 2009 construction started, refined into today's BGV, BFV, and CKKS schemes) encrypt a message by hiding it underneath a small random error term relative to a hard lattice problem. Decryption works by removing that error term — but every ciphertext addition roughly adds the two noise terms, and every ciphertext multiplication roughly multiplies them. Addition is cheap on the noise budget; multiplication is what burns through it. After enough multiplications, the noise term grows large enough to swamp the signal, and decryption returns garbage — this is exactly the wall that limits SHE schemes to a bounded circuit depth.

Gentry's insight for breaking through that wall was bootstrapping: homomorphically evaluate the scheme's own decryption circuit, using an encrypted copy of the secret key, on a noisy ciphertext — producing a fresh, low-noise encryption of the same plaintext, without the server ever learning the plaintext or the real secret key. It sounds almost circular — "use encryption to decrypt, in order to keep encrypting" — and that circularity is exactly the trick: the decryption circuit runs entirely inside the ciphertext space, so its own output is itself a ciphertext, refreshed rather than exposed. Bootstrapping is also, consistently, the single most expensive operation in an FHE pipeline; production systems try to minimize how often they need to invoke it, and a large fraction of FHE scheme design is really noise-budget engineering — packing more useful computation between bootstraps.

The upshot for system design: FHE evaluation is commonly benchmarked in the literature at somewhere between three and six orders of magnitude slower than the equivalent plaintext computation, depending on the scheme, circuit depth, and whether hardware acceleration is available — a qualitative characteristic of the field rather than a number worth memorizing precisely, since it shifts with each generation of libraries. Real deployments (Microsoft SEAL, IBM's HElib, Zama's TFHE-rs) lean hard into this constraint: they pick the narrowest tier of homomorphism the task actually needs. A private-sum aggregation — like Google's Private Join and Compute computing a joint revenue total across two companies without either seeing the other's rows — only needs additive PHE, so it uses Paillier at PHE's cost, not FHE's. A genuine fraud-detection model that needs additions, multiplications, and threshold comparisons over encrypted UPI transaction data needs FHE, and has to budget for the corresponding latency and ciphertext expansion (FHE ciphertexts routinely run tens to hundreds of times larger than the plaintext they encode). Choosing the right tier — PHE, SHE, or FHE — for the actual computation required is the real engineering decision this chapter has been building toward.

Active recall

Attempt these before reading the answers.

1. Is unpadded RSA's multiplicative homomorphism a security feature or a vulnerability in real-world deployments — and why do standards like RSA-OAEP deliberately destroy it?
2. A hospital encrypts three risk scores m = (10, 20, 5) under Paillier (same n = 77 as the worked example) using independent random values, and a cloud server multiplies all three ciphertexts together mod n². What plaintext does decryption of that product recover?
3. A scheme supports both ciphertext addition and multiplication, but only up to depth-4 circuits before accumulated noise makes decryption fail, and it has no bootstrapping step. Which tier does it belong to: PHE, SHE, or FHE?
4. Bootstrapping is sometimes described as "using encryption to decrypt itself." What problem does it actually solve, and what does it cost?
5. A fintech company wants to run a fraud-detection model — additions, multiplications, and comparisons — on encrypted UPI transaction data hosted on a third-party cloud, with neither the cloud nor a data breach ever exposing raw amounts. Which HE tier is required, and name one concrete cost this imposes that a pure-summation use case wouldn't pay.
6. In the RSA worked example, derive in one line why decrypting c1 · c2 mod n recovers m1 · m2 mod n exactly.

Answers.

1. It is a vulnerability, not a feature, once RSA is used for real signing or encryption. An attacker who can obtain a decryption (or signature) of ciphertexts they choose, combined with the ability to multiply ciphertexts freely, can forge decryptions or signatures for messages they never had legitimately signed — a chosen-ciphertext attack. OAEP padding embeds randomness and structure into the message before exponentiation specifically so that c1 · c2 no longer decrypts to any meaningful combination of m1 and m2, closing that attack path. The same property that makes textbook RSA a clean two-line homomorphism demo is exactly what production RSA is engineered to eliminate.

2. 35. Paillier's ciphertext multiplication corresponds to plaintext addition mod n: Dec(c1·c2·c3 mod n²) = (m1 + m2 + m3) mod n = (10+20+5) mod 77 = 35. Since 35 < 77, no wraparound occurs and the recovered value equals the true sum exactly.

3. SHE (Somewhat Homomorphic Encryption). Supporting both operations distinguishes it from PHE (which supports only one, but unlimited times); the hard bound on circuit depth with no bootstrapping to refresh noise distinguishes it from FHE (unbounded depth via periodic bootstrapping).

4. Bootstrapping solves noise accumulation: it homomorphically evaluates the scheme's own decryption circuit on a noisy ciphertext, using an encrypted copy of the secret key, producing a fresh low-noise ciphertext encrypting the same plaintext — without the plaintext or the real secret key ever being exposed to whoever runs the computation. It is the mechanism that turns bounded-depth SHE into unbounded-depth FHE. The cost is computational: bootstrapping is consistently the single most expensive step in an FHE pipeline, and minimizing how often it must run is a central design concern for any real system built on FHE.

5. FHE is required, because fraud detection needs both additions and multiplications (and comparisons, typically approximated as polynomial circuits) evaluated together — no PHE scheme supports both, and SHE would run out of noise budget on a model of realistic depth without bootstrapping. The concrete cost this imposes, compared to a pure-summation task that Paillier (PHE) could handle cheaply: substantially higher computational latency — commonly several orders of magnitude versus plaintext — plus significant ciphertext expansion (each encrypted value occupying far more space than its plaintext), and the recurring cost of bootstrapping to keep noise under control across the model's full depth.

6. c1·c2 ≡ m1^e·m2^e ≡ (m1·m2)^e (mod n), since modular exponentiation distributes over multiplication; raising both sides to the d-th power and using ed ≡ 1 (mod φ(n)) together with Euler's theorem gives ((m1·m2)^e)^d ≡ m1·m2 (mod n) — the homomorphism is a direct consequence of RSA's exponentiation being a group homomorphism on (ℤ_n*, ×), not a coincidence specific to the chosen numbers.

Think About It

Think about this: How would you explain homomorphic encryption: computing on ciphertext to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.

Practice Exercises

Now it is time to practice! Complete these challenges to solidify your understanding:

• Exercise 1: Write a short program that demonstrates the core concept from this chapter. Test it with at least 3 different inputs.
• Exercise 2: Find a real-world example where homomorphic encryption: computing on ciphertext is used in an Indian company (like TCS, Infosys, Flipkart, or ISRO). Write a paragraph explaining the connection.
• Exercise 3: Create a mind-map connecting homomorphic encryption: computing on ciphertext to at least 3 other topics you have studied.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind homomorphic encryption: computing on ciphertext, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.