Homomorphic encryption

A homomorphic encryption (HE) scheme allows computation on encrypted data: given $\mathsf{Enc}(m_1)$ and $\mathsf{Enc}(m_2)$, one can produce $\mathsf{Enc}(f(m_1,m_2))$ for some function class $f$, without decrypting. A fully homomorphic encryption (FHE) scheme supports arbitrary polynomial-time functions. The first FHE construction was given by Gentry — Gen09.

Syntax

A homomorphic encryption scheme is a tuple of efficient algorithms $\mathsf{HE}=(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec},\mathsf{Eval})$ with respect to message space $\mathcal{M}$ and a supported function class $\mathcal{F}$:

• $\mathsf{KeyGen}(1^{\lambda })\to (\mathsf{pk},\mathsf{sk}),$ outputs a public key and secret key,
• $\mathsf{Enc}(\mathsf{pk},m)\to c,$ encrypts a message $m\in \mathcal{M}$ under the public key,
• $\mathsf{Dec}(\mathsf{sk},c)\to m,$ decrypts a ciphertext under the secret key,
• $\mathsf{Eval}(\mathsf{pk},f,c_1,\dots ,c_k)\to c,$ homomorphically evaluates $f\in \mathcal{F}$ on ciphertexts, producing $c$ such that $\mathsf{Dec}(\mathsf{sk},c)=f(m_1,\dots ,m_k)$.

Properties

Correctness

For all $m_1,\dots ,m_k\in \mathcal{M}$ and all $f\in \mathcal{F}$, decryption of the evaluated ciphertext returns the correct output: $\mathrm{Pr}\left[\mathsf{Dec}(\mathsf{sk},\mathsf{Eval}(\mathsf{pk},f,\mathsf{Enc}(\mathsf{pk},m_1),\dots ,\mathsf{Enc}(\mathsf{pk},m_k)))=f(m_1,\dots ,m_k)\right]\ge 1-\mathrm{negl}(\lambda ).$

Security

A homomorphic encryption scheme is IND-CPA secure if the standard PKE semantic security game is satisfied: no efficient adversary can distinguish $\mathsf{Enc}(\mathsf{pk},m_0)$ from $\mathsf{Enc}(\mathsf{pk},m_1)$ for any $m_0,m_1$. (CCA security is incompatible with homomorphism.)

Variations

Partially homomorphic encryption (PHE)

Supports homomorphism over a restricted class: only additions (e.g., Paillier from DCR) or only multiplications (e.g., unpadded RSA), but not both.

Somewhat homomorphic encryption (SHE)

Supports both additions and multiplications, but only up to a bounded number (bounded by the multiplicative depth of the circuit).

Leveled fully homomorphic encryption

Supports all polynomial-size circuits of a-priori bounded depth (set at key generation time), without bootstrapping. First efficient construction from LWE — BGV12.

Fully homomorphic encryption (FHE)

Supports arbitrary polynomial-time computation via bootstrapping: a special homomorphic evaluation of the decryption circuit that refreshes the noise in a ciphertext. First construction based on ideal lattices — Gen09.

Compact FHE

An FHE scheme is compact if the ciphertext and the evaluation circuit’s output have bounded size, independent of the circuit being evaluated. Gentry’s original FHE is compact.

Other results

• First fully homomorphic encryption scheme from ideal lattices using bootstrapping — Gen09
• Leveled FHE without bootstrapping from LWE using modulus switching — BGV12
• FHE + DEPIR: doubly-efficient PIR and RAM computation from Ring-LWE — LMW23
• Additively homomorphic encryption from DCR — Pai99
• Multiplicatively homomorphic encryption from RSA — RSA78
• HE → rerandomizable encryption → SZK $\ne$ BPP — BL13
• Circular security: FHE schemes often need to encrypt their own secret key; the assumption that this is secure is called circular security and is not implied by standard assumptions