Homomorphic encryption

A homomorphic encryption (HE) scheme for a class $\mathcal{F}$ of functions is an IND-CPA-secure public-key encryption scheme with a public evaluation algorithm that, given $f\in \mathcal{F}$ and encryptions of $m_1,\dots ,m_k$, outputs a ciphertext of length bounded independently of $f$ that decrypts to $f(m_1,\dots ,m_k)$, where $\mathcal{F}$ contains functions of every polynomial arity that depend on all their arguments. It is fully homomorphic (FHE) when $\mathcal{F}$ contains every polynomial-size circuit.

Syntax

A homomorphic encryption scheme with message space $\mathcal{M}$ and function class $\mathcal{F}$, each $f\in \mathcal{F}$ a circuit $f:{\mathcal{M}}^k\to \mathcal{M}$ for some arity $k$, is a tuple of efficient algorithms $\mathsf{HE}=(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec},\mathsf{Eval})$:

• $\mathsf{KeyGen}(1^{\lambda })\to (\mathsf{pk},\mathsf{sk})$, a randomized algorithm outputting a public key, which includes any evaluation key, and a secret key,
• $\mathsf{Enc}(\mathsf{pk},m)\to c$, a randomized algorithm encrypting a message $m\in \mathcal{M}$,
• $\mathsf{Dec}(\mathsf{sk},c)\to m$, a deterministic algorithm,
• $\mathsf{Eval}(\mathsf{pk},f,c_1,\dots ,c_k)\to c$, a possibly randomized algorithm that takes a circuit $f\in \mathcal{F}$ of arity $k$ and $k$ ciphertexts and outputs a ciphertext.

Properties

Correctness

$\mathsf{HE}$ is correct if $(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec})$ is a $(1-\mathrm{negl}(\lambda ))$-correct PKE scheme and for all $f\in \mathcal{F}$ of arity $k$ and all $m_1,\dots ,m_k\in \mathcal{M}$,

$$\mathrm{Pr}\left[\mathsf{Dec}(\mathsf{sk},\mathsf{Eval}(\mathsf{pk},f,c_1,\dots ,c_k))=f(m_1,\dots ,m_k)\right]\ge 1-\mathrm{negl}(\lambda ),$$

over $(\mathsf{pk},\mathsf{sk})\leftarrow \mathsf{KeyGen}(1^{\lambda })$, $c_i\leftarrow \mathsf{Enc}(\mathsf{pk},m_i)$ and the coins of $\mathsf{Eval}$. The definition concerns $\mathsf{Eval}$ on fresh ciphertexts only (single-hop correctness); it does not require $\mathsf{Eval}$ applied to evaluated ciphertexts to decrypt correctly.

Security

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{cpa}}_{\HE,\calA}(\secpar)$}
\begin{algorithmic}
\State $(\pk, \sk) \gets \KeyGen(1^\secpar)$; $b \getsr \bits$
\State $(m_0, m_1, \stA) \gets \calA(1^\secpar, \pk)$
\Comment{$m_0, m_1 \in \calM$, $|m_0| = |m_1|$}
\State $c^* \gets \Enc(\pk, m_b)$
\State $b' \gets \calA(c^*, \stA)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

An HE scheme $\mathsf{HE}$ is IND-CPA-secure if for all admissible efficient $\mathcal{A}$,

$${\mathbf{Adv}}_{\mathsf{HE},\mathcal{A}}^{\mathrm{cpa}}(\lambda ):=\left|2\mathrm{Pr}\left[{\mathbf{G}}_{\mathsf{HE},\mathcal{A}}^{\mathrm{cpa}}(\lambda )=1\right]-1\right|$$

is negligible. This is the CPA game of the underlying PKE scheme: $\mathsf{Eval}$ takes only public inputs, so $\mathcal{A}$ can run it itself. A homomorphic encryption scheme is required to be correct and IND-CPA-secure, and $\mathsf{Eval}$ to be compact for a class $\mathcal{F}$ that contains, for every polynomial $k$ and all large enough $\lambda$, a $k(\lambda )$-ary function whose value depends on all its arguments: there is a polynomial $p$ with $|\mathsf{Eval}(\mathsf{pk},f,c_1,\dots ,c_k)|\le p(\lambda )$ for every $f\in \mathcal{F}$. Without this, every IND-CPA-secure PKE is HE for the projections $(m_1,\dots ,m_k)\mapsto m_1$, with $\mathsf{Eval}(\mathsf{pk},f,c_1,\dots ,c_k):=c_1$ — standard. Compact fully homomorphic encryption below inherits these requirements, and leveled FHE meets them with its depth bound fixed to $L=\lambda$; additively and multiplicatively homomorphic encryption meet them for sums or products of $k$ messages, computed by iterating the binary $\mathsf{Eval}$, whose outputs stay in ${\mathcal{C}}_{\mathsf{pk}}$, of fixed length; semi-homomorphic and somewhat homomorphic encryption, circuit-private HE for ${\mathrm{NC}}^1$, approximate, strongly homomorphic and private-key homomorphic encryption are defined separately.

An HE scheme is not IND-CCA2-secure when a binary $f\in \mathcal{F}$ and inputs $x,w,z,m_0$ with $f(x,w)\ne x$, $f(m_0,z)\ne f(x,z)$, $|m_0|=|x|$ and $|z|=|w|$ can be computed from $\mathsf{pk}$ in polynomial time and the scheme decrypts correctly, except with negligible probability, on fresh and evaluated encryptions of inputs so computed (as under perfect correctness, or when $f$ and the inputs depend on $1^{\lambda }$ only), as for additively homomorphic encryption and for FHE: $\mathcal{A}$ applies $\mathsf{Eval}$ for $f$ to the challenge ciphertext and a fresh encryption of $z$ and, unless the result is the challenge ciphertext, queries the decryption oracle on it (No fixed-construction reduction from HE to IND-CCA2 Security) — folklore. Chosen-ciphertext notions for such schemes, FHE included (its class contains the XOR of two bits, with $x=z=0$ and $w=m_0=1$), therefore stop short of IND-CCA2; see IND-CCA1-secure FHE.

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\ge 2$ 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 a deterministic $\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.

Length-flexible additively homomorphic encryption

An additively homomorphic encryption scheme is length-flexible if one key pair serves every length $s\ge 1$, chosen at encryption time: $\mathsf{pk}$ fixes integers $M_1<M_2<\cdots$ with $\log M_s=\Theta (s\cdot k)$ for a key-length parameter $k$, and for every $s$ polynomial in $\lambda$ the scheme run at length $s$ is additively homomorphic as above, IND-CPA security included, with message space ${\mathbb{Z}}_{M_s}$ and ciphertexts in ${\mathbb{Z}}_{M_{s+1}}$. A ciphertext at length $s$ is thus a plaintext at length $s+1$. The Damgård–Jurik generalization of Paillier’s scheme, with $M_s=N^s$ for the RSA modulus $N$, has this form, with the block length adjustable after the public key is fixed, and is as secure as Paillier’s scheme — DJ01; nested encryption across lengths gives the PIR of Lip05 — Lip05.

Semi-homomorphic encryption

A semi-homomorphic encryption scheme modulo $p$, for an integer $p\ge 2$ given to key generation, is an IND-CPA-secure public-key scheme meeting the definition of BDOZ11, a relaxed notion of homomorphic encryption: encryption accepts every integer plaintext $x$ and is additively homomorphic, and decryption is required to return the correct result modulo $p$ only if $x$ is numerically small enough, within bounds the definition fixes — BDOZ11. Fresh encryptions of $x\in \{0,\dots ,p-1\}$ are required to decrypt to $x$ with probability $1-\mathrm{negl}(\lambda )$, as in PKE correctness. Unlike additively homomorphic encryption, it need not decrypt every sum. BDOZ11 give instances based on lattices, subset sum and factoring, and a zero-knowledge proof of plaintext knowledge for any semi-homomorphic scheme, which their MPC with preprocessing uses — BDOZ11.

Multiplicatively homomorphic encryption

An IND-CPA-secure scheme is multiplicatively homomorphic if its message space is a group $(\mathbb{G},\cdot )$ with $|\mathbb{G}|\ge 2$, 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 a deterministic $\mathsf{Eval}(\mathsf{pk},\times ,c_1,c_2)\in {\mathcal{C}}_{\mathsf{pk}}$ decrypts to $\mathsf{Dec}(\mathsf{sk},c_1)\cdot \mathsf{Dec}(\mathsf{sk},c_2)$ for all $c_1,c_2\in {\mathcal{C}}_{\mathsf{pk}}$; without the fixed ciphertext length the notion is met by any perfectly correct IND-CPA-secure PKE whose message space is a group, with $\mathsf{Eval}$ returning the pair of its inputs and $\mathsf{Dec}$ multiplying their decryptions — folklore. ElGamal is an example — ElGamal85, IND-CPA under DDH — TY98. Unpadded RSA has this homomorphism but is deterministic, hence not IND-CPA-secure and not multiplicatively homomorphic in this sense — standard.

Somewhat homomorphic encryption (SHE)

A somewhat homomorphic scheme supports additions and multiplications up to a bounded degree: $\mathsf{KeyGen}(1^{\lambda },1^T)$ takes a bound $T$, any polynomial in $\lambda$, and for some $d=d(\lambda )\ge 2$ the class ${\mathcal{F}}_T$ contains every sum of at most $T$ products of at most $d$ messages; for every such $T$ the scheme is correct and IND-CPA-secure; and it is compact: there is a polynomial $p$, independent of $T$, such that every ciphertext output by $\mathsf{Eval}$ on $f\in {\mathcal{F}}_T$ has length at most $p(\lambda )$. A scheme whose $\mathsf{KeyGen}$ takes no bound meets this by ignoring it. Without compactness the evaluator that returns $f$ with its input ciphertexts meets the definition (see Compact FHE). Gentry’s bootstrapping starts from a somewhat homomorphic scheme — Gen09.

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}}_T$ for a polynomial $T$ fixed by the scheme, 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. Its correctness must also hold for every key pair output by $\mathsf{KeyGen}$: for all ciphertexts $c_1,c_2$ output by $\mathsf{Enc}$ or $\mathsf{Eval}$ under $\mathsf{pk}$ and every encryption under $\mathsf{pk}$ of the bits of $\mathsf{sk}$, $\mathsf{Eval}$ on the augmented decryption circuit outputs a ciphertext that decrypts under $\mathsf{sk}$ to $\neg (\mathsf{Dec}(\mathsf{sk},c_1)\wedge \mathsf{Dec}(\mathsf{sk},c_2))$, as bootstrapping with one key evaluates on key-dependent inputs — Gen09. The security property is one of the scheme itself, implied by its circular security for bit encryption — standard; 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 $\mathsf{KeyGen}(1^{\lambda },1^L)$ takes the depth bound $L$, any polynomial in $\lambda$, and correctness and IND-CPA security hold for every such $L$, 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.

Brakerski’s tensoring technique makes the ciphertext noise grow linearly rather than quadratically with each multiplication, and gives a scale-invariant scheme: its properties depend only on the ratio of the modulus to the initial noise, one modulus serves the whole evaluation, and its security reduces classically to the worst-case hardness of GapSVP with a quasi-polynomial approximation factor — Bra12; FV12 port that scheme to Ring-LWE — FV12. In the approximate-eigenvector scheme there is no evaluation key, and homomorphic addition and multiplication are, for the most part, matrix addition and multiplication — GSW13.

Fully homomorphic encryption (FHE)

An FHE scheme evaluates every polynomial-size circuit compactly (Compact FHE). The lattice-based schemes do so by bootstrapping: a homomorphic evaluation of the decryption circuit that refreshes the noise in a ciphertext. First construction based on ideal lattices — Gen09.

Bootstrapping is the main bottleneck of known schemes; FHEW computes a bit operation and bootstraps its output in about half a second on a personal computer, under worst-case lattice assumptions together with a circular-security assumption — DM15. Replacing the internal product of GSW ciphertexts by an external product between a GSW and an LWE ciphertext brings the same bootstrapping below $0.1$ seconds and its key from 1 GB to 24 MB — CGGI16; the journal version, TFHE, reports 13 ms on one core with a 16 MB key — CGGI20. Asymptotically, for $2^{\lambda }$ security under conventional lattice assumptions, bootstrapping takes $\tilde{O}(\lambda )$ homomorphic operations on GSW ciphertexts, optimal up to polylogarithmic factors for schemes that encrypt one bit per ciphertext, with runtime and approximation factor both small polynomials — AP14.

Compact FHE

A compact FHE scheme is an HE scheme for the class of all polynomial-size circuits: there is a polynomial $p$ such that every ciphertext output by $\mathsf{Eval}$ has length at most $p(\lambda )$, independent of the evaluated circuit $f$ — BV11. FHE on this page means compact FHE; Gentry’s original scheme is one if its bootstrappable SHE scheme is circular secure — Gen09. 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.

Circular-secure FHE

A circular-secure FHE scheme is a compact FHE scheme that remains IND-CPA-secure when its public key is published together with polynomially many independent encryptions, under that key, of the bits of its own secret key, and that is perfectly correct: for every key pair output by $\mathsf{KeyGen}$, $\mathsf{Dec}(\mathsf{sk},\mathsf{Enc}(\mathsf{pk},m))=m$ for every message $m$, and $\mathsf{Dec}(\mathsf{sk},\mathsf{Eval}(\mathsf{pk},f,c_1,\dots ,c_k))=f(\mathsf{Dec}(\mathsf{sk},c_1),\dots ,\mathsf{Dec}(\mathsf{sk},c_k))$ for every polynomial-size circuit $f$ and all ciphertexts $c_1,\dots ,c_k$ obtained from encryptions under $\mathsf{pk}$ by repeated application of $\mathsf{Eval}$, with probability 1 over the coins of $\mathsf{Enc}$ and $\mathsf{Eval}$. Under this assumption $\mathbf{NP}$ has adaptively sound NIZK arguments in the common reference string model (Circular-secure FHE ⇒ NIZK argument for NP) — CCH+19.

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.

Approximate homomorphic encryption

An approximate homomorphic encryption scheme has the syntax of HE for the class of arithmetic circuits, built from additions and multiplications, of depth at most $L$, with messages vectors of complex numbers of ${\ell }_{\infty }$-norm at most $1$, except that $\mathsf{KeyGen}(1^{\lambda },1^L,1^p)$ also takes a precision $p$ and $\mathsf{Dec}$ may be randomized. It is correct if every ciphertext obtained from fresh encryptions $c_i\leftarrow \mathsf{Enc}(\mathsf{pk},m_i)$ by repeated application of $\mathsf{Eval}$ decrypts to within $2^{-p}$ of $f(m_1,\dots ,m_k)$ in ${\ell }_{\infty }$-norm except with negligible probability, whenever the composed computation $f$ has depth at most $L$ and every gate of $f$ evaluated on $(m_1,\dots ,m_k)$ has value of ${\ell }_{\infty }$-norm at most $1$; and it is compact: evaluated ciphertexts have length at most a polynomial in $\lambda$, $L$ and $p$, independent of the size of $f$. It is IND-CPA-secure as in Security, with $\mathsf{KeyGen}(1^{\lambda },1^L,1^p)$, for all polynomials $L$ and $p$.

The scheme of CKKS17 supports approximate addition and multiplication of encrypted messages together with a rescaling procedure, which truncates a ciphertext to a smaller modulus and rounds the plaintext; the bit length of the ciphertext modulus grows linearly with the depth of the evaluated circuit, and the precision lost is bounded by the depth, at most one bit more than in unencrypted floating-point arithmetic — CKKS17. Bootstrapping extends it from a leveled to a fully homomorphic scheme — CHKKS18.

Statically approximate HE

An approximate HE scheme is statically approximate if a public efficient algorithm $\mathsf{Estimate}$, fixed by the parameters $(\lambda ,L,p)$ and given only a circuit and error bounds for its inputs, bounds the worst-case output error compositionally: for every $(\mathsf{pk},\mathsf{sk})$ output by $\mathsf{KeyGen}(1^{\lambda },1^L,1^p)$, every circuit $f$ of arity $k$, and all ciphertexts $c_1,\dots ,c_k$, messages $m_1,\dots ,m_k\in \mathcal{M}$ and radii $e_1,\dots ,e_k$, if every output of $\mathsf{Dec}(\mathsf{sk},c_i)$ is within $e_i$ of $m_i$ in ${\ell }_{\infty }$-norm for each $i$, then every output of $\mathsf{Dec}(\mathsf{sk},\mathsf{Eval}(\mathsf{pk},f,c_1,\dots ,c_k))$, over all coins of $\mathsf{Eval}$ and $\mathsf{Dec}$, is within $B=\mathsf{Estimate}(f,e_1,\dots ,e_k)$ of $f(m_1,\dots ,m_k)$ in ${\ell }_{\infty }$-norm — LMSS22 (Definition 11). $\mathsf{Estimate}$ sees neither $\mathsf{pk}$ nor the ciphertexts, so $B$ is computed from the circuit and the radii alone. A public bound $t_e=t_e(\lambda ,L,p)$ covers every fresh encryption: for every $(\mathsf{pk},\mathsf{sk})$ output by $\mathsf{KeyGen}(1^{\lambda },1^L,1^p)$ and every $m\in \mathcal{M}$, every output of $\mathsf{Dec}(\mathsf{sk},\mathsf{Enc}(\mathsf{pk},m))$, over all coins of $\mathsf{Enc}$ and $\mathsf{Dec}$, is within $t_e$ of $m$ in ${\ell }_{\infty }$-norm — LMSS22 (Definition 15). The variant recorded here also has deterministic $\mathsf{Dec}$; requires $t_e(\lambda ,L,p)$ to be computable in time polynomial in $\lambda$, $L$ and $p$, and $\mathsf{Estimate}$ to run in time polynomial in $\lambda$, $L$, $p$ and the length of its input, with outputs of at most $s(\lambda ,L,p)$ bits for a polynomial $s$; and requires that $t_e$ and, for every circuit of depth at most $L$, the bounds obtained by running $\mathsf{Estimate}$ one gate at a time, on each addition or multiplication, with radius $t_e$ for each input of the circuit and the bound already computed for each other input, are at most $2^{-p}$. These requirements only narrow LMSS22’s hypothesis.

IND-CPA-D security

The adversary also sees decryptions of ciphertexts whose plaintexts it already knows: those it had encrypted, and evaluations on them of circuits it chose. Below, the oracles keep a list of triples $(m_j^0,m_j^1,c_j)$; $\mathcal{E}$ encrypts $m^b$ for a pair $(m^0,m^1)$, $\mathcal{H}$ evaluates a circuit $f$ on listed ciphertexts and records $f$ applied to both message tracks, answering only when the composed computation from $\mathcal{E}$‘s outputs to the new entry has depth at most $L$ and every gate of that computation has value of ${\ell }_{\infty }$-norm at most $1$ on both tracks, and $\mathcal{D}$ decrypts an entry only when its two tracks agree — LM21. Here $\mathcal{D}$ answers at most $q$ queries, a bound fixed in advance and given to $\mathsf{KeyGen}$; the notion without a bound implies this one, and a scheme whose $\mathsf{KeyGen}$ takes no $q$ meets this syntax by ignoring it.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{cpa\text{-}d}}_{\HE,\calA}(\secpar)$}
\begin{algorithmic}
\State $(\pk, \sk) \gets \KeyGen(1^\secpar, 1^L, 1^p, 1^q)$; $b \getsr \bits$; $j \gets 0$
\State $b' \gets \calA^{\calE, \calH, \calD}(1^\secpar, \pk)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\algname{Oracle}
\caption{$\calE(m^0, m^1)$}
\begin{algorithmic}
\State $j \gets j + 1$; $c_j \gets \Enc(\pk, m^b)$
\State $(m^0_j, m^1_j) \gets (m^0, m^1)$
\Return $c_j$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\algname{Oracle}
\caption{$\calH(f, j_1, \ldots, j_k)$}
\begin{algorithmic}
\State $j \gets j + 1$; $c_j \gets \Eval(\pk, f, c_{j_1}, \ldots, c_{j_k})$
\Comment{$\bot$ unless the computation stays in the supported depth and norm}
\State $m^\beta_j \gets f(m^\beta_{j_1}, \ldots, m^\beta_{j_k})$ for $\beta \in \bits$
\Return $c_j$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\algname{Oracle}
\caption{$\calD(i)$}
\begin{algorithmic}
\If{$m^0_i \ne m^1_i$ or $q$ queries were answered}
\Return $\bot$
\Comment{Only ciphertexts whose plaintext $\calA$ knows}
\EndIf
\Return $\Dec(\sk, c_i)$
\end{algorithmic}
\end{algorithm}

An approximate HE scheme $\mathsf{HE}$ whose $\mathsf{KeyGen}(1^{\lambda },1^L,1^p,1^q)$ also takes the query bound $q$, correct and compact as above for every polynomial $q$ with lengths polynomial in $\lambda$, $L$, $p$ and $q$, is IND-CPA${}^{\mathrm{D}}$-secure if for all polynomials $L,p,q$ and all efficient $\mathcal{A}$,

$${\mathbf{Adv}}_{\mathsf{HE},\mathcal{A}}^{\mathrm{cpa}\text{-}\mathrm{d}}(\lambda ):=\left|2\mathrm{Pr}\left[{\mathbf{G}}_{\mathsf{HE},\mathcal{A}}^{\mathrm{cpa}\text{-}\mathrm{d}}(\lambda )=1\right]-1\right|$$

is negligible. The restriction on $\mathcal{D}$ is necessary: decrypting an entry whose tracks differ reveals $b$.

For approximate schemes IND-CPA does not capture security against passive adversaries: a passive attack on CKKS, running in expected polynomial time, recovers the secret key with high probability, and was carried out against the HEAAN, SEAL, HElib and PALISADE implementations — LM21. Adding to the output of decryption noise scaled to a tag, $t_e$ on a fresh ciphertext and $\mathsf{Estimate}$‘s bound on the error of the evaluated circuit on an evaluated one, leaves every efficient adversary against an IND-CPA-secure statically approximate scheme negligible advantage in the IND-CPA${}^{\mathrm{D}}$ game, for a number of decryption queries fixed in advance — LMSS22; with the bound tracked one gate at a time and the original scheme run at a large enough precision $p^{\prime }>p$, the result is also correct at precision $p$ and compact, and its advantage stays negligible, since each circuit query is a sequence of admissible single-gate queries to LMSS22’s scheme, so it is IND-CPA${}^{\mathrm{D}}$-secure (IND-CPA statically approximate HE ⇒ IND-CPA${}^{\mathrm{D}}$ approximate HE) — folklore. For exact schemes the two notions coincide when decryption fails with negligible probability — LM21, as CCPSS24 point out; implementations of exact schemes that allow a noticeable probability of decryption failure fall to efficient IND-CPA${}^{\mathrm{D}}$ distinguishing and key-recovery attacks, among them the default BFV implementation of OpenFHE — CCPSS24; concurrent work reports practical key recovery against BFV, BGV and TFHE in their basic form — CSBB24.

Rate-1 and compressible FHE

The rate of a scheme is the ratio of plaintext length to ciphertext length. Combining an FHE scheme with linear decryption and a new high-rate linearly homomorphic encryption scheme gives, from LWE, an FHE scheme of rate $1-\sigma$ for $\sigma =o(1)$ — BDGM19. A linearly homomorphic encryption scheme based on (ring) LWE with rate $1-\epsilon$ for any $\epsilon >0$, into which many FHE ciphertexts, including ones produced by homomorphic evaluation, can be compressed, gives single-server PIR of rate $4/9$ whose server performs a small constant number of multiplications modulo $q$ per database byte, which the authors expect to cost less than encrypting the whole database under AES — GH19.

Multi-key FHE

In multi-key FHE each party generates its own key pair, possibly from common public parameters, and $\mathsf{Eval}$ takes ciphertexts encrypted under different, unrelated public keys and outputs a ciphertext that decrypts under the secret keys of all parties involved, jointly; each party’s encryptions are IND-CPA-secure under its own key. The notion is due to LTV12, who use it for multiparty computation on the cloud in which users interact only to upload their inputs and to decrypt the output. The LWE-based schemes of CM15 and MW16 are single-hop for keys: all relevant keys must be known at the start of the homomorphic computation; the schemes of PS16b are multi-hop for keys, so the output of a computation under one set of keys can be used in further computation — PS16b; BP16 give fully dynamic multi-key FHE with short ciphertexts from lattices — BP16. A one-round distributed decryption turns multi-key FHE into two-round MPC (LWE + NIZK ⇒ two-round MPC) — MW16.

Threshold FHE

In threshold FHE the secret key is shared among $N$ parties: each holder of a share computes a partial decryption of an evaluated ciphertext, and partial decryptions from an authorized set of parties combine to the plaintext while revealing nothing beyond it. A threshold FHE scheme gives a universal thresholdizer, a tool for turning other cryptographic schemes into threshold ones — BGG+18.

Circuit privacy

An HE scheme for $\mathcal{F}$ is circuit private if an evaluated ciphertext reveals nothing about the evaluated function beyond its output and its size: there is an efficient $\mathcal{S}$ such that for all $f\in \mathcal{F}$ and messages $m_1,\dots ,m_k$, the tuples $(\mathsf{pk},\mathsf{sk},c_1,\dots ,c_k,\mathsf{Eval}(\mathsf{pk},f,c_1,\dots ,c_k))$ and $(\mathsf{pk},\mathsf{sk},c_1,\dots ,c_k,\mathcal{S}(1^{\lambda },\mathsf{pk},c_1,\dots ,c_k,|f|,f(m_1,\dots ,m_k)))$ are computationally indistinguishable, for $(\mathsf{pk},\mathsf{sk})\leftarrow \mathsf{KeyGen}(1^{\lambda })$ and $c_i\leftarrow \mathsf{Enc}(\mathsf{pk},m_i)$. The distinguisher holds the secret key, as the party who decrypts does. The definition assumes honestly generated keys and ciphertexts; maliciously circuit-private FHE is meant to keep the evaluated function hidden even for malformed keys and ciphertexts, and is built from a scheme without circuit privacy by techniques akin to bootstrapping and conditional disclosure of secrets — OPP14.

Circuit-private HE for NC1

A circuit-private HE scheme for ${\mathrm{NC}}^1$ is leveled: $\mathsf{KeyGen}(1^{\lambda },1^L)$ takes a bound $L$, any polynomial in $\lambda$, and for every such $L$ the scheme is correct, IND-CPA-secure and circuit private as above for the class of fan-in-2 boolean circuits of depth at most $\log L$, with evaluated ciphertexts of length bounded by a polynomial in $\lambda$ and $\log L$, independent of the circuit. Every ${\mathrm{NC}}^1$ circuit family on inputs of length polynomial in $\lambda$ is covered by a large enough polynomial $L$. A variant of the GSW scheme that evaluates branching programs is circuit private as it stands, which gives circuit-private HE for ${\mathrm{NC}}^1$ circuits under LWE with polynomial modulus-to-noise ratio (LWE with polynomial ratio ⇒ Circuit-private HE for NC1) — BdPMW16. For general circuits, sanitization makes the distribution of a ciphertext canonical, independent of the circuit that produced it, by alternating bootstrapping with public rerandomization; it applies to all lattice-based FHE proposed by 2016 and, unlike flooding the noise, does not degrade the security–efficiency trade-off much — DS16.

Compact private-key homomorphic encryption

A compact private-key homomorphic encryption scheme for addition modulo $2$ is an IND-CPA-secure symmetric-key bit-encryption scheme with a public algorithm $\mathsf{Eval}$ that maps ciphertexts $c_1,\dots ,c_t$ of bits $m_1,\dots ,m_t$, without the key, to a ciphertext that decrypts to $m_1\oplus \cdots \oplus m_t$ and whose length is independent of the number $t$ of ciphertexts it was computed from — Rot11. Without compactness the notion follows from any CPA-secure symmetric-key scheme, by letting $\mathsf{Eval}$ return its input ciphertexts and decryption XOR their plaintexts — folklore. Nothing is required of the distribution of evaluated ciphertexts. Every compact scheme of this kind yields public-key encryption (Compact private-key XOR-homomorphic encryption ⇒ PKE) — Rot11.

IND-CCA1-secure FHE

An HE scheme is IND-CCA1-secure if its underlying PKE scheme is IND-CCA1-secure: $\mathcal{A}$ may query decryption before, but not after, it receives the challenge. Gentry’s basic scheme is not: a trivial lunchtime attack recovers its secret key, while a minor modification of the somewhat homomorphic scheme of Smart and Vercauteren is IND-CCA1-secure, indeed PA-1, in the standard model under a lattice-based knowledge assumption — LMSV11. A generic transformation turns multi-key identity-based FHE into IND-CCA1-secure FHE; instantiated in the random oracle model, “assuming sub-exponential LWE, there is a leveled CCA1 FHE scheme in the random oracle model which is compact wrt circuit complexity”, and a second instantiation uses sub-exponentially secure iO and sub-exponentially secure lossy encryption — CRRV17. A notion strictly stronger than CCA1 is also achievable: one-hop FHE with input-verifiable CCA (IV-CCA) security follows in the standard model from circular-secure LWE, the assumption on which known LWE-based FHE with chosen-plaintext security already rests, through the Naor–Yung paradigm with a succinct argument for the validity of FHE ciphertexts built from batch arguments for NP — YYS25.

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
• Bootstrapping publishes encryptions of the scheme’s own secret-key bits — Gen09 — and every known FHE scheme from LWE requires the encryption scheme to be circular secure — MV24. Unless the counterexamples’ assumptions fail, IND-CPA security does not give circular security by the identity map: for bit encryption under an extension of SXDH to multilinear groups (Rot13), and for key cycles under LWE with polynomial modulus-to-noise ratio (AP16) or iO (KRW15).
• DCR ⇒ Length-flexible additively homomorphic encryption (Damgård–Jurik)
• LWE with polynomial ratio ⇒ Circuit-private HE for NC1
• Compact private-key XOR-homomorphic encryption ⇒ PKE
• IND-CPA statically approximate HE ⇒ IND-CPA-D approximate HE (LMSS22)

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 ⇒ HE (via Additively homomorphic encryption)
• Bootstrappable SHE ⇒ SHE (via Bootstrappable SHE)
• Circuit-private HE for NC1 ⇒ IND-CPA PKE (via Circuit-private HE for NC1)
• Circular-secure bootstrappable SHE ⇒ Bootstrappable SHE (via Circular-secure bootstrappable SHE)
• Circular-secure FHE ⇒ Compact FHE (via Circular-secure FHE)
• Circular-secure FHE ⇒ NIZK argument for NP (via Circular-secure FHE)
• Circular-secure bootstrappable SHE ⇒ Compact FHE (via Circular-secure bootstrappable SHE)
• Compact FHE ⇒ HE (via Compact FHE)
• SHE + correlated randomness ⇒ MPC with preprocessing (SPDZ) (via Somewhat homomorphic encryption (SHE))
• HE ⇒ IND-CPA PKE
• Strongly homomorphic encryption ⇒ Statistically rerandomizable encryption (via Strongly homomorphic encryption)
• Length-flexible additively homomorphic encryption ⇒ Additively homomorphic encryption (via Length-flexible additively homomorphic encryption)
• Length-flexible additively homomorphic encryption ⇒ PIR with polylogarithmic communication (Lipmaa) (via Length-flexible additively homomorphic encryption)
• Leveled FHE ⇒ HE (via Leveled fully homomorphic encryption)
• MMap + Leveled FHE ⇒ iO (via Leveled fully homomorphic encryption)
• Multiplicatively homomorphic encryption ⇒ HE (via Multiplicatively homomorphic encryption)
• Additively homomorphic encryption + Sparse LPN ⇒ SHE (via Additively homomorphic encryption)
• Compact private-key XOR-homomorphic encryption ⇒ PKE (via Compact private-key homomorphic encryption)
• Semi-homomorphic encryption ⇒ MPC with preprocessing (BDOZ) (via Semi-homomorphic encryption)
• Bootstrappable SHE ⇒ Leveled FHE (via Bootstrappable SHE)
• SHE ⇒ IND-CPA PKE (via Somewhat homomorphic encryption (SHE))
• IND-CPA statically approximate HE ⇒ IND-CPA-D approximate HE (LMSS22) (via Statically approximate HE)
• Statically approximate HE ⇒ Approximate HE (via Statically approximate HE)
• Strongly homomorphic encryption ⇒ IND-CPA PKE (via Strongly homomorphic encryption)

Produces Homomorphic encryption

• Additively homomorphic encryption ⇒ HE
• Bootstrappable SHE ⇒ SHE (via Somewhat homomorphic encryption (SHE))
• Circular-secure bootstrappable SHE ⇒ Bootstrappable SHE (via Bootstrappable SHE)
• Circular-secure FHE ⇒ Compact FHE (via Compact FHE)
• Circular-secure bootstrappable SHE ⇒ Compact FHE (via Compact FHE)
• Compact FHE ⇒ HE
• $d$-th Composite Residuosity ⇒ Additively homomorphic encryption (via Additively homomorphic encryption)
• DCR ⇒ Length-flexible additively homomorphic encryption (Damgård–Jurik) (via Length-flexible 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)
• Length-flexible additively homomorphic encryption ⇒ Additively homomorphic encryption (via Additively homomorphic encryption)
• Leveled FHE ⇒ HE
• 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)
• Multiplicatively homomorphic encryption ⇒ HE
• Additively homomorphic encryption + Sparse LPN ⇒ SHE (via Somewhat homomorphic encryption (SHE))
• LWE with polynomial ratio ⇒ Circuit-private HE for NC1 (via Circuit-private HE for NC1)
• QR ⇒ Additively homomorphic encryption (via Additively homomorphic encryption)
• Bootstrappable SHE ⇒ Leveled FHE (via Leveled fully homomorphic encryption)
• IND-CPA statically approximate HE ⇒ IND-CPA-D approximate HE (LMSS22) (via IND-CPA-D security)
• Statically approximate HE ⇒ Approximate HE (via Approximate 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)