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 $f$ in some function class $\mathcal{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$. (IND-CCA2 security is incompatible with non-trivial homomorphism: $\mathcal{A}$ applies $\mathsf{Eval}$ to the challenge ciphertext and queries the decryption oracle on the result — folklore. IND-CCA1-secure FHE is known, e.g. from LWE in the ROM — CRRV17.)

Variations

Partially homomorphic encryption (PHE)

Supports homomorphism over a restricted class: only additions or only multiplications, but not both.

Additively homomorphic encryption

Supports only additions, e.g. Paillier from DCR — Pai99.

Multiplicatively homomorphic encryption

Supports only multiplications, e.g. ElGamal — ElGamal85, IND-CPA under DDH — TY98. Unpadded RSA is multiplicatively homomorphic but deterministic, hence not IND-CPA secure — standard.

Somewhat homomorphic encryption (SHE)

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

Bootstrappable SHE

An SHE scheme is bootstrappable if $\mathcal{F}$ contains its own decryption circuit augmented by one NAND gate, $\mathsf{sk}\mapsto \neg \left(\mathsf{Dec}(\mathsf{sk},c_1)\wedge \mathsf{Dec}(\mathsf{sk},c_2)\right)$ for all ciphertexts $c_1,c_2$ — Gen09.

Leveled fully homomorphic encryption

Supports all polynomial-size circuits of depth at most $L$, where $L$ is fixed at key generation. Leveled FHE from LWE — BV11; without bootstrapping — 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 there is a polynomial $p$ such that every ciphertext output by $\mathsf{Eval}$ has length at most $p(\lambda )$, independent of the evaluated function $f$ — BV11. Gentry’s original FHE is compact.

Strongly homomorphic encryption

An HE scheme is strongly homomorphic if $\mathsf{Eval}$ is distribution-preserving: for all $f\in \mathcal{F}$ and $m_1,\dots ,m_k\in \mathcal{M}$, the output of $\mathsf{Eval}(\mathsf{pk},f,c_1,\dots ,c_k)$ on fresh encryptions $c_i\leftarrow \mathsf{Enc}(\mathsf{pk},m_i)$ is statistically close to a fresh encryption $\mathsf{Enc}(\mathsf{pk},f(m_1,\dots ,m_k))$ — BL13.

Other results

• Circular security + Bootstrappable SHE ⇒ HE
• LWE ⇒ Leveled fully homomorphic encryption
• Ring-LWE ⇒ Unkeyed DEPIR
• DCR ⇒ Additively homomorphic encryption
• DDH ⇒ Multiplicatively homomorphic encryption
• Strongly homomorphic encryption ⇒ RE
• No reduction from NP to HE
• Circular security: bootstrapped FHE publishes an encryption of its own secret key — Gen09; security in this setting is circular security. IND-CPA security does not imply it in general — KW16, AP16 — and whether LWE implies it for the LWE-based FHE schemes is open.
• 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

• Additively homomorphic encryption ⇒ MPC with preprocessing (BDOZ) (via Additively homomorphic encryption)
• Circular security + Bootstrappable SHE ⇒ HE (via Bootstrappable SHE)
• SHE ⇒ MPC with preprocessing (SPDZ) (via Somewhat homomorphic encryption (SHE))
• Strongly homomorphic encryption ⇒ RE (via Strongly homomorphic encryption)
• MMap + Leveled FHE ⇒ iO (via Leveled fully homomorphic encryption)
• Additively homomorphic encryption + Sparse LPN ⇒ SHE (via Additively homomorphic encryption)
• Bootstrappable SHE ⇒ Leveled FHE (via Bootstrappable SHE)

Produces Homomorphic encryption

• Circular security + LWE ⇒ HE
• Circular security + Bootstrappable SHE ⇒ HE
• $d$-th Composite Residuosity ⇒ Additively homomorphic encryption (via Additively homomorphic encryption)
• DCR ⇒ Additively homomorphic encryption (via Additively homomorphic encryption)
• DDH + Sparse Learning Parity with Noise ⇒ Somewhat homomorphic encryption (SHE) (via Somewhat homomorphic encryption (SHE))
• DDH ⇒ Multiplicatively homomorphic encryption (via Multiplicatively homomorphic encryption)
• LWE ⇒ Leveled fully homomorphic encryption (via Leveled fully homomorphic encryption)
• Additively homomorphic encryption + Sparse LPN ⇒ SHE (via Somewhat homomorphic encryption (SHE))
• QR ⇒ Additively homomorphic encryption (via Additively homomorphic encryption)
• Bootstrappable SHE ⇒ Leveled FHE (via Leveled fully homomorphic encryption)

Barriers

• No fixed-construction reduction from HE to IND-CCA2 Security
• No reduction from NP to HE