Homomorphic Encryption (HE): Compute on Encrypted Data

1) Core Idea and Flavors

Homomorphism means structure is preserved by a mapping. In HE, the mapping is encryption. If Enc is the encryption function and Dec is decryption, then for a supported operation ⊕ we have:

Dec( Eval( Enc(a) ⊕ Enc(b) ) )  =  a ⊕ b

• Partially homomorphic: classic Paillier is additively homomorphic (add on ciphertexts equals add on plaintexts). ElGamal in a suitable group is multiplicatively homomorphic.
• Somewhat or leveled HE: supports both addition and multiplication up to a bounded multiplicative depth (how many times you multiply). This is enough for many analytics and machine learning scoring functions.
• Fully homomorphic (FHE): supports arbitrary circuits by periodically bootstrapping, which refreshes a ciphertext to reduce accumulated noise so computation can continue.

Modern practical HE families derive security from lattice problems such as Ring-LWE: BFV and BGV for exact integer arithmetic, CKKS for approximate real arithmetic, and TFHE for fast boolean gates with programmable bootstrapping. All use large polynomial rings, noise terms, and carefully chosen parameters.

2) Toy Example (Concept)

A tiny conceptual flow using an additive homomorphism. The server never sees the inputs in the clear:

// Client
pk, sk    = HE.KeyGen()
c1        = HE.Enc(pk, 7)
c2        = HE.Enc(pk, 5)

// Server (stateless)
c3        = HE.Eval_Add(c1, c2)   // homomorphic addition

// Client
Dec(sk, c3)  == 12  // true; 7 and 5 were never exposed

Real systems add two practical details:

1. Noise budget: each operation increases ciphertext noise; once the budget is exhausted, decryption fails. Leveled schemes plan a circuit so that budget is enough without bootstrapping.
2. Packing: with BFV or CKKS you can pack many values into one ciphertext (SIMD style) to amortize cost  for example, sum 1,024 encrypted salaries in one pass.

3) Where HE Fits with Web3

Blockchains are transparent by design. HE gives a way to compute off-chain on encrypted inputs, then settle on-chain with minimal disclosures. Common patterns:

• Private analytics and dashboards: exchanges or protocols compute aggregate metrics (for example average trade size per region) on encrypted user data. They publish a commitment or a zero-knowledge proof on chain, not the raw metric inputs.
• Sealed-bid auctions and batch auctions: bidders encrypt bids; an operator computes the clearing price under HE. A zero-knowledge proof attests that the computed outcome is consistent with the encrypted bids and the auction rules.
• Credit or risk scoring for DeFi access: wallet attributes from KYC providers (income bucket, residency, sanctions screen) are encoded as encrypted bits or scalars; a scoring function runs under HE. On chain, only a threshold result is revealed, such as “score above 70” or “eligible.”
• Order matching engines: matching and price improvement can be computed on encrypted orders off chain while the settlement leg is finalized on chain. HE hides the book while ZK proves the matching was valid.
• Wallet security experiments: transform secrets under encryption, such as risk checks or rate limits, where the policy is evaluated over encrypted state so a service cannot steal keys even if compromised.

A recurring theme is hybrid HE and blockchain: keep the heavy computation and sensitive data off chain, then anchor the result on chain with a hash, a commitment, or a proof that the encrypted compute obeyed the rules.

4) HE and ZK: prove correctness

HE hides inputs. It does not, by itself, convince others that the operator computed the right function over those inputs. Three useful composition patterns:

1. Proof of correct decryption: the operator publishes a zero-knowledge proof that the plaintext they revealed really decrypts from a given ciphertext under a public key without exposing the secret key.
2. Proof of correct computation: generate a SNARK that verifies the HE evaluation circuit was applied correctly to committed ciphertexts and keys. The verifier does not learn the plaintexts, just that the output is consistent.
3. Attribute pre-screening: combine HE with verifiable credentials. A user first proves in zero knowledge that their attributes meet policy (for example over 18, residency allowed). Those attributes are then encoded and processed under HE to derive an encrypted score used for access control or pricing.

In practice, you will mix and match: HE protects data during compute, and a succinct proof convinces on-chain contracts that the outcome is valid so settlement can proceed.

5) Limits and Reality Check

• Performance and cost: FHE is still heavy for deep or branching logic. Leveled schemes shine for linear algebra, statistics, and shallow inference (for example a few multiplications). Expect milliseconds to seconds per operation off chain, not microseconds.
• Noise and depth planning: a computation graph must fit into the noise budget or call bootstrapping, which is orders of magnitude more expensive. CKKS gives approximate results well suited for analytics but not exact arithmetic.
• Security assumptions: most HE relies on lattice hardness and offers strong semantic security under chosen plaintext attack. If you need chosen ciphertext attack protections, combine with authenticated layers or proofs that the server followed the prescribed evaluation.
• Key management and trust boundaries: who holds the decryption key? For multi-party scenarios, use threshold decryption or combine with multi-party computation so no single party can decrypt alone.
• Alternatives: sometimes MPC or trusted execution environments are easier. MPC splits secrets across parties but adds round-trips; TEEs are fast but extend trust to hardware supply chains. HE is strongest when you want one untrusted operator to compute on many users’ encrypted data asynchronously.
• Developer ergonomics: modern SDKs are improving, but you still need to understand scaling factors, modulus switching, and encoding to avoid silent precision loss or overflow.

6) Implementation Notes for Builders

• Choose a scheme to match math: BFV or BGV for exact integer logic and counters; CKKS for averages, dot products, and model inference where a small floating-point error is acceptable; TFHE for boolean logic and comparisons.
• Encode wisely: scale real numbers to fixed-point before encrypting. With CKKS, track the scale explicitly and rescale after multiplications to maintain precision.
• Pack vectors: use batching to process hundreds of slots per ciphertext. Map your compute to vectorized primitives to reduce ciphertext count.
• Parameter selection: security level (for example 128 bits), polynomial degree, and modulus chain must be chosen together. Larger parameters mean more security and room for depth but slower operations.
• Rotation and relinearization keys: precompute and share evaluation keys that allow rotations and multiplication followed by dimension reduction. Manage their distribution like secrets.
• Auditable execution: log the exact function evaluated, parameters, and commitments to inputs so you can later produce a proof or reproduce computations.
• On-chain interface: avoid posting ciphertexts on chain; store a short commitment and a proof artifact hash. Contracts verify the proof and act on the claimed result.
• Side-channel hygiene: when integrating native libraries, prefer constant-time implementations where possible and isolate HE compute from untrusted co-tenants to reduce leakage risk.

7) Pilot Checklist

1. Define the exact function f(x) you need. Can it be approximated by additions and a small number of multiplications or comparisons?
2. Select a scheme and target depth; decide whether bootstrapping is allowed or out of scope for version one.
3. Model precision and error budgets. For CKKS, simulate worst-case precision loss and set thresholds accordingly.
4. Decide the trust model: single operator with threshold decryption, or multiple parties with MPC for decryption.
5. Plan proofs: do you need a proof of correct decryption, a proof of correct evaluation, or both?
6. Design your on-chain artifact: commitment of inputs and code version, result, and a proof hash; define how disputes are handled.
7. Run synthetic and adversarial tests: malformed ciphertexts, noise exhaustion, extreme inputs, and key rotation.
8. Write a privacy and security note for users: what is encrypted, who can decrypt, and under what conditions.

Quick check

1. What does “homomorphic” mean in this context, and why is it useful?
2. Give one Web3 use case where HE is a better fit than MPC, and one where MPC might be better.
3. Why combine HE with a zero-knowledge proof when settling on chain?

Go deeper

• Concepts: BFV and BGV exact arithmetic, CKKS approximate arithmetic, TFHE gate bootstrapping, packing and rotations, noise budgets, and bootstrapping trade-offs.
• Design lectures: sealed-bid auctions under HE, private analytics pipelines with threshold decryption, order matching with encrypted orders and on-chain proofs.
• Security lectures: proof of correct decryption, authenticated evaluation layers, key rotation and recovery, comparison with MPC and trusted execution environments.
• Builder labs: implement a simple encrypted average with CKKS, then add a zero-knowledge proof that the published result matches the committed inputs within a small tolerance.