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

An IND-CPA-secure scheme is additively homomorphic if its message space is a group $({\mathbb{Z}}_M,+)$, with $M$ determined by $\mathsf{pk}$, its ciphertexts lie in a set ${\mathcal{C}}_{\mathsf{pk}}$ of strings of a fixed length $\ell (\lambda )$ that contains every encryption, decryption is perfectly correct, and $\mathsf{Eval}(\mathsf{pk},+,c_1,c_2)\in {\mathcal{C}}_{\mathsf{pk}}$ decrypts to $\mathsf{Dec}(\mathsf{sk},c_1)+\mathsf{Dec}(\mathsf{sk},c_2)$ for all $c_1,c_2\in {\mathcal{C}}_{\mathsf{pk}}$. The constructions of PIR — Ste98 — and of collision-resistant hashing — IKO05 — from such schemes use the fixed ciphertext length. Examples are Paillier’s scheme from DCR — Pai99 — and Goldwasser–Micali over ${\mathbb{Z}}_2$ — GM84.

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), and is compact: there is a polynomial $p$ such that every ciphertext output by $\mathsf{Eval}$ on $f\in \mathcal{F}$ has length at most $p(\lambda )$, independent of $f$ — Gen09. Without compactness the notion is trivial (see Compact FHE).

Bootstrappable SHE

An SHE scheme is bootstrappable if it compactly evaluates its own decryption circuit augmented by one NAND gate: for all ciphertexts $c_1,c_2$ output by $\mathsf{Enc}$ or $\mathsf{Eval}$, the circuit $\mathsf{sk}\mapsto \neg \left(\mathsf{Dec}(\mathsf{sk},c_1)\wedge \mathsf{Dec}(\mathsf{sk},c_2)\right)$ lies in $\mathcal{F}$, and $\mathsf{Eval}$ on it outputs a ciphertext of length at most the compactness bound $p(\lambda )$ — Gen09.

Circular-secure bootstrappable SHE

A bootstrappable SHE scheme is circular secure if it remains IND-CPA-secure when its public key is published together with encryptions, under that key, of the bits of its own secret key — Gen09. This is circular security of the scheme itself; circular security of some other scheme does not give it.

Leveled fully homomorphic encryption

Supports all polynomial-size circuits of depth at most $L$, where $L$ is fixed at key generation, and evaluated ciphertexts have length bounded by a polynomial in $\lambda$ and $L$, independent of the circuit’s size, a relaxation of the definition of BGV12 and Gen09, which require one decryption circuit for every $L$. Leveled FHE follows from LWE with sub-exponential modulus-to-noise ratio, together with polynomial-ratio LWE in a smaller dimension — BV11; without bootstrapping, at a ratio exponential in the depth — BGV12; and from LWE with polynomial modulus-to-noise ratio — BV14.

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, IND-CPA-secure and supporting every polynomial-size circuit, 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. Without compactness the notion is trivial: from any IND-CPA-secure PKE, let $\mathsf{Eval}$ return $f$ together with its input ciphertexts and let decryption decrypt the inputs and evaluate $f$ — standard.

Strongly homomorphic encryption

An IND-CPA-secure public-key bit-encryption scheme is strongly homomorphic for a boolean function $f:\{0,1{\}}^k\to \{0,1\}$ that is not constant, not a projection or its negation, and not an AND or OR of literals (so not NAND or NOR either), if its evaluator for $f$ is distribution-preserving: for all $m_1,\dots ,m_k\in \{0,1\}$, 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-secure bootstrappable SHE ⇒ Compact FHE
• LWE with sub-exponential ratio ⇒ Leveled FHE (BGV12)
• Ring-LWE ⇒ Unkeyed DEPIR
• DCR ⇒ Additively homomorphic encryption
• DDH ⇒ Multiplicatively homomorphic encryption
• Strongly homomorphic encryption ⇒ Statistically rerandomizable encryption
• No reduction from NP to compact FHE
• 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 ⇒ cPIR (via Additively homomorphic encryption)
• Additively homomorphic encryption ⇒ CRHF (via Additively homomorphic encryption)
• Additively homomorphic encryption ⇒ MPC with preprocessing (BDOZ) (via Additively homomorphic encryption)
• Circular-secure bootstrappable SHE ⇒ Bootstrappable SHE (via Circular-secure bootstrappable SHE)
• Circular-secure bootstrappable SHE ⇒ Compact FHE (via Circular-secure bootstrappable SHE)
• Compact FHE ⇒ HE (via Compact FHE)
• FHE ⇒ cPIR (via Compact FHE)
• SHE ⇒ MPC with preprocessing (SPDZ) (via Somewhat homomorphic encryption (SHE))
• Strongly homomorphic encryption ⇒ Statistically rerandomizable encryption (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-secure bootstrappable SHE ⇒ Bootstrappable SHE (via Bootstrappable SHE)
• Circular-secure bootstrappable SHE ⇒ Compact FHE (via Compact FHE)
• Compact FHE ⇒ 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 with sub-exponential ratio ⇒ Leveled FHE (BGV12) (via Leveled fully homomorphic encryption)
• LWE with polynomial ratio ⇒ Leveled FHE (BV14) (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)
• Sub-exponential iO + Rerandomizable encryption ⇒ Compact FHE (CLTV) (via Compact FHE)
• LWE at sub-exponential and polynomial ratios ⇒ Bootstrappable SHE (BV11) (via Bootstrappable SHE)

Barriers

• No fixed-construction reduction from HE to IND-CCA2 Security
• No reduction from NP to compact FHE (via Compact FHE)