Computing on Encrypted Data

Throughline

Homomorphic encryption lets a server transform ciphertexts so that decryption reveals the result of a computation, without exposing the inputs.

1. The outsourcing goal

• Distinguish FHE from MPC:
  • MPC keeps parties online and interacting.
  • FHE lets a client upload once and leave the server to compute.
• Give the historical arc: proposed in 1978, first general construction by Gentry in 2009.
• State the honest constraint early: the possibility result is general; practical deployments are still workload-specific and expensive.

Reference: Rivest–Adleman–Dertouzos (1978); Gentry (2009)

2. Homomorphism before FHE

• Recall exponential ElGamal from Part 4:

$$\mathsf{Enc}(g^{m_1})\cdot\mathsf{Enc}(g^{m_2}) =\mathsf{Enc}(g^{m_1+m_2})$$

• Explain that addition and multiplication are enough to evaluate any arithmetic circuit.
• Define the ladder:
  • partially homomorphic: one operation
  • somewhat / leveled homomorphic: bounded circuit depth
  • fully homomorphic: unbounded depth through refresh or bootstrapping

3. Noise growth over the integers

• Use the toy DGHV-style ciphertext:

$$c=m+2r+kq$$

• Decrypt:

$$m=(c\bmod q)\bmod 2$$

• Work one addition and one multiplication.
• Track how noise grows slowly under addition and quickly under multiplication.
• Define the noise budget and show decryption failing once the centered remainder crosses the allowed bound.

Reference: van Dijk–Gentry–Halevi–Vaikuntanathan (2010)

4. LWE and practical schemes

• Introduce noisy linear equations:

$$b_i=\langle\mathbf a_i,\mathbf s\rangle+e_i\pmod q$$

• State the LWE problem: recover $\mathbf s$ or distinguish samples from uniform.
• Explain the worst-case lattice connection without overstating it; note the relevant approximation factors and reduction model in the finished prose.
• Sketch Regev encryption.
• Move to Ring-LWE and practical schemes:
  • BFV/BGV for exact modular arithmetic
  • CKKS for approximate real-number arithmetic
  • batching/SIMD when plaintext-ring conditions permit it
• Keep the quantum claim narrow:
  • Shor breaks factoring and discrete-log families.
  • No polynomial-time quantum attack is known for standard lattice assumptions.
  • Hash collision security is reduced rather than eliminated; the quantum random-oracle model remains meaningful.

Reference: Regev (2005); Fan–Vercauteren (2012)

5. Bootstrapping

• Start with a ciphertext near the end of its noise budget.
• Homomorphically evaluate the decryption circuit using encrypted key material.
• Output a fresh encryption of the same plaintext with a renewed budget.
• Explain circular-security assumptions where relevant.
• State the practical cost: bootstrapping is usually the dominant operation.
• Mention GSW as an alternative construction style, not simply as “better noise growth.”

Reference: Gentry (2009); Gentry–Sahai–Waters (2013)

6. Private information retrieval

• Goal: retrieve row $i$ without revealing $i$.
• Encrypt a one-hot selector vector and evaluate:

$$\mathsf{Enc}(\text{row}_i) =\sum_j \mathsf{Enc}(v_j)\cdot \text{row}_j$$

• Explain why the server must hide the access pattern as well as the query value.
• State the baseline cost: linear server work unless the scheme adds preprocessing or stronger structure.

Reference: Chor–Goldreich–Kushilevitz–Sudan (1995)

7. Closing the series

• Give honest performance bounds and name suitable workload shapes.
• Contrast three privacy tools:
  • FHE hides inputs during computation.
  • Differential privacy limits what outputs reveal about individuals.
  • Secure hardware trusts a hardware boundary instead of only mathematics.
• Close the six-part arc: definitions first, then constructions and composition.

Assumptions introduced

• LWE and Ring-LWE for the practical FHE families discussed here.
• Scheme-specific circular-security or bootstrapping assumptions where applicable.

Go deeper

• Gentry, Computing Arbitrary Functions of Encrypted Data
• Regev, On Lattices, Learning with Errors, Random Linear Codes, and Cryptography
• Dwork–Roth, The Algorithmic Foundations of Differential Privacy
• Scribed applied cryptography notes, §20–23