Overview

Homomorphic encryption

Encryption that lets anyone compute on ciphertexts, producing an encryption of a function of the underlying plaintexts without access to the secret key.

What it is

A homomorphic encryption (HE) scheme adds an evaluation algorithm to public-key encryption. Given an evaluation key, a function $f$ from a class $C$ , and encryptions of $m_{1}, \dots, m_{k}$ , it outputs a ciphertext that decrypts to $f (m_{1}, \dots, m_{k})$ , exactly or, for approximate schemes, within a stated error. Compactness requires the evaluated ciphertext to have size independent of the size of $f$ ; without it the problem is trivial. The basic security goal is IND-CPA. Ciphertexts are malleable by design, so HE cannot be IND-CCA2 secure; weaker chosen-ciphertext notions remain possible (). The question was posed as "privacy homomorphisms" () and first answered for all circuits by .

Core notions

Partially homomorphic (PHE): one operation, any number of times, e.g. addition in .
Somewhat homomorphic (SHE): additions and multiplications up to a bounded degree. Lattice ciphertexts carry noise that grows with each operation and must stay below a threshold for decryption to succeed.
Leveled HE: parameters are chosen for a depth bound $L$ fixed at key generation; every circuit of depth at most $L$ can be evaluated ().
Fully homomorphic (FHE) and bootstrapping: bootstrapping evaluates the decryption circuit homomorphically on an encryption of the secret key and returns a ciphertext with fresh noise, which allows unbounded depth. Because the encrypted secret key is public, security relies on a circular-security assumption.
Noise management: relinearization (key switching) shrinks a ciphertext after multiplication; modulus switching and scale-invariant encodings slow noise growth.
Exact versus approximate: BGV and BFV compute exactly modulo a plaintext modulus; CKKS computes on approximate real or complex numbers and treats noise and rounding as bounded precision loss; FHEW and TFHE encrypt bits or small integers and refresh after each gate.
Packing (SIMD): one ciphertext holds a vector of slots processed in parallel and rearranged by rotations ().
IND-CPA-D: IND-CPA where the adversary also sees decryptions of honestly evaluated ciphertexts. Decrypted CKKS results expose noise and allow key recovery (); exact schemes with noticeable decryption failure can fail it too ().
Circuit privacy: the evaluated ciphertext reveals nothing about $f$ beyond its output, even to the key holder; IND-CPA does not imply it. Noise flooding or repeated re-randomization and bootstrapping achieve it ().

Main approaches

First generation: ideal lattices () and integers (), with a squashed decryption circuit to make bootstrapping possible.
LWE and Ring-LWE with relinearization: SHE from standard LWE (), leveled FHE by modulus switching (), and scale-invariant schemes (, , the basis of BFV). Packing made workloads such as AES evaluation feasible ().
GSW and fast gate bootstrapping: approximate-eigenvector ciphertexts multiply without relinearization (). This structure underlies subsecond gate bootstrapping (), TFHE's external product (), and programmable bootstrapping that applies a lookup table while refreshing (, ).
Approximate arithmetic: CKKS with rescaling (), bootstrapping by approximate modular reduction (), word-size RNS arithmetic (), and higher-precision refresh ().

Notation used in the comparison table

Parameters below occur in efficiency or security bounds. Each meaning is scoped to its stated regime. Measured quantities are named in words; protocol objects are defined where used. Source aliases do not equate different regimes.

Symbol	Meaning	Regime	Paper aliases
λ	Computational security parameter.	HE security definitions.	writes κ; writes λ
n	LWE secret dimension.	Vector LWE.	writes n
d_R	Degree of the polynomial defining the plaintext/ciphertext ring.	Ring-based HE.	writes d
q	Ciphertext modulus at the specified level.	LWE and ring-based HE.	writes q; writes q
t	Plaintext modulus.	Exact modular HE.	writes t
B	Bound on noise magnitude in the stated norm.	LWE correctness and modulus-to-noise ratios.	No paper spelling asserted.
L	Circuit depth bound fixed at setup.	Leveled HE; multiplicative depth or other gate-depth model must be stated.	writes L; writes L
k	Number of evaluation hops.	Multi-hop HE.	No paper spelling asserted.
s	Circuit size per hop in the stated circuit model.	Multi-hop compactness.	No paper spelling asserted.
p	Prime order of the plaintext field.	Finite-field homomorphism and local PRGs.	No paper spelling asserted.
ε	Positive constant in the stated asymptotic regime.	Subexponential modulus-to-noise ratio.	No paper spelling asserted.
N	RSA modulus of Paillier-type encryption.	Paillier (decisional composite residuosity) encryption.	writes n

This topic follows the construction line from partial to fully homomorphic encryption and its security notions, with implementations, parameter sets, workloads, and benchmark runs kept as separate objects. PIR built on HE belongs to the PIR topic.

New to the area? Start here

Craig Gentry · STOC 2009
Zvika Brakerski, Vinod Vaikuntanathan · FOCS 2011
Zvika Brakerski, Craig Gentry, Vinod Vaikuntanathan · ITCS 2012
Craig Gentry, Amit Sahai, Brent Waters · CRYPTO 2013
Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, Malika Izabachène · ASIACRYPT 2016
Jung Hee Cheon, Andrey Kim, Miran Kim, Yongsoo Song · ASIACRYPT 2017