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

• Circular security + Somewhat homomorphic encryption (SHE) ⇒ HE
• LWE ⇒ Leveled fully homomorphic encryption
• LWE ⇒ DEPIR
• DCR ⇒ Partially homomorphic encryption (PHE)
• RSA ⇒ Partially homomorphic encryption (PHE)
• HE ⇒ RE
• No reduction from HE to SZK
• 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
• Single-hop FHE with IV-CCA security (strictly stronger than CCA1) in the standard model from circular-secure LWE — YYS25

Participates in

Builds on Homomorphic encryption

• DKG + HE ⇒ TPKE
• HE ⇒ MPC with preprocessing (SPDZ, etc.)
• HE ⇒ RE

Produces Homomorphic encryption

• Circular security + LWE ⇒ HE
• Circular security + Somewhat homomorphic encryption (SHE) ⇒ HE
• [[d-th-composite-residuosity-to-he|$d$-th Composite Residuosity ⇒ HE]]
• DCR ⇒ HE
• QR ⇒ HE
• Somewhat homomorphic encryption (SHE) ⇒ HE

Barriers

• No reduction from HE to CCA Security
• No reduction from HE to SZK