Achievable CCA2 Relaxation for Homomorphic Encryption

Homomorphic encryption (HE) supports computing over encrypted data without access to the secret key. HE is a prominent approach to safeguarding data and minimizing the impact of potential breaches, especially useful for outsourcing of computations over sensitive data, as required by the industry cloud-based architecture.

The security notion achievable for HE schemes is security against chosen-plaintext attack (CPA-security), whereas it is well known that security against chosen-ciphertext attack (CCA2-security) is not achievable due to the inherent malleability of HE schemes. However, CPA-security is not always sufficient for securing protocols, as it considers only honestly generated ciphertexts and has no guarantees in settings where an adversary is allowed to inject its own maliciously crafted ciphertexts into an honest system (see, e.g., [46], Chapter 10). Therefore, relying on CPA-security typically secures protocols only against semi-honest adversaries, e.g., in [1, 6, 9, 13, 31, 35, 48] (unless further cryptographic tools are employed to enhance security).

In practice, however, security against malicious adversaries is desired to combat real-life attacks. A natural question therefore is the following:

Is there a relaxation of CCA2-security that is achievable for HE schemes and secures protocols against malicious attackers?

Our Contribution. In this work we answer affirmatively the above question by providing a new security notion, showing it is achievable for HE schemes and that it guarantees privacy against malicious adversaries for a wide and natural family of protocols.

The new security notion, named function-chosen-plaintext-attack (funcCPA-security), is a relaxation of CCA2 security for public-key encryption schemes. Concretely, while CCA2 security captures resiliency against adversaries that receive decryptions of ciphertexts of their choice, funcCPA guarantees resiliency only against adversaries that receive re-encryptions of the underlying cleartext values of ciphertexts of their choice (or, more generally, encryptions of the result of a computation on those values); see Definition 10. That is, in funcCPA the adversary sees only ciphertexts, no cleartext values; nonetheless, the adversary has full control on the computation performed on the underlying values, even without knowing them, and can inject maliciously crafted ciphertexts.

We show that funcCPA-security is achievable for HE schemes, where CCA2-security is not. Furthermore, funcCPA-security implies CPA-security, but not vice versa. To prove the latter, we provide: (1) a security proof showing, for a wide and natural family of outsourcing protocols (named, client-aided outsourcing protocols), that they preserve privacy when instantiated with any funcCPA-secure encryption scheme; and (2) an attack that breaks privacy in these protocols when instantiated with a (carefully crafted) CPA-secure encryption scheme.

To prove that funcCPA is achievable for HE schemes, we show how to construct funcCPA-secure HE schemes from any CPA-secure HE scheme equipped with a sanitization algorithm, including the HE schemes of Gentry [29], Brakerski-Vaikuntanathan [17] and Ducas and Micciancio [25], where sanitization re-randomizes ciphertexts to make them statistically close to other (sanitized) ciphertexts decrypting to the same plaintext as defined in [26] (see Definition 7).

Theorem 1

(funcCPA-secure HE scheme achievability, informal) Every CPA-secure HE scheme with a sanitization algorithm can be transformed into a funcCPA-secure HE scheme.^{Footnote 1}

To further motivate the definition of funcCPA-security, we note that many secure outsourcing protocols in the literature provide the server with the capability of seeing re-encryptions of ciphertexts of its choice, and even encrypted results of computations performed on the underlying values of such ciphertexts. For example, in [48] the client provides the server with re-encryptions for ciphertexts of the server’s choice, with the goal of avoiding costly bootstrapping at the server’s side.^{Footnote 2} Likewise, in [1, 6, 9, 13, 31, 35] the server obtains, via interaction with the client, the encrypted results of applying various computations on the underlying cleartext values of ciphertexts of its choice, including computing comparisons [13], minima [1, 6], linear equations solutions [9, 31], ReLU [35]. Moreover, in real-world systems it is common that computation results on data, are stored, and later retrieved and used for further computations; when computations are securely outsourced to an untrusted server using homomorphic encryption, this pipeline entails decrypting the results for storage and then re-encrypting them prior to sending to the server for the subsequent computation—this process is, in effect, a re-encryption oracle as modeled in our work.

To capture and generalize secure outsourcing protocols such as discussed above [1, 6, 9, 13, 31, 35], we define a natural family of protocols named: client-aided outsourcing protocols. This family consists of all protocols where a client generates keys and uploads encrypted data to a server; the server executes computations over the encrypted data and sends encrypted results to the client; moreover, the server may send the client (typically few and lightweight) queries of the form \(({\textbf{e}},G)\), for \({\textbf{e}}\) a vector of ciphertexts and G a function, so that the client computes G on the underlying cleartext values and sends the server the encrypted result \({\textbf{e}}' \leftarrow \textsf{Enc}_{pk}(G(\textsf{Dec}_{sk}({\textbf{e}})))\).

We prove that client-aided outsourcing protocols instantiated with funcCPA-secure schemes preserve privacy against malicious servers.

Theorem 2

(privacy against malicious servers, informal) Client-aided outsourcing protocols instantiated with any funcCPA-secure scheme preserve privacy against malicious servers.

Conversely, the attack we exhibit exemplifies that CPA-security does not provide privacy against malicious servers for this class of protocols.

Theorem 3

(attack, informal) There exist CPA-secure HE schemes so that for client-aided outsourcing protocols instantiated with these schemes, there is an attack by the server that recovers the client’s input.

Achievability by existing schemes of funcCPA-security. To avoid the performance overhead incurred due to using sanitization, we examine the achievability of funcCPA-security for popular HE schemes. We prove that the leveled HE schemes of BV [17], BGV [16] and B/FV [15, 27] are leveled-funcCPA-secure (based on their CPA-security). That is, they satisfy a natural adaptation of funcCPA to leveled settings, where the funcCPA oracle answers queries with ciphertexts for the next level.^{Footnote 3} Our security proof requires essentially no modifications to the schemes (other than a slight change in their evaluation keys generation that has little influence on performance) and without any extra security assumptions.

Theorem 4

(leveled HE are leveled-funcCPA-secure, informal) The leveled HE schemes of BV, BGV, B/FV are leveled-funcCPA-secure.

More generally, the above holds for every leveled HE scheme with keys generated independently for each level (as specified in Definition 13).

In contrast, for the homomorphic schemes of BV and BGV we show that funcCPA-security implies (weak) circular security. Concretely, we show that the funcCPA oracle enables generating from the public key an encryption of the secret key (in the encoding required for bootstrapping), and thus, funcCPA-security eliminates the need for the weak circular security assumption. This can be interpreted as a barrier on proving funcCPA-security for these schemes, as it would resolve the long-standing open problem on the necessity of circular security assumption (see, e.g., Question 11 in Peikert’s survey [43]).

Theorem 5

(funcCPA vs. circular security, informal) If the homomorphic encryption scheme of BV or BGV is funcCPA-secure, then it is weakly circular secure.

On the necessity of funcCPA against semi-honest adversaries. To further study the funcCPA-security notion, we examine its necessity against semi-honest adversaries. We prove that for client-aided outsourcing protocols satisfying a natural property, CPA-security suffices against semi-honest adversaries. The property we require is that the protocol is cleartext computable in the sense that the client’s input determines the underlying cleartext values of the ciphertexts transmitted throughout the protocol. This captures the fact that the encryption in the protocol is an external wrapping of the cleartext values, used merely for achieving privacy against the server, and does not affect the underlying cleartext computation. This property is natural in outsourcing protocols, where the server does not contribute any input to the computation but rather it is only a vessel for storing and processing encrypted data on behalf of the client.

Theorem 6

(privacy against semi-honest servers, informal) Cleartext-computable client-aided outsourcing protocols using a CPA-secure encryption scheme preserve privacy against semi-honest servers.

Our Techniques. Our definition of funcCPA (Definition 10) extends CPA by granting the adversary in the CPA experiment access to an \(\textsf{Enc}_{pk}({\mathcal {G}}(\textsf{Dec}_{sk}(\cdot )))\) oracle for a family of functions \({\mathcal {G}}\). Namely, the adversary can submit (possibly, adaptive) queries \(({\textbf{e}},G)\), for ciphertexts \({\textbf{e}}\) and a function \(G\in {\mathcal {G}}\) of its choice, and receive an encrypted result \({\textbf{e}}'\leftarrow \textsf{Enc}_{pk}(G(\textsf{Dec}_{sk}({\textbf{e}})))\).

To prove achievability of funcCPA for sanitized HE schemes (Theorem 1), we first define the notion of circuit-privacy\(^+\) that lies between the semi-honest and malicious definitions of circuit privacy in allowing maliciously formed ciphertexts but requiring honestly generated keys. We then show how to transform CPA-secure schemes with a sanitization algorithm into CPA-secure circuit-private\(^+\) schemes (Lemma 2). Finally, we prove that CPA-secure circuit-private\(^+\) schemes are funcCPA-secure.

For our attack proving the insufficiency of CPA-security (Theorem 3), we first show that every CPA-secure scheme can be slightly modified to yield a punctured CPA-secure scheme with which our attack is applicable. The attack uses a single query \({\textbf{e}}'\leftarrow \textsf{Enc}_{pk}(G(\textsf{Dec}_{sk}({\textbf{e}})))\), where \({\textbf{e}}\) is a concatenation of the client’s encrypted input with a special “trapdoor" ciphertexts planted in the public key. The query \({\textbf{e}}\) hits the puncturing of the scheme so that the result \({\textbf{e}}'\) reveals the client’s input. The encryption scheme remains CPA secure, despite the puncturing, because the trapdoor ciphertext is infeasible to generate honestly, i.e., by encrypting an efficiently samplable message.

Related Work. Several CCA relaxations were previously considered. Relaxing CCA2 by forbidding querying the decryption oracle on any ciphertext that decrypts to the same message as the challenge ciphertext (or extensions of this notion) was proposed in [18, 44, 47]. However, for HE this is unachievable (because the adversary can produce ciphertexts that decrypt to related messages, query the decryption oracle on those, and consequently recover the message in the challenge ciphertext). CCA1-secure HE schemes were constructed in [38] based on the short principal ideal problem, which has later been shown to be insecure [11], and in [19, 40] based on indistinguishability obfuscation (iO) or succinct non-interactive arguments of knowledge (SNARKs).

Insufficiency of CPA-security for protocols utilizing homomorphic encryption was considered by Li and Micciancio [37]. They show that protocols instantiated with the CPA-secure approximate HE schemes of CKKS [21] are insecure when the protocol exposes decryptions to the attacker, even for semi-honest adversaries. In contrast, our attack applies both to exact and approximate schemes and even when no decryptions are provided (albeit with a malicious adversary).

Prior versions of this work. Preliminary versions of this work appeared in [3, 4, 10]: The notion of funcCPA-security and its implication to privacy against malicious servers (Theorem 2) was introduced in [4], in the context of presenting new privacy preserving machine learning protocols. We remark that these protocols were published in [5, 7], albeit with security only against semi-honest servers. The study of funcCPA was extended in [10] by introducing the generic construction of funcCPA-secure encryption from sanitization (Theorem 1); proving the insufficiency of CPA-security for privacy against malicious servers (Theorem 3); and proving the sufficiency of CPA-security for privacy against semi-honest servers in cleartext computable client-aided outsourcing protocols (Theorem 6). Open problems presented in [10] were addressed in [3], where we proved that leveled HE schemes are (leveled) funcCPA-secure (Theorem 4), and introduced connections between funcCPA and circular security (Theorem 5). In addition, [3] introduced the observation that funcCPA w.r.t the identity function (i.e., with an oracle that can only refresh ciphertexts) implies funcCPA w.r.t an oracle that can compute all the circuits for which the scheme is homomorphic (Lemma 1).

Follow-up works. A follow-up work by Nuida [41] proposed a different definition of funcCPA (albeit, using the same name funcCPA). It was shown in [41] that their definition does not guarantee privacy in client-aided outsourcing protocols, and the thrust of that work was to study several possible treatments of invalid ciphertexts. We stress that the results from [41] have no bearing on our funcCPA definition, in particular we show in Theorem 2 that our definition does imply privacy for client-aided protocols. We note that our results hold regardless of how invalid ciphertexts are treated (as long as funcCPA holds w.r.t. an oracle that uses the same treatment as the client in the protocol). See Remark 3. We also note that [41, Theorems 3 and 5] are special cases of [10, Theorem 7]. Another follow-up work, by Dodis, Halevi and Wichs [24], showed that funcCPA-secure encryption can be constructed in a black-box manner from CPA-secure encryption. Moreover, they the show that funcCPA-security is implied by CCA1-security (see [24, Footnote 2]).

Paper organization. Preliminary definitions are given in Sect. 2. Our results on funcCPA definition, sufficiency and achievability are given in Sect. 3. Our result on the insufficiency of CPA against malicious adversaries in Sects. 4, and on its sufficiency against semi-honest ones for natural protocols is given in Sect. 5. We conclude in Sect. 6.

In this section we briefly specify standard terminology, notations and definitions used throughout this paper.

2.1 Terminology and Notations

We use the following standard notations and terminology. For \(n \in {\mathbb {N}}\), let [n] denote the set \( \{1,\ldots ,n\} \). A function \( \mu :{\mathbb {N}}\rightarrow {\mathbb {R}}^+ \) is negligible in n if for every positive polynomial \(p(\cdot )\) and all sufficiently large n it holds that \(\mu (n)<1/p(n)\). We use \( {\textsf{neg}}(\cdot ) \) to denote a negligible function if we do not need to specify its name. Unless otherwise indicated, “polynomial" and “negligible" are measured with respect to a system parameter \(\lambda \) called the security parameter. We use the shorthand notation \(\textsf {ppt}\) for probabilistic polynomial time in \(\lambda \). A probability ensemble \( X = \{X(a, n)\}_{a\in \{ 0,1 \}^*,n\in {\mathbb {N}}}\) is an infinite sequence of random variables indexed by \(a\in \{ 0,1 \}^*\) and \(n\in {\mathbb {N}}\). Let \( X = \{X(a, n)\}_{a\in \{ 0,1 \}^*,n\in {\mathbb {N}}}\) and \( Y = \{Y(a, n)\}_{a\in \{ 0,1 \}^*,n\in {\mathbb {N}}}\) be two probability ensembles. X and Y are said to be computationally indistinguishable, denoted by \(X\approx _c Y\), if for every non-uniform polynomial-time algorithm \({\mathcal {D}}\) there exists a negligible function \({\textsf{neg}}\) such that for every \(a\in \{ 0,1 \}^*\) and every \(n\in {\mathbb {N}}\),

A (strong) one-way function is a polynomial-time computable function \(f:\{ 0,1 \}^*\rightarrow \{ 0,1 \}^*\) so that any ppt algorithm can invert f with at most negligible probability; see a formal definition in Goldreich [32], Definition 2.2.1.

2.2 CPA-Secure Public-Key Encryption

We use the standard definition for public-key encryption (PKE) scheme \({\mathcal {E}}=(\textsf{Gen},\textsf{Enc},\textsf{Dec})\) and its properties of correctness, CPA-indistinguishability experiment against an adversary \({\mathcal {A}}\) denoted \(\textsf{EXP}^{cpa}_{{\mathcal {A}}, {\mathcal {E}}}(\lambda )\), and CPA-security for single and multiple messages. A scheme is fully decryptable if applying the decryption algorithm on any ciphertext in the ciphertext space returns an element from the message space (and requiring, in addition, that the ciphertext space is efficiently recognizable). Formal details follow.

2.2.1 Public-key encryption

A public-key encryption scheme has the following syntax and correctness requirement.

Definition 1

(Public-Key Encryption (PKE)) A public-key encryption (PKE) scheme with message space \({\mathcal {M}}\) is a triple \((\textsf{Gen},\textsf{Enc},\textsf{Dec})\) of ppt algorithms

satisfying the following conditions:

• \(\textsf{Gen}\) (key generation) takes as input the security parameter \(1^\lambda \) and outputs a pair (pk, sk) consisting of a public key pk and a secret key sk; denoted: \((pk,sk)\leftarrow \textsf{Gen}(1^\lambda )\).

• \(\textsf{Enc}\) (encryption) takes as input a public key pk and a message \(m\in {\mathcal {M}}\) and outputs a ciphertext c; denoted: \({\textbf{c}}\leftarrow \textsf{Enc}_{pk}(m)\).

• \(\textsf{Dec}\) (decryption) takes as input a secret key sk and a ciphertext c and outputs a decrypted message \(m'\); denoted: \(m'\leftarrow \textsf{Dec}_{sk}(c)\).

Correctness. The scheme is correct if for every (pk, sk) in the range of \(\textsf{Gen}(1^\lambda )\) and every message \(m\in {\mathcal {M}}\),

where the probability is taken over the random coins of the encryption algorithm.

2.2.2 Security against chosen-plaintext attack

A PKE \({\mathcal {E}}= (\textsf{Gen}, \textsf{Enc}, \textsf{Dec})\) is CPA-secure if no ppt adversary \({\mathcal {A}}\) can distinguish between the encryption of two equal length messages \(x_0,x_1\) of his choice. This is formally stated using the following experiment between a challenger \(\textsf {Chal}\) and the adversary \({\mathcal {A}}\).

The \( {\textsf {CPA}}\) indistinguishability experiment \(\textsf{EXP}^{cpa}_{{\mathcal {A}}, {\mathcal {E}}}(\lambda )\):

1. 1.

   \(\textsf{Gen}(1^\lambda )\) is run by \(\textsf {Chal}\) to obtain keys (pk, sk).

2. 2.

   \(\textsf {Chal}\) provides the adversary \({\mathcal {A}}\) with pk. \({\mathcal {A}}\) sends to \(\textsf {Chal}\) two messages \(x_0,x_1\in {\mathcal {M}}\) s.t. \(|x_0| = |x_1|\).

3. 3.

   \(\textsf {Chal}\) chooses a random bit \(b \in \{ 0,1 \}\), computes a ciphertext \(c \leftarrow \textsf{Enc}_{pk}(x_b)\) and sends c to \({\mathcal {A}}\). We call c the challenge ciphertext.

4. 4.

   \({\mathcal {A}}\) outputs a bit \(b'\).

5. 5.

   The output of the experiment is defined to be 1 if \(b' = b\) (0 otherwise).

Definition 2

(\({\textsf {CPA}}\)-security) A public-key encryption scheme \({\mathcal {E}}= (\textsf{Gen}, \textsf{Enc}, \textsf{Dec})\) has indistinguishable encryptions under chosen-plaintext attacks (or is \({\textsf {CPA}}\)-secure) if for all ppt adversaries \({\mathcal {A}}\) there exists a negligible function \({\textsf{neg}}\) such that:

where the probability is taken over the random coins of \({\mathcal {A}}\) and \(\textsf {Chal}\).

2.2.3 Security for multiple messages.

A PKE \({\mathcal {E}}= (\textsf{Gen}, \textsf{Enc}, \textsf{Dec})\) with message space \({\mathcal {M}}\) has indistinguishable multiple encryptions if no ppt adversary \({\mathcal {A}}\) can distinguish between the encryption of two vectors of equal length messages \(X_0 = (x_0^1,\ldots ,x_0^t)\) and \(X_1 = (x_1^1,\ldots ,x_1^t)\) of his choice. See formal definition in [36].

Theorem 7

(from [36], Thm. 10.10) If a public-key encryption scheme is CPA-secure, then it has indistinguishable multiple encryptions security.

Definition 3

(fully decryptable) A PKE scheme \({\mathcal {E}}=(\textsf{Gen},\textsf{Enc},\textsf{Dec})\) with message space \({\mathcal {M}}\) and ciphertext space \({\mathcal {T}}\) is fully decryptable if \({\mathcal {T}}\) is efficiently recognizable and for all \(\lambda \in {\mathbb {N}}\), \(c\in {\mathcal {T}}\), and any (pk, sk) in the range of \(\textsf{Gen}(1^\lambda )\) it holds that \(\textsf{Dec}_{sk}(c) \in {\mathcal {M}}\) (and \(\bot \) if \(c\notin {\mathcal {T}}\)).

2.3 Homomorphic Encryption

A homomorphic public-key encryption scheme (HE) is a public-key encryption scheme equipped with an additional ppt algorithm called \(\textsf{Eval}\) that supports “homomorphic evaluations" on ciphertexts. The correctness requirement is extended to hold with respect to any sequence of homomorphic evaluations performed on ciphertexts. A fully homomorphic encryption scheme must satisfy an additional property called compactness requiring that the size of the ciphertext does not grow with the complexity of the sequence of homomorphic operations.

Definition 4

(Homomorphic encryption (HE)) A homomorphic public-key encryption (HE) scheme \({\mathcal {E}}= (\textsf{Gen}, \textsf{Enc},\textsf{Dec}, \textsf{Eval})\) with message space \({\mathcal {M}}\) is a tuple of ppt algorithms as follows: \((\textsf{Gen}, \textsf{Enc},\textsf{Dec})\) is a correct PKE. \(\textsf{Eval}\) (homomorphic evaluation) takes as input the public key pk, a circuit \(C:{\mathcal {M}}^{\ell } \rightarrow {\mathcal {M}}\), and ciphertexts \(c_1,\dots , c_{\ell }\), and outputs a ciphertext \({\widehat{c}} \leftarrow \textsf{Eval}_{pk}(C,c_1, \dots , c_{\ell })\).

The scheme is secure if it is a \({\textsf {CPA}}\)-secure PKE; compact if its decryption circuit is of polynomial size (in the security parameter); \({\mathcal {C}}\)-homomorphic for a circuit family \({\mathcal {C}}\) if for all \(C\in {\mathcal {C}}\) and all inputs \(x_1, \dots , x_{\ell }\) to C, letting \((pk,sk)\leftarrow \textsf{Gen}(1^\lambda )\) and \(c_i \leftarrow \textsf{Enc}(pk, x_i)\) it holds that:

where the probability is taken over all the randomness in the experiment; and fully homomorphic if it is compact and \({\mathcal {C}}\)-homomorphic for \({\mathcal {C}}\) the class of all circuits.

A \({\mathcal {C}}\)-homomorphic encryption scheme is bootstrappable if it supports homomorphic evaluation of all circuits composed from copies of its decryption circuit connected by a single gate from the set of gates (see [28, Definitions 4.1.2\(-\)4.1.3]).

A HE scheme is leveled (leveled HE) if for each \(L\in {\mathbb {Z}}^+\) given as an extra parameter to \(\textsf{Gen}\), denoted \((pk,sk)\leftarrow \textsf{Gen}(1^\lambda ,1^L)\), the scheme compactly evaluates all circuits of depth at most L. The complexity of its algorithms is polynomial in L on top of \(\lambda \). CPAsecurity for leveled HE is defined similarly to the standard CPA definition except for the capability of the adversary to choose the level to which the challenge ciphertext is encrypted (to guarantee security of the scheme for all the levels). More formally,

Definition 5

(leveled HE[29]) A family of homomorphic encryption schemes \(\{{\mathcal {E}}^{(L)}:L \in {\mathbb {Z}}^+\}\) is leveled fully homomorphic (leveled HE) if, for all \(L\in {\mathbb {Z}}^+\), they all use the same decryption circuit, \({\mathcal {E}}^{(L)}\) compactly evaluates all circuits of depth at most L (that use some specified set of gates), and the computational complexity of \({\mathcal {E}}^{(L)}\)’s algorithms is polynomial in \(\lambda \), L, and (in the case of \(\textsf{Eval}\)) the size of the circuit C. In this case L can be given as an extra parameter to \(\textsf{Gen}\), denoted \((pk,sk)\leftarrow \textsf{Gen}(1^\lambda ,1^L)\).

Remark 1

In Definition 4 the syntax denotes by pk the key used both in \(\textsf{Enc}\) and \(\textsf{Eval}\). When it is desired to explicitly specify what information is needed by each of these two procedures, it is customary to slightly change this syntax so that key generation outputs three keys: \((pk,evk,sk)\leftarrow \textsf{Gen}(1^\lambda ,1^L)\), where \(\textsf{Enc}\) takes the public key pk and \(\textsf{Eval}\) takes the evaluation key evk (\(\textsf{Dec}\) takes the secret key sk).

The CPA indistinguishability experiment \(\textsf{EXP}^{cpa}_{{\mathcal {A}}, {\mathcal {E}}}(\lambda ,L)\) for leveled HE  is parameterized by the security parameter \(\lambda \) and number of levels L, and executed between a challenger \(\textsf {Chal}\) and an adversary \({\mathcal {A}}\) as follows:

1. 1.

   \(\textsf{Gen}(1^\lambda ,1^L)\) is run by \(\textsf {Chal}\) to obtain keys \((pk_\ell ,sk_\ell )_{\ell \in \{0,\ldots ,L\}}\) (we consider the public key \(pk_\ell \) to include the evaluation key \(evk_\ell \) if exists).

2. 2.

   \(\textsf {Chal}\) provides the adversary \({\mathcal {A}}\) with \((pk_\ell )_{\ell \in \{0,\ldots ,L\}}\). \({\mathcal {A}}\) sends to \(\textsf {Chal}\) two messages \(x_0,x_1\in {\mathcal {M}}\) s.t. \(|x_0| = |x_1|\) and \(\ell \in \{0,\ldots ,L\}\).

3. 3.

   \(\textsf {Chal}\) chooses a random bit \(b \in \{ 0,1 \}\), computes a ciphertext \(c \leftarrow \textsf{Enc}_{pk_{\ell }}(x_b)\) and sends c to \({\mathcal {A}}\). We call c the challenge ciphertext.

4. 4.

   \({\mathcal {A}}\) outputs a bit \(b'\).

5. 5.

   The output of the experiment is defined to be 1 if \(b' = b\) (0 otherwise).

Definition 6

(CPA security for leveled HE) A leveled HE scheme \({\mathcal {E}}=(\textsf{Gen},\textsf{Enc},\textsf{Dec},\textsf{Eval})\) is CPA-secure if for every ppt adversary \({\mathcal {A}}\) and L polynomial in the security parameter \(\lambda \), there exists a negligible function \({\textsf{neg}}\) such that:

where the probability is over all randomness in the experiment.

Sanitization. A ciphertext sanitization algorithm for a homomorphic encryption re-randomizes ciphertexts to make them statistically close to other (sanitized) ciphertexts decrypting to the same plaintext. Sanitization algorithms exist for most contemporary HE schemes [26].

Definition 7

(Sanitization algorithm [26]) A Sanitize algorithm for a homomorphic public-key encryption scheme \({\mathcal {E}}=(\textsf{Gen},\textsf{Enc},\textsf{Dec},\textsf{Eval})\) is a ppt algorithm that takes a public key pk and a ciphertext c and returns a ciphertext, so that with probability \(\ge 1 - {\textsf{neg}}(\lambda )\) over the choice of \((pk, sk) \leftarrow \textsf{Gen}(1^\lambda )\) the following holds:

• (Message-preservation) \(\forall c\) in the ciphertext space: \(\textsf{Dec}_{sk}(\textsf {Sanitize}_{pk}(c)) = \textsf{Dec}_{sk}(c). \)

• (Sanitization) \(\forall c, c'\) in the ciphertext space s.t. \(\textsf{Dec}_{sk}(c) = \textsf{Dec}_{sk}(c')\):

  $$\begin{aligned} \varDelta \left( \left( \textsf {Sanitize}_{pk}(c),(pk, sk)\right) , \left( \textsf {Sanitize}_{pk}(c'),(pk,sk) \right) \right) \le {\textsf{neg}}(\lambda ). \end{aligned}$$

2.4 Interactive Client–Server Protocols

The protocols considered in this work involve two-parties, client and server, denoted by \(\textsf{Clnt}\) and \(\textsf{Srv}\) respectively, where the client has input and output, the server has no input and no output, and both receive the security parameter \(\lambda \). The client and server interact in an interactive protocol denoted by \(\pi =\langle \textsf{Clnt},\textsf{Srv}\rangle \). The server’s view in an execution of \(\pi \), on client’s input x, no server’s input (denoted by \(\bot \)), and security parameter \(\lambda \), is a random variable \(\textsf {view}^\pi _{\textsf{Srv}}(x,\bot ,\lambda )\) capturing what the server has learned, and defined by \( \textsf {view}^\pi _{\textsf{Srv}}(x,\bot ,\lambda ) = (r, m_1,\dots ,m_t) \) where r is the random coins of \(\textsf{Srv}\), and \(m_1,\dots ,m_t\) are the messages \(\textsf{Srv}\) received during the protocol’s execution. The client’s output in the execution is denoted by \(\textsf {out}^\pi _{\textsf{Clnt}}(x,\bot ,\lambda )\). The protocol preserves privacy if the views of any server on (same length) inputs are computationally indistinguishable [33, Definition 2.6.2 Part 2]^{Footnote 4}:

Definition 8

(Correctness and privacy) An interactive client–server protocol \(\pi =\langle \textsf{Clnt},\textsf{Srv}\rangle \) for computing \(F:{\textsf{A}}\rightarrow {\textsf{B}}\), where the server has no input or output is said to be:

Correct::

if \(\textsf{Srv}\) and \(\textsf{Clnt}\) are ppt and for all \(x\in {\textsf{A}}\),\(\Pr [\textsf {out}^\pi _\textsf{Clnt}(x,\bot ,\lambda ) = F(x)] > 1-{\textsf{neg}}(\lambda ). \)

Private::

if for every ppt server \(\textsf{Srv}^*\) and every ppt distinguisher \({\mathcal {D}}\) that chooses \(x_0,x_1\in {\textsf{A}}\) s.t. \(|x_0|=|x_1|\), there exists a negligible function \({\textsf{neg}}(\cdot )\) such that for every \(\lambda \in {\mathbb {N}}\), it holds that:

$$\begin{aligned} \left| \Pr [{\mathcal {D}}(\textsf {view}^\pi _{\textsf{Srv}^*}(x_0,\bot ,\lambda )) = 1 ] - \Pr [{\mathcal {D}}(\textsf {view}^\pi _{\textsf{Srv}^*}(x_1,\bot ,\lambda )) = 1] \right| \le {\textsf{neg}}(\lambda ) \end{aligned}$$

where the probability is taken over the random coins of \(\textsf{Clnt}\) and \(\textsf{Srv}^*\).

Definition 8 captures malicious adversaries, but can be relaxed to semi-honest ones by quantifying only over the prescribed \(\textsf{Srv}\) rather than every ppt \(\textsf{Srv}^*\). We call the former privacy against malicious servers and the latter privacy against semi-honest servers.

Client-aided outsourcing protocols. We formally define the family of client-aided outsourcing protocols, or \(({\mathcal {E}},{\mathcal {G}})\)-aided outsourcing protocols, parameterized by a PKE scheme \({\mathcal {E}}\) with message space \({\mathcal {M}}\) and a family of functions \({\mathcal {G}}=\{G_n:{\mathcal {M}}\rightarrow {\mathcal {M}}\}_{n\in {\mathbb {N}}}\). We note that \({\mathcal {E}}\) can be any PKE scheme (i.e., not necessarily an HE scheme).

Definition 9

(\(({\mathcal {E}},{\mathcal {G}})\)-aided outsourcing protocol) Let \({\mathcal {E}}= (\textsf{Gen}, \) \(\textsf{Enc}, \textsf{Dec})\) be a public-key encryption scheme with message space \({\mathcal {M}}\), and \({\mathcal {G}}=\{G_n:{\mathcal {M}}\rightarrow {\mathcal {M}}\}_{n\in {\mathbb {N}}}\) a family of functions. An interactive client–server protocol \(\pi =\langle \textsf{Clnt},\textsf{Srv}\rangle \) for computing a function \(F:{\textsf{A}}\rightarrow {\textsf{B}}\) is called an \(({\mathcal {E}},{\mathcal {G}})\)-aided outsourcing protocol if it has the following three stage structure:

1. 1.

   Client’s input outsourcing phase (on input \(x\in {\textsf{A}}\)): \( \textsf{Clnt}\) runs \((pk,sk)\leftarrow \textsf{Gen}(1^\lambda )\), encrypts its input \({\textbf{c}}\leftarrow \textsf{Enc}_{pk}(x)\), and sends \({\textbf{c}}\) and pk to \(\textsf{Srv}\).

2. 2.

   Server’s computation phase: \( \textsf{Srv}\) performs some computation and in addition may interact (multiple times) with \(\textsf{Clnt}\) by sending it pairs \(({\textbf{e}},n)\), for \({\textbf{e}}\) a vector of ciphertexts and \(n\in {\mathbb {N}}\), receiving in response \(\textsf{Enc}_{pk}(G_n(\textsf{Dec}_{sk}({\textbf{e}})))\).

3. 3.

   Client’s output phase: \(\textsf{Srv}\) sends to \(\textsf{Clnt}\) the last message of the protocol; upon receiving this message, \(\textsf{Clnt}\) produces an output.

Remark 2

(multiple inputs and outputs) The query \({\textbf{e}}\) and response \({\textbf{e}}'\) can be vectors of ciphertexts, with decryption and encryption in \(\textsf{Enc}_{pk}(G_n(\textsf{Dec}_{sk}({\textbf{e}})))\) computed entry-by-entry. Throughout the paper we slightly abuse notations and denote by \({\mathcal {M}}\), \(\textsf{Dec}\), \(\textsf{Enc}\), \({\textbf{e}}\) and \({\textbf{e}}'\) also their extension to vectors.

In this section we first formally define funcCPA-security and prove that client-aided protocols instantiated with a funcCPA-secure scheme preserve privacy against malicious adversaries (see Sect. 3.1). We then show that funcCPA-secure HE is achievable from any HE equipped with a sanitization algorithm (see Sect. 3.2 ). Next we prove that funcCPA-security is satisfied by all leveled schemes satisfying a natural property of level keys’ independence, e.g., the leveled HE schemes of BV [17], BGV [16] and B/FV [15, 27] with a minor tweaking of their evaluation key (see Sect. 3.3); furthermore, funcCPA-security implies weak circular security for other natural schemes, e.g., the schemes of BV [17] and BGV [16] (see Sect. 3.4).

3.1 funcCPA-Security: A Sufficient Relaxation of CCA2

We define the function-chosen-plaintext attack (funcCPA-security) security notion of public-key encryption and show that \(({\mathcal {E}},{\mathcal {G}})\)-aided outsourcing protocols preserve privacy against malicious servers if \({\mathcal {E}}\) is funcCPA-secure. We remark that \({\mathcal {E}}\) may be a PKE that is not necessarily a HE.

The definition captures a weaker adversary than the standard CCA2 adversary in the sense that the adversary has access to a “decrypt-function-encrypt" oracle, specified with respect to a family of functions, where the adversary may submit a ciphertext together with a function identifier and receive in response a ciphertext that is produced as follows. The submitted ciphertext is first decrypted, then the requested function is calculated on the plaintext, and the result is encrypted and returned to the adversary.

More formally, we define funcCPA-security via a funcCPA-experiment specified for a public-key encryption scheme \({\mathcal {E}}= (\textsf{Gen}, \textsf{Enc}, \textsf{Dec})\) with message space \({\mathcal {M}}\), a family of functions \({\mathcal {G}}=\{G_n:{\mathcal {M}}\rightarrow {\mathcal {M}}\}_{n\in {\mathbb {N}}}\), and an adversary \({\mathcal {A}}\), as follows:

The funcCPA indistinguishability experiment \(\textsf{EXP}^{Fcpa}_{{\mathcal {A}}, {\mathcal {E}}, {\mathcal {G}}}(\lambda )\):

1. 1.

   \(\textsf{Gen}(1^\lambda )\) is run to obtain a key pair (pk, sk)

2. 2.

   The adversary \({\mathcal {A}}\) is given pk and access to a decrypt-function-encrypt oracle, denoted \(\textsf{Enc}_{pk}({\mathcal {G}}(\textsf{Dec}_{sk}(\cdot )))\), defined as follows: queries to \(\textsf{Enc}_{pk}({\mathcal {G}}(\textsf{Dec}_{sk}(\cdot )))\) are pairs consisting of a ciphertext \({\textbf{e}}\) and a function index n, and the response is \({\textbf{e}}'\leftarrow \textsf{Enc}_{pk}(G_n(\textsf{Dec}_{sk}({\textbf{e}})))\).^{Footnote 5}

3. 3.

   \({\mathcal {A}}\) outputs a pair of messages \(x_0, x_1\in {\mathcal {M}}\) with \( |x_0| = |x_1| \).

4. 4.

   A random bit \( b \in \{ 0,1 \}\) is chosen, and the ciphertext \(c\leftarrow \textsf{Enc}_{pk}(x_b)\) is computed and given to \({\mathcal {A}}\). We call c the challenge ciphertext. \({\mathcal {A}}\) continues to have access to the \(\textsf{Enc}_{pk}({\mathcal {G}}(\textsf{Dec}_{sk}(\cdot ))) \) oracle.

5. 5.

   The adversary \({\mathcal {A}}\) outputs a bit \(b'\). The experiment’s output is defined to be 1 if \(b'=b\), and 0 otherwise.

Definition 10

(\( \textsf {funcCPA}\)) A PKE scheme \({\mathcal {E}}= (\textsf{Gen}, \textsf{Enc}, \textsf{Dec})\) with message space \({\mathcal {M}}\) is funcCPA-secure w.r.t. a family of functions \({\mathcal {G}}=\{G_n:{\mathcal {M}}\rightarrow {\mathcal {M}}\}_{n\in {\mathbb {N}}}\) (funcCPA-secure w.r.t. \({\mathcal {G}}\)) if for all ppt adversaries \({\mathcal {A}}\), there exists a negligible function \({\textsf{neg}}(\cdot )\) such that:

where the probability is taken over the random coins used by \({\mathcal {A}}\), as well as the random coins used to generate (pk, sk), choose b, and encrypt.

Remark 3

(Handling decryption errors) In Definitions 9 and 10 we do not include an explicit discussion of how decryption errors are treated. This is because our theorem showing that funcCPA implies privacy (Theorem 8) holds with any treatment of errors, as long as errors are treated identically by both the client in the client-aided outsourcing protocol and the oracle in the funcCPA-experiment. An example of a possible treatment of errors follows: if decryption fails on a query \(({\textbf{e}},n)\) submitted to the client or oracle, they return \(\textsf{Enc}_{pk}(G_n(m))\) for an arbitrary message \(m\in {\mathcal {M}}\). Another example is provided in our preprint [4].

Theorem 8

(funcCPA implies privacy) Let \({\mathcal {E}}\) be a PKE with message space \({\mathcal {M}}\) and \({\mathcal {G}}=\{G_n:{\mathcal {M}}\rightarrow {\mathcal {M}}\}_{n\in {\mathbb {N}}}\) a family of functions.

If \({\mathcal {E}}\) is \(\textsf {funcCPA}\)-secure w.r.t. \({\mathcal {G}}\), then every \(({\mathcal {E}},{\mathcal {G}})\)-aided outsourcing protocol preserves privacy against malicious servers.

Proof

Let \(\pi \) be a \(({\mathcal {E}},{\mathcal {G}})\)-aided outsourcing protocol for a function \(F:{\textsf{A}}\rightarrow {\textsf{B}}\). Assume by contradiction that privacy does not hold for \(\pi \). That is, there exists a ppt distinguisher \({\mathcal {D}}\) that chooses \( x_0,x_1\in {\textsf{A}}\) with \(|x_0|=|x_1|\), a malicious ppt server \(\mathsf {Srv^*}\), and a polynomial \(p(\cdot )\) such that for infinitely many \(\lambda \in {\mathbb {N}}\):

We show that given \({\mathcal {D}}\) and \(\mathsf {Srv^*}\) we can construct an adversary \({\mathcal {A}}\) that violates the \(\textsf {funcCPA}\) security of \({\mathcal {E}}\) with respect to the family \({\mathcal {G}}\).

The adversary \({\mathcal {A}}\) participates in \(\textsf{EXP}^{Fcpa}_{{\mathcal {A}},{\mathcal {E}},{\mathcal {G}}}\) as follows:

1. 1.

   Upon receiving pk, \({\mathcal {A}}\) outputs \(x_0,x_1\) (as computed by \({\mathcal {D}}\)).

2. 2.

   Upon receiving \({\textbf{c}}_x\leftarrow \textsf{Enc}_{pk}(x_b)\) from the challenger, \({\mathcal {A}}\) internally executes \(\mathsf {Srv^*}\) and behaves as the \(\textsf{Clnt}\) in the execution of the protocol \(\pi \): in the client’s input outsourcing phase of \(\pi \), \({\mathcal {A}}\) sends \(({\textbf{c}}_x, pk)\) to \(\mathsf {Srv^*}\); in the server’s computation phase of \(\pi \), every incoming message \(({\textbf{e}},n)\) to \(\textsf{Clnt}\) is redirected to the oracle \(\textsf{Enc}_{pk}({\mathcal {G}}(\textsf{Dec}_{sk}(\cdot )))\) and the response is sent to \(\mathsf {Srv^*}\) as if it were coming from \(\textsf{Clnt}\).

3. 3.

   \({\mathcal {A}}\) runs the distinguisher \({\mathcal {D}}\) on \(\textsf {view}_{\mathsf {Srv^*}}\) (\(\mathsf {Srv^*}\)’s view in \({\mathcal {A}}\) during Step 2) and outputs whatever \({\mathcal {D}}\) outputs.

The adversary \({\mathcal {A}}\) is \(\textsf {ppt}\) due to \(\mathsf {Srv^*}\) and \({\mathcal {D}}\) being ppt. Note that \(\pi \) is perfectly simulated.

We denote by \(\textsf {view}^{\textsf{EXP}^{Fcpa}}_{\mathsf {Srv^*}}(x_{b},\bot ,\lambda )\) the view of \(\mathsf {Srv^*}\), simulated by \({\mathcal {A}}\), in the execution of \(\textsf{EXP}^{Fcpa}_{{\mathcal {A}},{\mathcal {E}},{\mathcal {G}}} \) with bit b being selected by the challenger. Since \({\mathcal {A}}\) behaves exactly as \(\mathsf {Srv^*}\) in \(\pi \), it holds that for every \(b\in \{ 0,1 \}\),

From Eqs. 1 and 2 it follows that:

Therefore, we obtain that:

where the last inequality follows from Eq. 3. Combining this with \({\mathcal {A}}\) being \(\textsf {ppt}\), we derive a contradiction to \({\mathcal {E}}\) being \( \textsf {funcCPA}\) secure. This concludes the proof. \(\square \)

We observe that for fully decryptable \({\mathcal {C}}\)-homomorphic schemes, it suffices to prove \(\textsf {funcCPA}\)-security w.r.t the identity function \({\mathcal {I}}\) to obtain \(\textsf {funcCPA}\)-security w.r.t \({\mathcal {C}}\). We note that full decryption holds for well-known schemes including [15, 16, 22, 25, 30, 45].

Lemma 1

Let \({\mathcal {E}}=(\textsf{Gen},\textsf{Enc},\textsf{Dec},\textsf{Eval})\) be a fully decryptable^{Footnote 6}\({\mathcal {C}}\)-homomorphic PKE scheme. If \({\mathcal {E}}\) is funcCPA-secure w.r.t the identity function \({\mathcal {I}}\) then it is funcCPA-secure w.r.t \({\mathcal {C}}\).

Proof

Let \({\mathcal {E}}= (\textsf{Gen}, \textsf{Enc}, \textsf{Dec},\textsf{Eval})\) be a fully decryptable \({\mathcal {C}}\)-homomorphic encryption scheme with message space \({\mathcal {M}}\) and ciphertext \({\mathcal {T}}\) that is funcCPA-secure w.r.t the identity function \({\mathcal {I}}:{\mathcal {M}}\rightarrow {\mathcal {M}}\). For any ppt adversary \({\mathcal {A}}\) that participates in \(\textsf{EXP}^{Fcpa}_{{\mathcal {A}},{\mathcal {E}}, {\mathcal {C}}} \) we construct an adversary \({\mathcal {B}}\) for \( \textsf{EXP}^{Fcpa}_{{\mathcal {B}},{\mathcal {E}},{\mathcal {I}}} \) that behaves as follows: The adversary \({\mathcal {B}}\) runs \({\mathcal {A}}\) internally while relaying messages between the challenger and \({\mathcal {A}}\), with the exception that \(\textsf{Enc}_{pk}({\mathcal {C}}(\textsf{Dec}_{sk}(\cdot )))\) queries are treated as follows: first the queried ciphertext is forwarded to the challenger that returns a fresh ciphertext of the encrypted value, then \(\textsf{Eval}\) is executed over this fresh ciphertext and the result ciphertext is forwarded again to the challenger that returns a fresh ciphertext for its underlying value. That is, \({\mathcal {B}}\) does the following:

• Upon receiving pk from challenger, forward it to \({\mathcal {A}}\).

• Answer queries \(({\textbf{e}},n)\) to \(\textsf{Enc}_{pk}({\mathcal {C}}(\textsf{Dec}_{sk}(\cdot )))\) by sending \(({\textbf{e}},{\mathcal {I}})\) to the challenger and obtaining a fresh ciphertext \({\textbf{e}}'\) (and \(\bot \) if \({\textbf{e}}\notin {\mathcal {T}}\)), computing \({\textbf{e}}''\leftarrow \textsf{Eval}_{pk}\left( C_n, {\textbf{e}}'\right) \) and sending \(({\textbf{e}}'',{\mathcal {I}})\) to the challenger. The response to the second query is given to \({\mathcal {A}}\).

• Once \({\mathcal {A}}\) generates \(x_0,x_1\) forward them to the challenger and return the response \(c\leftarrow \textsf{Enc}_{pk}(x_b)\) to \({\mathcal {A}}\).

• Output the \(b'\) that \({\mathcal {A}}\) outputs.

The adversary \({\mathcal {B}}\) is ppt (due to \({\mathcal {A}}\) and \(\textsf{Eval}\) being ppt), and all the interaction of \({\mathcal {A}}\) is perfectly simulated by \({\mathcal {B}}\) due to \({\mathcal {E}}\) being fully decryptable together with \({\mathcal {C}}\)-homomorphic. More formally, letting \((pk,sk)\leftarrow \textsf{Gen}(1^\lambda )\), for all \(C\in {\mathcal {C}}\) and \(c_1,\ldots c_\ell \in {\mathcal {T}}\) it holds that:

(if \({\mathcal {A}}\) submits a ciphertext not in \({\mathcal {T}}\) then the challenger’s response is \(\bot \) in both executions). Since the number of queries of \({\mathcal {A}}\) is polynomial in \(\lambda \), the indistinguishability of \(\textsf{EXP}^{Fcpa}_{{\mathcal {A}},{\mathcal {E}}, {\mathcal {C}}}(\lambda )\) and \(\textsf{EXP}^{Fcpa}_{{\mathcal {B}},{\mathcal {E}}, {\mathcal {I}}}(\lambda )\) follows.

Finally, from the \(\textsf {funcCPA}\)-security of \({\mathcal {E}}\) w.r.t \({\mathcal {I}}\) we conclude that

as required. \(\square \)

3.2 Sanitized HE Schemes are funcCPA-Secure

We show how to transform any HE scheme \({\mathcal {E}}\) that has a sanitization algorithm into a sanitized HE scheme, denoted \({\mathcal {E}}^\textsf {santz}\), so that if \({\mathcal {E}}\) is CPA-secure, then \({\mathcal {E}}^\textsf {santz}\) is funcCPA-secure.

Definition 11

(Sanitized scheme \({\mathcal {E}}^{\textsf {santz}}\)) Let \({\mathcal {E}}=(\textsf{Gen},\textsf{Enc},\textsf{Dec},\textsf{Eval})\) be HE scheme with message space \({\mathcal {M}}\) and a sanitization algorithm Sanitize. We define its sanitized scheme \({\mathcal {E}}^{\textsf {santz}} = (\textsf{Gen}, \textsf{Enc}^\textsf {santz}, \textsf{Dec}, \textsf{Eval}^\textsf {santz})\) as follows: \(\textsf{Gen}\) and \(\textsf{Dec}\) are as in \({\mathcal {E}}\); \(\textsf{Enc}^\textsf {santz}\) takes a public key pk and a message \(m\in {\mathcal {M}}\) and outputs:

\(\textsf{Eval}^\textsf {santz}\) takes pk, a circuit C, and ciphertexts \(c_1,\ldots ,c_\ell \) and outputs:

We note that \({\mathcal {E}}^{\textsf {santz}}\) inherits the compactness, security and correctness properties of \({\mathcal {E}}\) (in particular, correctness holds due to correctness of \({\mathcal {E}}\) and the message-preservation property of Sanitize). The homomorphism of \({\mathcal {E}}^\textsf {santz}\) may, in general, hold with respect to a subset of the circuits for which \({\mathcal {E}}\) is homomorphic. Nonetheless, when employing the sanitization algorithm of Ducas and Stehlé [26] both \({\mathcal {E}}\) and \({\mathcal {E}}^\textsf {santz}\) are fully homomorphic.

Theorem 9

(\({\mathcal {E}}^\textsf {santz}\) is funcCPA-secure) Let \({\mathcal {E}}\) be a fully decryptable CPA-secure HE scheme with a sanitization algorithm; \({\mathcal {E}}^\textsf {santz}\) its sanitized scheme. If \({\mathcal {E}}^\textsf {santz}\) is \({\mathcal {C}}\)-homomorphic, then it is funcCPA-secure w.r.t. \({\mathcal {C}}\).^{Footnote 7}\(^{,}\)^{Footnote 8}

Proof

To prove the theorem, we first enhance the definition of circuit privacy to circuit-privacy\(^+\) (cf. Definition 12 below); then show that the sanitized scheme \({\mathcal {E}}^\textsf {santz}\) satisfies circuit-privacy\(^+\) for \({\mathcal {C}}\) (cf. Lemma 2 below); and show that if a \({\mathcal {C}}\)-homomorphic CPA-secure encryption scheme satisfies circuit-privacy\(^+\) for \({\mathcal {C}}\), then it is funcCPA-secure w.r.t. \({\mathcal {C}}\) (cf. Lemma 3 below). We conclude that \({\mathcal {E}}^\textsf {santz}\) is funcCPA-secure w.r.t. \({\mathcal {C}}\). \(\square \)

Circuit privacy\(^+\). Our definition of circuit-privacy\(^+\) addresses maliciously generated ciphertexts by quantifying over all ciphertexts in the ciphertext space, rather than only over ciphertexts that were properly formed by applying the encryption algorithm on a message. Prior definitions of circuit privacy either considered the semi-honest settings where both the keys and the ciphertext are properly formed [14, 29, 34], or considered settings where both keys and ciphertexts may be maliciously formed [23, 34, 39, 42]. In contrast, in our settings the keys are properly formed whereas the ciphertexts may be maliciously formed.

Definition 12

(Circuit privacy\(^+\)) A \({\mathcal {C}}\)-homomorphic PKE scheme \({\mathcal {E}}=(\textsf{Gen}, \textsf{Enc}, \textsf{Dec}, \textsf{Eval})\) is circuit-private\(^+\) for \({\mathcal {C}}\) if the following holds with probability \(\ge 1 - {\textsf{neg}}(\lambda )\) over the choice of \((pk, sk) \leftarrow \textsf{Gen}(1^\lambda )\): For every circuit \(C\in {\mathcal {C}}\) over \(\ell \) inputs and ciphertexts \(c_1,\dots ,c_\ell \) in the ciphertext space of \({\mathcal {E}}\) the following distributions are statistically close:

where the distributions are over the random coins of \( \textsf{Enc}\) and \( \textsf{Eval}\).

We prove that the sanitized scheme \({\mathcal {E}}^\textsf {santz}\) is circuit-private\(^+\).

Lemma 2

(\({\mathcal {E}}^\textsf {santz}\) is circuit-private\(^+\)) Let \({\mathcal {E}}\) be a fully decryptable HE scheme with a sanitization algorithm, and \({\mathcal {E}}^\textsf {santz}\) its sanitized scheme. If \({\mathcal {E}}^\textsf {santz}\) is \({\mathcal {C}}\)-homomorphic, then it is circuit-private\(^+\) for \({\mathcal {C}}\).

We first highlight the key steps; the formal proof details appear subsequently.

To prove that \({\mathcal {E}}^\textsf {santz}\) is circuit-private\(^+\), we show that ciphertexts resulting from homomorphic evaluation over maliciously crafted ciphertexts are statistically close to those resulting from first decrypting then computing in cleartext and then encrypting the output. Sanitizing these ciphertexts (as done in \({\mathcal {E}}^\textsf {santz}\)) is aimed for guaranteeing this statistical closeness. However, the sanitization guarantee holds only if these ciphertexts decrypt to the same message; proving the latter is the heart of our proof.

We cannot rely on homomorphism to argue the latter, because correct evaluation is guaranteed only on “fresh” encryptions (cf. maliciously crafted ciphertexts as in our scenario). To address this issue we introduce a “hybrid” experiment, where we decrypt-and-then-encrypt the ciphertexts given as input to \(\textsf{Eval}\), which guarantees that they are fresh encryptions. (We rely on full decryption to ensure that decryption yields some element in the message space.) In this hybrid experiment correct evaluation indeed holds.

To guarantee that correct evaluation holds even without re-encryption, we rely on the fact that in \({\mathcal {E}}^\textsf {santz}\) we sanitize also the input to \(\textsf{Eval}\) and not just its output. This “inner” sanitization guarantees that the sanitized input ciphertexts are statistically close to those in the hybrid experiment (since they decrypt to the same message); from this (together with their statistical independent due to injecting fresh randomness in each sanitization) we derive that the ciphertext produced by the homomorphic evaluation is statistically close to the one produced in the hybrid experiment. This in turn implies that they decrypt to the same message.

Proof of Lemma 2

Let \({\mathcal {E}}=(\textsf{Gen},\textsf{Enc},\textsf{Dec},\textsf{Eval})\) be a fully decryptable HE scheme with a sanitization algorithm Sanitize. Denote by \({\mathcal {E}}^\textsf {santz}= (\textsf{Gen},\textsf{Enc}^\textsf {santz},\textsf{Dec},\textsf{Eval}^\textsf {santz})\) its sanitized version as specified in Definition 11. Let \({\mathcal {C}}\) be the set of circuits so that \({\mathcal {E}}^\textsf {santz}\) is \({\mathcal {C}}\)-homomorphic. We show that \({\mathcal {E}}^\textsf {santz}\) is circuit-private\(^+\) for \({\mathcal {C}}\).

Fix a circuit \(C\in {\mathcal {C}}\) over \(\ell \) inputs, ciphertexts \(c_1,\dots ,c_\ell \), a security parameter \(\lambda \). To prove circuit-privacy\(^+\) holds, we need to show the two ciphertexts \(\textsf{Enc}^\textsf {santz}_{pk}\left( C\left( \textsf{Dec}_{sk}(c_1),\cdots ,\textsf{Dec}_{sk}(c_\ell ) \right) \right) \) and \(\textsf{Eval}^\textsf {santz}_{pk}\left( C, c_1,\dots ,c_\ell \right) \) are statistically close, with overwhelming probability over the choice of \((pk,sk)\leftarrow \textsf{Gen}(\lambda )\).

By definition of \({\mathcal {E}}^\textsf {santz}\),

and

By the sanitization property of \(\textsf {Sanitize}\), if two ciphertexts decrypt to the same plaintext then their sanitized version is statistically close. Therefore, it is sufficient to show that the corresponding ciphertexts in the above two equations (i.e., \(\textsf{Enc}_{pk}\left( C\left( \textsf{Dec}_{sk}(c_1),\ldots ,\textsf{Dec}_{sk}(c_\ell ) \right) \right) \) and \(\textsf{Eval}_{pk}( C, \textsf {Sanitize}_{pk}(c_1),\dots ,\textsf {Sanitize}_{pk}(c_\ell ) )\)) decrypt to the same plaintext.

The correctness property of \({\mathcal {E}}\) together with it being fully decryptable ensures that for every \((pk,sk)\leftarrow \textsf{Gen}(1^\lambda )\):

and

where the probabilities are taken over the random coins of the encryption algorithm.

From Eq. 6 together with the sanitization property of \(\textsf {Sanitize}\), we obtain that, for each \( i\in [\ell ]\), with probability \(\ge 1 - {\textsf{neg}}(\lambda )\) over the choice of \((pk, sk) \leftarrow \textsf{Gen}(1^\lambda )\):

Moreover, with probability \(\ge 1-{\textsf{neg}}(\lambda )\), the above holds for all \(i\in [\ell ]\) simultaneously (by union bound).

Since \(\textsf {Sanitize}\) uses independent randomness for each \(i\in [\ell ]\), its output on distinct i’s is statistically independent. So the joint distribution over all \(i\in [\ell ]\) is likewise negligible (since the statistical distance of the joint distribution of independent random variables is the sum of their statistical distances, and the number of random variables is \(\ell ={\textsf{poly}}(\lambda )\)). Namely,

The \({\mathcal {C}}\)-homomorphism of \({\mathcal {E}}^\textsf {santz}\) guarantees that \({\mathcal {E}}^*=(\textsf{Gen},\textsf{Enc}^\textsf {santz},\textsf{Dec},\textsf{Eval})\) is likewise \({\mathcal {C}}\)-homomorphic (due to the message-preservation property of \(\textsf {Sanitize}\)), and hence for every \((pk,sk)\leftarrow \textsf{Gen}(1^\lambda )\) it holds that,

Combining Equations  8-9 we guarantee correctness of \(\textsf{Eval}\) on the sanitized \(c_1,\dots ,c_{\ell }\). That is, for every \((pk,sk)\leftarrow \textsf{Gen}(1^\lambda )\) it holds that,

Using the correctness property of \({\mathcal {E}}\) as stated in Equation  7, we obtain that for every \((pk,sk)\leftarrow \textsf{Gen}(1^\lambda )\) it holds that with probability \(\ge 1-{\textsf{neg}}(\lambda )\) over the random coins of the experiment,

This concludes the proof as by the sanitization property of \(\textsf {Sanitize}\), we obtain that with probability \(\ge 1 - {\textsf{neg}}(\lambda )\) over the choice of \((pk, sk) \leftarrow \textsf{Gen}(1^\lambda )\) and the random coins in \( \textsf{Enc}\) and \(\textsf{Eval}\) the following distributions are statistically close,

and

as desired. \(\square \)

Circuit privacy\(^+\) implies funcCPA. We prove that a HE scheme is funcCPA-secure if it is CPA-secure and circuit-private\(^+\).

Lemma 3

(circuit-privacy\(^+\) implies funcCPA) Let \({\mathcal {E}}\) be a CPA-secure PKE. If \({\mathcal {E}}\) is \({\mathcal {C}}\)-homomorphic and circuit-private\(^+\) for \({\mathcal {C}}\), then \({\mathcal {E}}\) is \(\textsf {funcCPA}\)-secure w.r.t. \({\mathcal {C}}\).

Proof

The main proof idea is to carefully replace \(\textsf{Enc}_{pk}({\mathcal {G}}(\textsf{Dec}_{sk}(\cdot )))\) oracle calls with \(\textsf{Eval}\) operations; details follow.

Let \({\mathcal {E}}= (\textsf{Gen}, \textsf{Enc}, \textsf{Dec},\textsf{Eval})\) be a \(\textsf {CPA}\)-secure \({\mathcal {C}}\)-homomorphic encryption scheme with message space \({\mathcal {M}}\) that is circuit-private\(^+\) for \({\mathcal {C}}\). For any ppt adversary \({\mathcal {A}}\) that participates in \(\textsf{EXP}^{Fcpa}_{{\mathcal {A}},{\mathcal {E}}, {\mathcal {C}}} \) we construct an adversary \({\mathcal {B}}\) for \( \textsf{EXP}^{cpa}_{{\mathcal {B}},{\mathcal {E}}} \) that behaves as follows: The adversary \({\mathcal {B}}\) runs \({\mathcal {A}}\) internally while relaying messages between the challenger and \({\mathcal {A}}\), with the exception that \(\textsf{Enc}_{pk}({\mathcal {C}}(\textsf{Dec}_{sk}(\cdot )))\) queries are answered using \(\textsf{Eval}\). That is, \({\mathcal {B}}\) does the following:

• Upon receiving pk from challenger, forward it to \({\mathcal {A}}\).

• Answer queries \(({\textbf{e}},n)\) to \(\textsf{Enc}_{pk}({\mathcal {C}}(\textsf{Dec}_{sk}(\cdot )))\) by \({\textbf{e}}'\leftarrow \textsf{Eval}_{pk}\left( C_n, {\textbf{e}}\right) \).

• Once \({\mathcal {A}}\) generates \(x_0,x_1\) forward them to the challenger and return the response \({\textbf{c}}\leftarrow \textsf{Enc}_{pk}(x_b)\) to \({\mathcal {A}}\).

• Output the \(b'\) that \({\mathcal {A}}\) outputs.

The adversary \({\mathcal {B}}\) is ppt (due to \({\mathcal {A}}\) and \(\textsf{Eval}\) being ppt), and all the interaction of \({\mathcal {A}}\) is perfectly simulated by \({\mathcal {B}}\) except for the responses to queries to \(\textsf{Enc}_{pk}({\mathcal {C}}(\textsf{Dec}_{sk}(\cdot )))\) that are simulated using \(\textsf{Eval}\). Circuit privacy\(^+\) of \({\mathcal {E}}\) guarantees that these responses are indistinguishable from decrypting, applying \(C_n\) and encrypting the result.

More formally, we define a series of hybrid executions that gradually move between \(\textsf{EXP}^{Fcpa}_{{\mathcal {A}},{\mathcal {E}}, {\mathcal {C}}}\) experiment (where \( \textsf{Enc}_{pk}({\mathcal {C}}(\textsf{Dec}_{sk}(\cdot ))) \) oracle is used) to \(\textsf{EXP}^{cpa}_{{\mathcal {B}},{\mathcal {E}}}\) experiment (where \(\textsf{Eval}\) is used). Let q denote an upper bound on the number of queries done by \({\mathcal {A}}\), we define \(q+1\) hybrids as follows:

Hybrid \( {{{\textbf {{\textsf {H}}}}}}_0\):

is defined as the execution of \(\textsf{EXP}^{Fcpa}_{{\mathcal {A}},{\mathcal {E}}, {\mathcal {C}}}\).

Hybrid \( {{{\textbf {{\textsf {H}}}}}}_i\):

is defined for \(i\in [q]\). The hybrid \( {\textsf{H}}_i\) is defined as \(\textsf{EXP}^{Fcpa}_{{\mathcal {A}}_i,{\mathcal {E}}, {\mathcal {C}}}\), where \({\mathcal {A}}_i\)’s last i queries are answered using \(\textsf{Eval}\) instead of oracle \(\textsf{Enc}_{pk}({\mathcal {C}}(\textsf{Dec}_{sk}(\cdot )))\).

Note that \( {\textsf{H}}_q\) is equivalent to the \( \textsf {CPA}\)-experiment \(\textsf{EXP}^{cpa}_{{\mathcal {B}},{\mathcal {E}}}\), and hence,

In each pair of adjacent hybrids \( {\textsf{H}}_{i-1}\) and \( {\textsf{H}}_{i}\), the difference is that in \( {\textsf{H}}_{i}\) the \((q-i+1)\)’th query is done using \(\textsf{Eval}\) instead \(\textsf{Enc}_{pk}({\mathcal {C}}(\textsf{Dec}_{sk}(\cdot ))) \) oracle. In this case the indistinguishability follows from \({\mathcal {E}}\) being circuit-private\(^+\) for \({\mathcal {C}}\). Namely,

Since q is polynomial in \(\lambda \), by the hybrid argument the indistinguishability of \(\textsf{EXP}^{Fcpa}_{{\mathcal {A}},{\mathcal {E}},{\mathcal {C}}}\) and \(\textsf{EXP}^{cpa}_{{\mathcal {B}},{\mathcal {E}}}\) follows. Finally, from the \(\textsf {CPA}\)-security of \({\mathcal {E}}\) and Eq. 10 we conclude that

As required. \(\square \)

3.3 funcCPA Security of leveled HE Schemes

We show that CPA implies funcCPA for leveled HE schemes satisfying a natural property. This property is satisfied, e.g., by BV [17], BGV [16] and B/FV [15, 27] (with a slight modification of their evaluation key), see Corollary 1.

Concretely, we address leveled HE schemes where each level is associated with a set of keys (usually, public, secret and evaluation keys), each ciphertext is associated with a (efficiently recognizable) level corresponding to the keys used for this ciphertext, and the scheme has independent level keys in the sense that the public and secret key pair can be sampled independently for each level, and the evaluation key for each level can be efficiently generated from the secret key for the current level and the public key for the next level.

Definition 13

(independent level keys) We say that a leveled HE scheme \({\mathcal {E}}=(\textsf{Gen},\textsf{Enc},\textsf{Dec},\textsf{Eval})\) has independent level keys if \( \textsf{Gen}\) (level key generation) takes as input the security parameter \(1^\lambda \) and a number of levels \(1^L\), uses ppt algorithms \(\textsf{GenKey}\) and \(\textsf{GenEvKey}\), and outputs for each level \(\ell \in \{0,\ldots ,L\}\) a public key, secret key, and an evaluation key defined by: \( (pk_\ell ,sk_\ell )\leftarrow \textsf{GenKey}(1^\lambda ) \hbox { and } evk_\ell \leftarrow \textsf{GenEvKey}(sk_{\ell },pk_{\ell -1}) \) denoted: \((pk_\ell , evk_\ell ,sk_\ell ,)_{\ell \in [L]}\leftarrow \textsf{Gen}(1^\lambda ,1^L)\)

We reformulate the definition of funcCPA to capture security for leveled HE schemes (leveled-funcCPA) as follows: the adversary can choose the level to which the challenge ciphertext is encrypted, and the “decrypt-function-encrypt" oracle is modified to return a ciphertext for the next level. That is, to answer a query on a ciphertext of level \(\ell \), the ciphertext is first decrypted using \(sk_\ell \), then the requested function is calculated on the plaintext and the result is encrypted under the public key for the next level \(pk_{\ell - 1}\) and returned to the adversary, see Definition 14.

The leveled-funcCPA indistinguishability experiment \(\textsf{EXP}^{Fcpa}_{{\mathcal {A}}, {\mathcal {E}}, {\mathcal {G}}}(\lambda ,L)\) for leveled HE  is parameterized by the security parameter \(\lambda \) and number of levels L, and executed between a challenger \(\textsf {Chal}\) and an adversary \({\mathcal {A}}\):

1. 1.

   \(\textsf{Gen}(1^\lambda ,1^L)\) is run to obtain keys \((pk_\ell ,sk_\ell )_{\ell \in \{0,\ldots ,L\}}\) (we consider the public key \(pk_\ell \) to include the evaluation key \(evk_\ell \) if it exists).

2. 2.

   The adversary \({\mathcal {A}}\) is given \((pk_\ell )_{\ell \in \{0,\ldots ,L\}}\) and access to a decrypt-function-encrypt oracle, denoted \(\{\textsf{Enc}_{pk_{\ell -1}}({\mathcal {G}}(\textsf{Dec}_{sk_\ell }(\cdot )))\}_{\ell \in [L]}\), defined as follows: the queries to this oracle are pairs \(({\textbf{e}}_\ell ,n)\) consisting of a ciphertext \({\textbf{e}}_\ell \) of some level \(\ell \in [L]\) (where the level is efficiently identifiable given the ciphertext) and a function index n, and the response is \({\textbf{e}}'\leftarrow \textsf{Enc}_{pk_{\ell -1}}(G_n(\textsf{Dec}_{sk_\ell }({\textbf{e}}_\ell )))\).^{Footnote 9}

3. 3.

   \({\mathcal {A}}\) outputs a pair of messages \(x_0, x_1\in {\mathcal {M}}\) s.t. \(|x_0| = |x_1|\) and \(\ell \in \{0,\ldots ,L\}\).

4. 4.

   A random bit \(b \in \{ 0,1 \}\) is chosen, and the ciphertext \(c\leftarrow \textsf{Enc}_{pk_\ell }(x_b)\) is computed and given to \({\mathcal {A}}\). We call c the challenge ciphertext. \({\mathcal {A}}\) continues to have access to the oracle.

5. 5.

   The adversary \({\mathcal {A}}\) outputs a bit \(b'\). The experiment’s output is defined to be 1 if \(b'=b\) (0 otherwise).

Definition 14

(\(\textsf {funcCPA}\) for leveled HE) A leveled HE scheme \({\mathcal {E}}= (\textsf{Gen}, \textsf{Enc}, \textsf{Dec},\textsf{Eval})\) with message space \({\mathcal {M}}\) is leveled-funcCPA-secure with respect to a family of functions \({\mathcal {G}}=\{G_n:{\mathcal {M}}\rightarrow {\mathcal {M}}\}_{n\in {\mathbb {N}}}\) (leveled-funcCPA-secure w.r.t. \({\mathcal {G}}\)) if for every ppt adversary \({\mathcal {A}}\) and L polynomial in the security parameter \(\lambda \), there exists a negligible function \({\textsf{neg}}(\cdot )\) such that:

where the probability is taken over all random coins of the experiment.

We prove that CPA-secure leveled HE schemes with independent level keys are funcCPA-secure w.r.t any admissible family \({\mathcal {G}}\). Admissible here says that all \(G_n\in {\mathcal {G}}\) are polynomial-time computable and have fixed output length \(|G_n(x_0)|= |G_n(x_1)|\) for all \(x_0,x_1 \in {\mathcal {M}}\). (We note that the latter trivially holds when \({\mathcal {G}}\) is a family of circuits.)

Theorem 10

(leveled HE is funcCPA) Let \({\mathcal {E}}\) be a leveled HE scheme with independent level keys. If \({\mathcal {E}}\) is CPA-secure, then \({\mathcal {E}}\) is leveled-funcCPA-secure w.r.t. any admissible family \({\mathcal {G}}\).

Proof

Let \({\mathcal {E}}= (\textsf{Gen}, \textsf{Enc}, \textsf{Dec}, \textsf{Eval})\) be a CPA-secure public-key leveled HE scheme with message space \({\mathcal {M}}\). Assume by contradiction that there exists an admissible family of functions \({\mathcal {G}}=\{G_n:{\mathcal {M}}\rightarrow {\mathcal {M}}\}_{n\in {\mathbb {N}}}\) over \({\mathcal {M}}\) such that \({\mathcal {E}}\) is not funcCPA-secure w.r.t \({\mathcal {G}}\). That is, there exists a ppt adversary \({\mathcal {A}}\), L polynomial in the security parameter \(\lambda \), and a polynomial \(p(\cdot )\) such that for infinitely many \(\lambda \) it holds that:

We show below that given \({\mathcal {A}}\) we can construct an adversary \({\mathcal {B}}\) that wins in \(\textsf{EXP}^{cpa}_{{\mathcal {B}},{\mathcal {E}}}(\lambda , L)\) with non-negligible advantage, violating the \(\textsf {CPA}\) security of \({\mathcal {E}}\).

The adversary \({\mathcal {B}}\) executes \({\mathcal {A}}\), relaying messages between the challenger and \({\mathcal {A}}\), while responding to any query \(({\textbf{e}}_\ell ,n)\) from \({\mathcal {A}}\) with an encryption using \(pk_{\ell -1}\) of \(G_n\) on an arbitrary message \(m\in {\mathcal {M}}\). That is \({\mathcal {B}}\) does the following,

• Upon receiving \((pk_\ell )_{\ell \in \{0,\ldots ,L\}}\) from challenger, forward it to \({\mathcal {A}}\).

• Answer queries \(({\textbf{e}}_\ell ,n)\) for a ciphertext \({\textbf{e}}_\ell \) of level \(\ell \) by \({\textbf{e}}'\leftarrow \textsf{Enc}_{pk_{\ell -1}}(G_n(m))\) for an arbitrary \(m\in {\mathcal {M}}\).

• Once \({\mathcal {A}}\) generates \(x_0,x_1\) and \(\ell \) forward them to the challenger and return the response \(c\leftarrow \textsf{Enc}_{pk_\ell }(x_b)\) to \({\mathcal {A}}\).

• Output the \(b'\) that \({\mathcal {A}}\) outputs.

The adversary \({\mathcal {B}}\) is ppt due to adversary \({\mathcal {A}}\) being ppt and admissibility of \({\mathcal {G}}\). Moreover all the interaction of \({\mathcal {A}}\) is perfectly simulated by \({\mathcal {B}}\) except for the responses to queries to \(\{\textsf{Enc}_{pk_{\ell -1}}({\mathcal {G}}(\textsf{Dec}_{sk_\ell }(\cdot )))\}_{\ell \in [L]}\) that are simulated using encryption of the image of \(G_n\) on an arbitrary message.

Let \(\textsf{EXP}^{Fcpa^\#}\) experiment denote this variant of \(\textsf{EXP}^{Fcpa}\) that is simulated by \({\mathcal {A}}\), namely \(\textsf{EXP}^{Fcpa^\#}\) is an experiment identical to \(\textsf{EXP}^{Fcpa}\) except that each query \(({\textbf{e}}_\ell ,n)\) to \(\textsf {Chal}\) is answered by the encryption of \(G_n(m)\) under \(pk_{\ell -1}\) for arbitrary \(m\in {\mathcal {M}}\).

By definition of \(\textsf{EXP}^{Fcpa^\#}\) it holds that,

Furthermore, the \(\textsf {CPA}\) security and independent level keys of \({\mathcal {E}}\) guarantees (as shown in Lemma 4 below) that \({\mathcal {A}}\)’s winning probability in \(\textsf{EXP}^{Fcpa^\#}\) and \(\textsf{EXP}^{Fcpa}\) is computationally indistinguishable. In particular,

Putting Eq. 13 together with Eqs. 11-12, it follows that

Combining this with \({\mathcal {A}}\) being \(\textsf {ppt}\), we derive a contradiction to \({\mathcal {E}}\) being \( \textsf {CPA}\) secure. This concludes the proof. \(\square \)

Let \(\textsf{EXP}^{Fcpa^\#}\) be as defined in the proof of Theorem 10, i.e., it is identical to \(\textsf{EXP}^{Fcpa}\) except that \(\textsf {Chal}\), upon receiving queries \(({\textbf{e}}_\ell ,n)\), instead of responding as in step 2 in Definition 14, responds by sending the encryption under \(pk_{\ell -1}\) of \(G_n(m)\) for an arbitrary message \(m\in {\mathcal {M}}\) (rather then \(m=\textsf{Dec}_{sk_\ell }({\textbf{e}}_\ell )\)). We show that the adversary is indifferent to the correctness of answers it receives from the \(\textsf {Chal}\) in the sense that its output distribution in \(\textsf{EXP}^{Fcpa}\) and \(\textsf{EXP}^{Fcpa^\#}\) is indistinguishable.

Lemma 4

Let \({\mathcal {E}}= (\textsf{Gen}, \textsf{Enc}, \textsf{Dec}, \textsf{Eval})\) be a CPA-secure leveled HE scheme with a message space \({\mathcal {M}}\). Let \({\mathcal {G}}=\{G_n:{\mathcal {M}}\rightarrow {\mathcal {M}}\}_{n\in {\mathbb {N}}}\) be a family of admissible functions. If \({\mathcal {E}}\) has independent level keys then for any \(\textsf {ppt}\) adversary \({\mathcal {A}}\) and L polynomial in the security parameter \(\lambda \), there exists a negligible function \({\textsf{neg}}(\cdot )\) such that:

Proof

Assume by contradiction that Lemma 4 does not hold. That is, there exists a \(\textsf {ppt}\) adversary \({\mathcal {A}}\), L polynomial in the security parameter \(\lambda \), and a polynomial \(p(\cdot )\) such that for infinitely many \(\lambda \) it holds that:

We define a series of hybrid executions that gradually move between \(\textsf{EXP}^{Fcpa}_{{\mathcal {A}},{\mathcal {E}}, {\mathcal {G}}}(\lambda , L)\) execution (where \(\textsf {Chal}\) responds with \(\textsf{Enc}_{pk_{\ell -1}}(G_n(\textsf{Dec}_{sk_\ell }({\textbf{e}}_\ell )))\)) to \( \textsf{EXP}^{Fcpa^\#}_{{\mathcal {A}},{\mathcal {E}}, {\mathcal {G}}}(\lambda , L)\) execution (where \(\textsf {Chal}\) responds with an encryption of the image of \(G_n\) on an arbitrary message). Let L denote the number of levels. We define \(L+1\) hybrids as follows:

Hybrid \({{{\textbf {{\textsf {H}}}}}}_0 \):

is defined as the execution of \(\textsf{EXP}^{Fcpa}_{{\mathcal {A}},{\mathcal {E}}, {\mathcal {G}}}(\lambda , L)\).

Hybrid \( {{{\textbf {{\textsf {H}}}}}}_j\) (\(j=1,\ldots ,L\)):

is similar to \( {\textsf{H}}_0 \) except that the queries to \(\{\textsf{Enc}_{pk_{\ell -1}}({\mathcal {G}}(\textsf{Dec}_{sk_\ell }(\cdot )))\}_{\ell \in [L]}\) oracle for \(\ell \le j\), each query \(({\textbf{e}}_\ell ,n)\) is answered by \(\textsf{Enc}_{pk_{\ell -1}}(G_n(m))\) for an arbitrary \(m\in {\mathcal {M}}\) (instead of sending \(\textsf{Enc}_{pk_{\ell -1}}(G_n(\textsf{Dec}_{sk_\ell }({\textbf{e}}_\ell )))\) as in Definition 14, Step 2).

Note that in each pair of adjacent hybrids \( {\textsf{H}}_{j-1}\) and \( {\textsf{H}}_{j}\) for \(j\in [L]\) the difference is that in \( {\textsf{H}}_{j}\) all the queries of level j ciphertexts are answered using \(G_n(m)\) for an arbitrary m instead of \(\textsf{Dec}_{sk_j}({\textbf{e}}_j)\).

Denote by \(\textsf{EXP}^{H_j}_{{\mathcal {A}},{\mathcal {E}}, {\mathcal {G}}}(\lambda , L)\) the output of the experiment in hybrid \({\textsf{H}}_j\).

By the hybrid argument it follows from Eq. 15 that there exists \(j\in [L]\) such that:

We show that Eq. 16 contradicts \({\mathcal {E}}\) being \(\textsf {CPA}\) secure. That is, we construct an adversary \({\mathcal {B}}\) that communicates with the challenger \(\textsf {Chal}\) in the CPA indistinguishability experiment \(\textsf{EXP}^{cpa}_{{\mathcal {B}},{\mathcal {E}}}\) and wins with a non-negligible advantage over half. Concretely, \({\mathcal {B}}\) participates in \(\textsf{EXP}^{cpa}_{{\mathcal {B}},{\mathcal {E}}}\) by internally running \({\mathcal {A}}\) as follows:

1. 1.

   Upon receiving \(\{pk\}_{\ell \in \{0,\ldots ,L\}}\) from \(\textsf {Chal}\), \({\mathcal {B}}\) computes new keys \((pk'_\ell ,sk'_\ell )\) for every \(j \le \ell \le L\), and forwards \(\{pk_\ell \}_{\ell < j}\cup \{pk'_\ell \}_{j \le \ell \le L}\) while answering each query of \({\mathcal {A}}\) as follows:

   1. (a)

      For queries to oracle with \(({\textbf{e}}_\ell ,n)\) for ciphertexts of level \(\ell < j\) respond with \(\textsf{Enc}_{pk_{\ell -1}}(G_n(m))\) for an arbitrary \(m\in {\mathcal {M}}\).

   2. (b)

      For queries to oracle with \(({\textbf{e}}_\ell ,n)\) for ciphertexts of level \(\ell > j\) respond with \(\textsf{Enc}_{pk'_{\ell -1}}(G_n(\textsf{Dec}_{sk'_\ell }(e_\ell )))\).

   3. (c)

      For queries to oracle with \(({\textbf{e}}_\ell ,n)\) for ciphertexts of level \(\ell = j\) proceeds as follows:

      1. i.

         \({\mathcal {B}}\) sets \(m_0= G_n(\textsf{Dec}_{sk'_j}({\textbf{e}}_j))\), samples uniformly random \(m\in {\mathcal {M}}\), and sends \(m_0\) and \(m_1=G_n(m)\) and \(j-1\) to \(\textsf {Chal}\).

      2. ii.

         Upon receiving from \(\textsf {Chal}\) the challenge ciphertext \(c^* \leftarrow \textsf{Enc}_{pk_{j-1}}(m_{b^*})\) for uniformly random \(b^*\leftarrow \{0,1\}\), forward ciphertext \(c^*\) to \({\mathcal {A}}\).

   4. (d)

      Once \({\mathcal {A}}\) generates \(x_0,x_1\) and \(\ell \) choose a random \(b \in \{ 0,1 \}\) and respond with \(c\leftarrow \textsf{Enc}_{pk_\ell }(x_b)\) to \({\mathcal {A}}\).

2. 2.

   Let \(b'\) be the output of \({\mathcal {A}}\). \({\mathcal {B}}\) outputs 0 if \(b'=b\) and 1 otherwise.

We note that if \(b^*=0\), then the challenge ciphertext \(c^*\) is an encryption under \(pk_{j-1}\) of \(G_n(\textsf{Dec}_{sk_j}({\textbf{e}}_j))\) and of a random element in the range of \(G_n\) otherwise; moreover, since \({\mathcal {E}}\) has independent level keys, then the “fake” and real keys are identically distributed, i.e., \(\{sk_\ell ,pk_\ell \}_{\ell \in \{0,\ldots ,L\}}\equiv \{sk_\ell ,pk_\ell \}_{\ell <j}\cup \{sk'_\ell ,pk'_\ell \}_{j \le \ell \le L}\) Therefore, if \(b^*=0\) then the view of \({\mathcal {A}}\) is exactly as in \(H_{j-1}\) and otherwise as in \(H_j\). We obtain that

and since L is polynomial in \(\lambda \) we obtain

for some polynomial \(q(\cdot )\), in contradiction to the CPA-security of \({\mathcal {E}}\); this concludes the proof. \(\square \)

Schemes with independent level keys. In BV, BGV and B/FV, for example, indeed each ciphertext is associated with a level and there are independent encryption and decryption keys \((pk_\ell ,sk_\ell )\) for each level \(\ell \). Moreover, the evaluation key \(evk_\ell \) (called key switching in BV, BGV and B and re-linearization keys in FV) is essentially the encryption of an efficiently computable function of the secret key \(sk_\ell \) of the current level (concretely, the encryption of \(sk'_\ell = \textsf{Powersof}2(sk_\ell \otimes sk_\ell )\)) under the public key \(pk_{\ell -1}\) for the next level.

More accurately, to generate \(evk_\ell \) they use a fresh public key \(pk'_{\ell -1}\) with which they mask \(sk'_\ell \). This is important when instantiating their scheme as a fully homomorphic encryption, i.e., when there’s a single key tuple (pk, evk, sk) used for all levels, in which case using pk (rather than \(pk'\)) to encrypt a function of sk would require a circular security assumption. In contrast, when using these schemes as a leveled HE, as we do, then anyhow the keys \((pk_\ell ,sk_\ell )\) are sampled independently from \((pk_{\ell -1}, sk_{\ell -1})\), and so encrypting \(sk'_{\ell }\) under \(pk_{\ell -1}\) requires no circular security assumption. Therefore, their generation of the evaluation keys can be modified to output the encryption of \(sk'_\ell \) under \(pk_{\ell -1}\), without harming correctness or security.^{Footnote 10} With this slight modification indeed these scheme satisfy Definition 13.

Proposition 1

The leveled HE schemes of BV, BGV and B/FV [15,16,17, 27] (with the aforementioned evaluation key) have independent level keys.

Corollary 1

The leveled HE schemes of BV, BGV and B/FV [15,16,17, 27] (with the aforementioned evaluation key) are leveled-funcCPA-secure.

3.4 Barriers on Proving funcCPA for Existing HE Schemes

In this section we prove that if the homomorphic encryption scheme of BV [17] or BGV [16] is funcCPA-secure, then it is (weakly) circular secure. More generally, we show the above holds for all schemes satisfying a property we call oblivious secret key extraction (ObvSK). In the following we first formally define weak circular security and ObvSK; then prove that for schemes supporting ObvSK, funcCPA-security w.r.t a proper family \({\mathcal {F}}\) implies weak circular security; and conclude by showing that the schemes of BV and BGV support ObvSK.

Circular security extends CPA-security to capture security of public-key encryption schemes against adversaries seeing an encryption of the secret key [20, Definition 2.5].

Circular security is required by all fully homomorphic encryption schemes following Gentry’s [28] blueprint, as they publish an encryption of the secret key to be used during bootstrapping (where bootstrapping [28] is the process of homomorphically evaluating the scheme’s decryption circuit with a hardwired ciphertext on an encrypted secret key as input). Specifically, they require security to hold against adversaries seeing an encryption of the secret key in the encoding by which it is specified as input to the decryption circuit (see [17, Definition 3.8]).

Weak circular security is formally stated, for a public-key encryption scheme \({\mathcal {E}}= (\textsf{Gen}, \textsf{Enc}, \textsf{Dec})\), using the following experiment between a challenger \(\textsf {Chal}\) and an adversary \({\mathcal {A}}\) (where \(\textsf{sk}\) denotes the secret key when specified in the encoding as required for the decryption circuit):

The weak circular indistinguishability experiment \(\textsf{EXP}^{wc}_{{\mathcal {A}},{\mathcal {E}}}(\lambda )\):

1. 1.

   \(\textsf {Chal}\) computes \((pk, sk)\leftarrow \textsf{Gen}(1^\lambda )\) and \({\textbf{c}}_{sk}\leftarrow \textsf{Enc}_{pk}(\textsf{sk})\), and sends \((pk,{\textbf{c}}_{sk})\) to \({\mathcal {A}}\).

2. 2.

   \({\mathcal {A}}\) sends to \(\textsf {Chal}\) two messages \(x_0,x_1\) s.t. \(|x_0|=|x_1|\).

3. 3.

   \(\textsf {Chal}\) chooses a random bit \(b \in \{ 0,1 \}\), computes a ciphertext \(c \leftarrow \textsf{Enc}_{pk}(x_b)\) and sends c to \({\mathcal {A}}\). We call c the challenge ciphertext.

4. 4.

   \({\mathcal {A}}\) outputs a bit \(b'\).

5. 5.

   The output of the experiment is defined to be 1 if \(b' = b\) (0 otherwise).

Definition 15

(weak circular security) A PKE scheme \({\mathcal {E}}=(\textsf{Gen},\textsf{Enc},\textsf{Dec})\) is weakly circular secure if for every ppt adversary \({\mathcal {A}}\), there exists a negligible function \({\textsf{neg}}(\cdot )\) such that:

where the probability is taken over the random coins of \({\mathcal {A}}\) and \(\textsf {Chal}\).

Oblivious secret key extraction captures the ability to generate, from the public key, ciphertexts encrypting data related to the secret key, so that from their decryption one can efficiently compute the secret key in the encoding as required for the decryption circuit.

Definition 16

(oblivious secret key extraction (ObvSK)) Let \({\mathcal {E}}= (\textsf{Gen}, \textsf{Enc}, \textsf{Dec})\) be a PKE scheme with message space \({\mathcal {M}}\), and \({\mathcal {F}}= \{F_n:{\mathcal {M}}\rightarrow {\mathcal {M}}\}_{n\in {\mathbb {N}}}\) be a family of functions. We say that \({\mathcal {E}}\) supports oblivious secret key extraction (ObvSK) w.r.t \({\mathcal {F}}\) if there exists a ppt algorithm \(\textsf {Alg}\) that takes a public key pk and outputs \(n=n(\lambda )\) ciphertexts under pk, so that the following holds. There exists a negligible function \({\textsf{neg}}(\cdot )\) such that for all \(\lambda \in {\mathbb {N}}\) the following holds:

where the secret key \(\textsf{sk}\) outputted by \(F_n\) is in the encoding required for the decryption circuit, and where the probability is taken over the randomness in \(\textsf{Gen}\) and \(\textsf {Alg}\).

funcCPA-security for schemes supporting ObvSK implies weak circular security. Next we show that if a public-key encryption scheme \({\mathcal {E}}\) support ObvSK w.r.t \({\mathcal {F}}\) and is funcCPA-secure w.r.t \({\mathcal {G}}\) that contains \({\mathcal {F}}\), then \({\mathcal {E}}\) is weakly circular secure.

Theorem 11

Let \({\mathcal {E}}=(\textsf{Gen},\textsf{Enc},\textsf{Dec})\) be a PKE scheme that is \(\textsf {funcCPA}\)-secure w.r.t a family of functions \({\mathcal {G}}\). If \({\mathcal {E}}\) is ObvSK w.r.t \({\mathcal {F}}\) and \({\mathcal {F}}\subseteq {\mathcal {G}}\) then \({\mathcal {E}}\) is weakly circular secure.

Proof

The proof idea is, given pk, to first use \(\textsf {Alg}\) (from the ObvSK property) to get encrypted data related to sk; then use \(\textsf{Enc}_{pk}({\mathcal {G}}(\textsf{Dec}_{sk}(\cdot )))\) (from the funcCPA property) to transform them to ciphertexts \({\textbf{c}}_{sk}\) encrypting sk (in the encoding for the decryption circuit); finally show that—if the scheme is not circular secure—then using \({\textbf{c}}_{sk}\) we can break funcCPA-security. The formal details follow.

Suppose by contradiction that \({\mathcal {E}}\) is not circular secure, i.e., there exists a ppt adversary \({\mathcal {A}}\) that wins \(\textsf{EXP}^{wc}_{{\mathcal {A}},{\mathcal {E}}}\) with non-negligible advantage over a random guess. We construct an adversary \({\mathcal {B}}\) that runs \({\mathcal {A}}\) internally and breaks funcCPA-security of the scheme.

The adversary \({\mathcal {B}}\) participates in the funcCPA-security experiment as follows. First, given pk from \(\textsf {Chal}\), \({\mathcal {B}}\) computes \((c_1,\ldots ,c_n) \leftarrow \textsf {Alg}(pk)\) (for \(\textsf {Alg}\) as guaranteed by the ObvSK property), sends a query \(((c_1,\ldots ,c_n),n)\) to the \(\textsf{Enc}_{pk}({\mathcal {G}}(\textsf{Dec}_{sk}(\cdot )))\) oracle (provided as part of the funcCPA experiment), and receives in response (the vector of ciphertexts)

which is an encryption of the secret key sk in the encoding as needed for bootstrapping with \(1-{\textsf{neg}}(\lambda )\) probability (by the ObvSK property). Next \({\mathcal {B}}\), internally runs \({\mathcal {A}}\), while providing to it \({\textbf{c}}_{sk}\) together with pk, relaying messages between \({\mathcal {A}}\) and \(\textsf {Chal}\), and outputting the guess \(b'\) outputted by \({\mathcal {A}}\).

The view of \({\mathcal {A}}\) in \(\textsf{EXP}^{Fcpa}_{{\mathcal {B}},{\mathcal {E}}}\) is identical to its view in \(\textsf{EXP}^{wc}_{{\mathcal {A}},{\mathcal {E}}}\) (except with a \({\textsf{neg}}(\lambda )\) probability, for the case of failure in the ObvSK). Implying (by the contradiction assumption)

for some polynomial \(p(\cdot )\), in contradiction to the funcCPA-security of \({\mathcal {E}}\). \(\square \)

As a corollary from Theorem 11 we conclude that for bootstrappable ObvSK schemes, funcCPA-security implies full homomorphism without relying on any circular security assumption.

Corollary 2

Let \({\mathcal {E}}=(\textsf{Gen},\textsf{Enc},\textsf{Dec},\textsf{Eval})\) be a bootstrappable HE scheme that supports ObvSK w.r.t \({\mathcal {F}}\). If \({\mathcal {E}}\) is \(\textsf {funcCPA}\)-secure w.r.t \({\mathcal {G}}\) and \({\mathcal {F}}\subseteq {\mathcal {G}}\) then \({\mathcal {E}}\) is fully homomorphic.

Proof

The proof is derived by combining the following two facts. First, by Theorem 4.3.2 in [28], bootstrappable HE schemes that are weakly circular secure are fully homomorphic. Second, by Theorem 11, if \({\mathcal {E}}\) support ObvSK w.r.t \({\mathcal {F}}\) and it is \(\textsf {funcCPA}\)-secure w.r.t \({\mathcal {G}}\) that contains \({\mathcal {F}}\), then \({\mathcal {E}}\) is weakly circular secure. Combining the above, we conclude that \({\mathcal {E}}\) is fully homomorphic. \(\square \)

Schemes supporting ObvSK. BV and BGV are examples of schemes supporting ObvSK. More generally, we show that ObvSK is supported by all public-key encryption schemes \({\mathcal {E}}=(\textsf{Gen},\textsf{Enc},\textsf{Dec})\) satisfying the following:

1. 1.

   The secret key \(sk=(1,s)\) and ciphertext c are from the ring:

   • LWE-based schemes: \({\mathbb {Z}}_q^{n+1}\)

   • RLWE-based schemes: \(R_q^2\) for \(R_q = {\mathbb {Z}}_q[x]/F[X]\)

   where q, n, d are positive integers, d a power of 2, \(F[X]=X^d + 1\), and s has small coefficients in the sense that decryption correctness holds on ciphertexts encrypting each coefficient of s.

2. 2.

   Decryption is via inner-product (with messages encoded in the least significant bits): \(\textsf{Dec}_{sk}(c) = \left[ \left[ \langle c,sk\rangle \right] _q \right] _p\) where \([z]_x\) is the remainder of z in division by x and p a positive integer.

In the following let \({\mathcal {F}}^{LWE} = \{F^{LWE}_n:{\mathbb {Z}}_q^n\rightarrow \{ 0,1 \}^{n\cdot \lceil \log q\rceil }\}_{q,n}\) denote a family of functions that given \((s_1,\ldots ,s_n)\in {\mathbb {Z}}_q^n\) outputs \(sk=(1,s)\in {\mathbb {Z}}_q^{n+1}\) in the encoding as required by the decryption circuit in LWE-based schemes satisfying the above properties. Similarly, let \({\mathcal {F}}^{RLWE} = \{F^{RLWE}_d:R_q \rightarrow R_q^2\}_{q,d}\) denote a family of functions that given \((s'_{d-1},\ldots ,s'_0) \in R_q\) outputs \(sk=({\textbf{1}}, (-s'_0,s'_{d-1},\ldots ,s'_1)) \in R_q^2\) in the encoding as required by the decryption circuit in the RLWE-based schemes satisfying the above properties. (Here \((s'_{d-1},\ldots ,s'_0)\) is a vector of coefficients specifying a polynomial \(s'(X)\in R_q\), and \({\textbf{1}}\) denotes the unit element in \(R_q\).) Moreover, for a scheme \({\mathcal {E}}\) satisfying the above properties, either in the LWE-based or RLWE-based form, we use the short hand notation of denoting by \({\mathcal {F}}^{GLWE}\) the family \({\mathcal {F}}^{LWE}\) in case \({\mathcal {E}}\) is LWE-based, and \({\mathcal {F}}^{RLWE}\) otherwise.

Proposition 2

Suppose \({\mathcal {E}}=(\textsf{Gen},\textsf{Enc},\textsf{Dec})\) satisfies (1)-(2) above. Then \({\mathcal {E}}\) supports ObvSK w.r.t. \({\mathcal {F}}^{GLWE}\).

Proof

The proof is case-by-case, presenting in each case an algorithm \(\textsf {Alg}\) producing ciphertexts so that from their decryption the secret key is efficiently computable (with probability \(1-{\textsf{neg}}(\lambda )\) when accounting for possible decryption errors). The secret key can then be transformed to the encoding required by the decryption circuit.

Case I: \({\mathcal {E}}\) is LWE-based with least significant bit encoding. Let \(\delta _i\in \{ 0,1 \}^n\) denote the indicator vector \(\delta _i(j)=1\) if-and-only-if \(j=i\). Let \(\textsf {Alg}_1(pk)\) be the algorithm that given pk computes \(c\leftarrow \textsf{Enc}_{pk}(0)\), computes \(c_i = c + (0,\delta _i) \mod q\) for \(i\in [n]\) and outputs \((c_1,\ldots ,c_n)\). Observe that, for all \(i\in [n]\), \(\textsf{Dec}_{sk}(c_i)\) returns the ith coordinate of the secret key \(sk =(1, s_1,\ldots ,s_n) \in {\mathbb {Z}}_q^{n+1}\) as follows:

Namely, given \(( \textsf{Dec}_{sk}(c_1), \dots , \textsf{Dec}_{sk}(c_n))=(s_1,\ldots ,s_n)\) we can efficiently recover the secret key sk.

Case II: \({\mathcal {E}}\) is RLWE-based with least significant bit encoding. Let \(\delta (X)\in R_q\) be the polynomial \(\delta (X) = X\). Let \(\textsf {Alg}_2(pk)\) be the algorithm that given pk computes \(c\leftarrow \textsf{Enc}_{pk}(0)\), computes \(c' = c + (0,\delta )\) in \(R_q^2\) and outputs \(c'\). Recall that \(sk = ({\textbf{1}}, s) \in R_q^2\) for \(s(X) = \sum _{i=0}^{d-1}s_iX^i\) a polynomial, and denote the coefficients of s by \((s_{d-1},\ldots ,s_0)\). We show that \(\textsf{Dec}_{sk}(c')\) returns the polynomial \(s' = \delta \cdot s\) in \(R_q\), from which sk can be efficiently computed.

We show that \(s'\) has coefficients \((s_{d-2},\ldots ,s_0,-s_{d-1})\):

where the last equality follows from \(X^d = -1 \mod F[X]\). We conclude that, from the coefficients \((s'_{d-1},\ldots ,s'_0)\) of \(s'\leftarrow \textsf{Dec}_{sk}(c')\), we can efficiently compute the coefficients of s by setting \(s_{d-1}:= -s'_0\) and \(s_i:= s'_{i+1}\) for all \(i\in \{0,\ldots ,d-2\}\), and outputting \(sk = ({\textbf{1}},s_{d-1},\ldots ,s_0)\). \(\square \)

As an immediate corollary from Proposition 2, we obtain that the addressed schemes support ObvSK.

Corollary 3

(BV and BGV support ObvSK) The HE schemes from BV [17] and BGV [16] support ObvSK w.r.t. \({\mathcal {F}}^{GLWE}\).

Since these schemes are known to be bootstrappable, then combining Corollary 3 with Corollary 2 we derive that if they are funcCPA-secure then they are fully homomorphic.

Corollary 4

If BV [17] or BGV [16] is funcCPA-secure w.r.t to \({\mathcal {G}}\) containing \({\mathcal {F}}^{GLWE}\), then it is fully homomorphic.

We show that CPA-security is insufficient for guaranteeing privacy in client-aided outsourcing protocols. For this purpose we construct a CPA-secure PKE scheme and exhibit an input-recovery attack that completely breaks privacy in client-aided outsourcing protocols instantiated with our scheme. In fact, we can transform any CPA-secure encryption scheme \({\mathcal {E}}\) with message space \({\mathcal {M}}\) of super polynomial size, using a one-way function f and any function G, into a CPA-secure encryption scheme \({\mathcal {E}}^f\) for which our attack works on any \(({\mathcal {E}}^f,{\mathcal {G}})\)-aided outsourcing protocol for any \({\mathcal {G}}\) containing G. Moreover, if \({\mathcal {E}}\) was an HE scheme then so is \({\mathcal {E}}^f\). For simplicity of the presentation we concentrate on G being the identity function \({\mathcal {I}}\) for the construction of \({\mathcal {E}}^f\). The scheme \({\mathcal {E}}^f\) is similar to \({\mathcal {E}}\), except for the key difference that its encryption and decryption are “punctured" on a random point \(m^*\in {\mathcal {M}}\), where its public key implicitly specifies \(m^*\) by augmenting it with \(f(m^*)\) and \(\textsf{Enc}_{pk}(m^*)\).^{Footnote 11} See our construction in Fig. 1 and Theorem 12. Our attack breaks security in the strong sense that the server is able to completely recover the client’s input; see Theorem 13.

The construction of the scheme \({\mathcal {E}}^f=(\textsf{Gen}^f,\textsf{Enc}^f,\textsf{Dec}^f,\textsf{Eval}^f)\) from a PKE scheme \({\mathcal {E}}=(\textsf{Gen},\textsf{Enc},\textsf{Dec},\textsf{Eval})\) with message space \({\mathcal {M}}\) and ciphertext space \({\mathcal {T}}\) and a one-way function f over \({\mathcal {M}}\). The message space and ciphertext space of \({\mathcal {E}}^f\) are \({\mathcal {M}}\times {\mathcal {M}}\) and \(({\mathcal {T}}\times {\mathcal {T}}) \cup ({\mathcal {M}}\times {\mathcal {M}})\) respectively

Full size image

Theorem 12

(properties of \({\mathcal {E}}^f\)) For every PKE scheme \({\mathcal {E}}\) and one-way function f over the message space of \({\mathcal {E}}\), the scheme \({\mathcal {E}}^f\) (cf. Fig. 1) is a PKE scheme satisfying the following. If \({\mathcal {E}}\) is CPA-secure, compact, and \({\mathcal {C}}\)-homomorphic, then \({\mathcal {E}}^f\) is CPA-secure, compact, and \({\mathcal {C}}\times {\mathcal {C}}\)-homomorphic.^{Footnote 12}

Proof

Correctness, compactness and homomorphism of \({\mathcal {E}}^f\) follow directly from the properties of \({\mathcal {E}}\). See the formal details in Lemma 6, Appendix A. The CPA-security of \({\mathcal {E}}^f\) follows from the CPA-security of \({\mathcal {E}}\) and the one-wayness of f: the encryption in \({\mathcal {E}}^f\) is identical to encrypting pairs \((m_1,m_2)\) of messages under \({\mathcal {E}}\), except if \(m_2\) is a pre-image of \(f(m^*)\), but the latter occurs with no more than a negligible probability due to f being a one-way function and \(m^*\) being a random message. See formal details in Lemma 7, Appendix A. \(\square \)

We present our attack in which the server recovers the client’s input in any \(({\mathcal {E}}^f,{\mathcal {G}})\)-aided outsourcing protocol for \({\mathcal {G}}\) containing the identity function \({\mathcal {I}}\). We remark that our attack is applicable from every PKE \({\mathcal {E}}\), regardless of whether it is a HE scheme.

Theorem 13

(CPA-security does not imply privacy) For every PKE scheme \({\mathcal {E}}\) with message space \({\mathcal {M}}\) and every one-way function f over \({\mathcal {M}}\), there exists a CPA-secure PKE scheme \({\mathcal {E}}^f\) so that for every family of functions \({\mathcal {G}}=\{G_n:{\mathcal {M}}\rightarrow {\mathcal {M}}\}_{n\in {\mathbb {N}}}\) containing the identity function \({\mathcal {I}}\) and every \(({\mathcal {E}}^f,{\mathcal {G}})\)-aided outsourcing protocol there is a server’s strategy that recovers the client’s input.

Proof

Denote \({\mathcal {E}}=(\textsf{Gen},\textsf{Enc},\textsf{Dec})\). Set \({\mathcal {E}}^f =(\textsf{Gen}^f,\textsf{Enc}^f,\textsf{Dec}^f)\) to be the encryption scheme constructed from \({\mathcal {E}}\) and f in Fig. 1.

Our active input-recovery attack is applicable on any \(({\mathcal {E}}^f,{\mathcal {G}})\)-aided outsourcing protocol \(\pi = \langle \textsf{Clnt},\textsf{Srv}\rangle \) as follows.

1. 1.

   \(\textsf{Clnt}\) executes phase 1 of \(\pi \). That is, it runs \((pk^f,sk^f)\leftarrow \textsf{Gen}^f(1^\lambda )\) to obtain a public key \(pk^f = (pk,\textsf{Enc}_{pk}(m^*),f(m^*))\), encrypts its input x by computing \({\textbf{c}}_{x} \leftarrow \textsf{Enc}^f_{pk^f}(x,x)\) and sends \({\textbf{c}}_{x}\) and \(pk^f\) to \(\textsf{Srv}\).

2. 2.

   Upon receiving \({\textbf{c}}_{x}=({\textbf{c}}_1,{\textbf{c}}_2)\) and \(pk^f\), \(\textsf{Srv}\) generates a new ciphertext \({\textbf{e}}= ({\textbf{c}}_1, \textsf{Enc}_{pk}(m^*))\), where \(\textsf{Enc}_{pk}(m^*)\) is taken from \(pk^f\), and sends \(({\textbf{e}},{\mathcal {I}})\) to \(\textsf{Clnt}\).

3. 3.

   \(\textsf{Clnt}\) sends \(({\textbf{c}}'_1,{\textbf{c}}'_2)\leftarrow \textsf{Enc}^f_{pk^f}( {\mathcal {I}}( \textsf{Dec}^f_{sk^f}( {\textbf{e}})))\) to \(\textsf{Srv}\).

4. 4.

   Upon receiving the client’s response \(({\textbf{c}}'_1,{\textbf{c}}'_2)\), \(\textsf{Srv}\) outputs \({\textbf{c}}'_1\).

The attack recovers the client’s input x because \({\textbf{c}}'_1 = x\) as explained next. Observe that \( {\mathcal {I}}(\textsf{Dec}^f_{sk^f}({\textbf{e}})) = (x,m^*) \) is a message where the encryption algorithms \(\textsf{Enc}^f_{pk^f}\) is punctured, implying that

Namely, \(({\textbf{c}}'_1,{\textbf{c}}'_2)=(x,m^*)\) in Step 3, and so \({\textbf{c}}'_1=x\). \(\square \)

We define a natural property for \(({\mathcal {E}},{\mathcal {G}})\)-aided outsourcing protocols (called cleartext computable), and show that for protocols satisfying this property, CPA-security guarantees privacy against semi-honest servers; see Theorem 14.

Cleartext-computable protocols. A protocol is cleartext computable if the messages whose encryption constitutes the client’s responses to the server’s queries are efficiently computable given only the client’s input. To formalize this we first define the client’s cleartext response. Let \(\pi =\langle \textsf{Clnt},\textsf{Srv}\rangle \) be an \(({\mathcal {E}},{\mathcal {G}})\)-aided outsourcing protocol (cf. Definition 9). The client’s cleartext response in an execution of \(\pi \) on client’s input x and randomness \(r_{\textsf{Clnt}}\), server’s randomness \(r_{\textsf{Srv}}\), and security parameter \(\lambda \in {\mathbb {N}}\), is defined by:

where \((sk,pk)\leftarrow \textsf{Gen}(1^\lambda )\) is the key pair generated by the client in Phase 1 of \(\pi \); q is the number of queries sent from server to client in Phase 2 of \(\pi \); and for each \(j\in [q]\), \((\mathbf {e_j},n_j)\) and \(\textsf{Enc}_{pk}(G_{n_j}(\textsf{Dec}_{sk}(\mathbf {e_j})))\) are the jth server’s query and the corresponding client’s response, respectively, with \(G_{n_j}(\textsf{Dec}_{sk}(\mathbf {e_j}))\) being the underlying cleartext response message.

Definition 17

(cleartext computable) An \(({\mathcal {E}},{\mathcal {G}})\)-aided outsourcing protocol \(\pi =\langle \textsf{Clnt},\textsf{Srv}\rangle \) for computing a function \( F:{\textsf{A}}\rightarrow {\textsf{B}}\) is cleartext computable if \(\textsf{Srv}\) is ppt and there exists a ppt function h such that for all inputs \(x\in {\textsf{A}}\), all client and server randomness \(r_{\textsf{Clnt}}\) and \(r_{\textsf{Srv}}\), respectively, and all \(\lambda \in {\mathbb {N}}\)

CPA-security implies privacy for cleartext computable protocols. We show that for cleartext computable \(({\mathcal {E}},{\mathcal {G}})\)-aided outsourcing protocols, CPA-security of \({\mathcal {E}}\) implies that the protocol preserves privacy against semi-honest servers.

Similarly to Theorem 10, the family \({\mathcal {G}}\) should be admissible in the sense that all \(G_n\in {\mathcal {G}}\) are polynomial-time computable (in the security parameter) and have fixed output length, i.e., \(|G_n(x_0)|= |G_n(x_1)|\) for all \(x_0,x_1 \in {\mathcal {M}}\).

Theorem 14

(privacy of cleartext computable protocols) Every cleartext computable \(({\mathcal {E}},{\mathcal {G}})\)-aided outsourcing protocol preserves privacy against semi-honest servers, provided that \({\mathcal {E}}\) is CPA-secure and \({\mathcal {G}}\) is admissible.

Proof

We show that for cleartext computable protocols, when instantiated with a CPA-secure encryption scheme, a semi-honest server cannot distinguish encrypted response of correct or random values, and hence privacy follows. The formal details follow.

Let \({\mathcal {E}}= (\textsf{Gen}, \textsf{Enc}, \textsf{Dec})\) be a CPA-secure public-key encryption scheme with message space \({\mathcal {M}}\), \({\mathcal {G}}=\{G_n:{\mathcal {M}}\rightarrow {\mathcal {M}}\}_{n\in {\mathbb {N}}}\) a family of admissible functions over \({\mathcal {M}}\), and \(\pi \) a \(({\mathcal {E}},{\mathcal {G}})\)-aided outsourcing protocol for a function \(F:{\textsf{A}}\rightarrow {\textsf{B}}\). Assume by contradiction that privacy does not hold for \(\pi \). That is, there exists a ppt distinguisher \({\mathcal {D}}\) that chooses \(x_0,x_1 \in {\textsf{A}}\) with \(|x_0|=|x_1|\), and a polynomial \(p(\cdot )\) such that for infinitely many \(\lambda \in {\mathbb {N}}\):

We show below that given \({\mathcal {D}}\) we can construct an adversary \({\mathcal {A}}\) that violate the \(\textsf {CPA}\) security of \({\mathcal {E}}\).

The adversary \({\mathcal {A}}\) participates in \( \textsf{EXP}^{cpa}_{{\mathcal {A}},{\mathcal {E}}} \) as follows:

1. 1.

   Upon receiving pk output \(x_0, x_1\) (as computed by \({\mathcal {D}}\)).

2. 2.

   Upon receiving \(\textsf{Enc}_{pk}(x_b)\) behave exactly as \(\textsf{Srv}\) behaves while executing \(\pi \) upon receiving \( \mathbf {c_x}\) and pk from \(\textsf{Clnt}\), except that every message \( ({\textbf{e}},n) \) (where \({\textbf{e}}\) is an encryption and \(n\in {\mathbb {N}}\)) sent from \(\textsf{Srv}\) to \(\textsf{Clnt}\) is answered by \({\mathcal {A}}\) as follows: \({\mathcal {A}}\) samples uniformly at random m from the domain of \(G_n\), computes \({\textbf{e}}'\leftarrow \textsf{Enc}_{pk}(G_n(m))\), and behaves as \(\textsf{Srv}\) upon receiving \({\textbf{e}}'\) as the response from \(\textsf{Clnt}\).

3. 3.

   Run the distinguisher \({\mathcal {D}}\) on \(\textsf {view}_{\textsf{Srv}}\) (\(\textsf{Srv}\)’s view in \({\mathcal {A}}\) during step 2) and output whatever \({\mathcal {D}}\) outputs.

The adversary \({\mathcal {A}}\) is \(\textsf {ppt}\) due to the admissibility of \({\mathcal {G}}\) and \(\textsf{Srv}\) and \({\mathcal {D}}\) being ppt. Note that \(\pi \) is almost perfectly simulated except that the queries to \(\textsf{Clnt}\) are simulated using encryption of the image of \(G_n\) on a randomly sampled elements in its domain. Let \(\pi '\) denote this variant of \(\pi \) that is simulated by \({\mathcal {A}}\), namely \(\pi '\) is a protocol identical to \(\pi \) except that each query \(({\textbf{e}},n)\) to \(\textsf{Clnt}\) is answered by the encryption of \(G_n(m)\) for a randomly sampled m from the domain of \(G_n\). We denote by \(\textsf {view}^{\textsf{EXP}^{cpa}}_{\textsf{Srv}}(x_b,\bot ,\lambda )\) the view of \(\textsf{Srv}\), simulated by \({\mathcal {A}}\), in the execution of \(\textsf{EXP}^{cpa}_{{\mathcal {A}},{\mathcal {E}}} \) with bit b being selected by the challenger. By definition of \(\pi '\) it holds that for every \(b\in \{ 0,1 \}\),

Furthermore, the \(\textsf {CPA}\) security of \({\mathcal {E}}\) and cleartext computability of \(\pi \) guarantees (as shown in Lemma 5 below) that the server’s view in \(\pi \) and \(\pi '\) is computationally indistinguishable. In particular, for every \(x\in {\textsf{A}}\)

Putting Eq. 21 together Lemma 5 and Eqs. 19-20, it follows that

Therefore, we obtain that:

where the last inequality follows from Eq. 22. Combining this with \({\mathcal {A}}\) being \(\textsf {ppt}\), we derive a contradiction to \({\mathcal {E}}\) being \( \textsf {CPA}\) secure. This concludes the proof. \(\square \)

Let \(\pi '=\langle \textsf{Clnt}',\textsf{Srv}\rangle \) be as defined in the proof of Theorem 14, i.e., it is identical to \(\pi =\langle \textsf{Clnt},\textsf{Srv}\rangle \) except that \(\textsf{Clnt}'\), upon receiving server’s queries \(({\textbf{e}},n)\), instead of responding as in step 2 in Definition 9, responds by sending the encryption of \(G_n(m)\) for a uniformly random message m from the domain of \(G_n\). We show that the server is indifferent to the correctness of answers it receives from the client in the sense that its view in \(\pi \) and \(\pi '\) is indistinguishable.

Lemma 5

Let \({\mathcal {E}}= (\textsf{Gen}, \textsf{Enc}, \textsf{Dec})\) be a CPA-secure public-key encryption scheme with a message space \({\mathcal {M}}\). Let \({\mathcal {G}}=\{G_n:{\mathcal {M}}\rightarrow {\mathcal {M}}\}_{n\in {\mathbb {N}}}\) be a family of admissible functions. If \(\pi \) is a cleartext computable \(({\mathcal {E}},{\mathcal {G}})\)-aided outsourcing protocol for \(F:{\textsf{A}}\rightarrow {\textsf{B}}\), then for every efficiently samplable \(x\in {\textsf{A}}\), and all \(\lambda \in {\mathbb {N}}\) the following holds:

Proof

Assume by contradiction that Lemma 5 does not hold. That is, there exists a \(\textsf {ppt}\) distinguisher \({\mathcal {D}}\) that chooses \(x\in {\textsf{A}}\) and a polynomial \(p(\cdot )\) such that for infinitely many \(\lambda \in {\mathbb {N}}\):

We define a series of hybrid executions that gradually move between \(\pi =\langle \textsf{Clnt},\textsf{Srv}\rangle \) execution (where \(\textsf{Clnt}\) responds with \(\textsf{Enc}_{pk}(G_n(\textsf{Dec}_{sk}({\textbf{e}})))\)) to \( \pi '=\langle \textsf{Clnt}',\textsf{Srv}\rangle \) execution (where \(\textsf{Clnt}'\) responds with an encryption of the image of \(G_n\) on a random message). Let q denote the number of queries made to \(\textsf{Clnt}\) in \(\pi \). We define \(q+1\) hybrids as follows:

Hybrid \( {{{\textbf {{\textsf {H}}}}}}_0 \):

is defined as the execution of \(\langle \textsf{Clnt},\textsf{Srv}\rangle \).

Hybrid \( {{{\textbf {{\textsf {H}}}}}}_j\) (\(j=1,\ldots ,q\)):

is similar to \( {\textsf{H}}_0 \) except that the last j queries to \(\textsf{Clnt}\), each query \(({\textbf{e}},n)\) is answered by sampling a uniformly random m in the domain of \(G_n\) and responding with \(\textsf{Enc}_{pk}(G_n(m))\) (instead of sending \(\textsf{Enc}_{pk}(G_n(\textsf{Dec}_{sk}({\textbf{e}})))\) as in Definition 9, Step 2).

Note that in each pair of adjacent hybrids \( {\textsf{H}}_{j-1}\) and \( {\textsf{H}}_{j}\) for \(j\in [q]\) the difference is that in \( {\textsf{H}}_{j}\) the \((q+1-j)\)’th query is answered using \(G_n(m)\) for a random m instead of \(\textsf{Dec}_{sk}({\textbf{e}})\).

Denote by \(\textsf {view}^{{\textsf{H}}_j}_{\textsf{Srv}}(x,\bot ,\lambda )\) the view of \(\textsf{Srv}\) in the hybrid \({\textsf{H}}_j\).

By the hybrid argument it follows from Eq. 23 that there exists \(j\in [q]\) such that:

We show that Eq. 24 contradicts \({\mathcal {E}}\) being \(\textsf {CPA}\) secure. That is, we construct an adversary \({\mathcal {A}}\) that communicates with the challenger \(\textsf {Chal}\) in the CPA indistinguishability experiment \(\textsf{EXP}^{cpa}_{{\mathcal {A}},{\mathcal {E}}}\) and wins with a non-negligible advantage over half. Concretely, \({\mathcal {A}}\) participates in \(\textsf{EXP}^{cpa}_{{\mathcal {A}},{\mathcal {E}}}\) as follows:

1. 1.

   \({\mathcal {A}}\) computes the client’s cleartext response \(\textsf {clear-res}_\textsf{Srv}(x,r,\lambda ) = (y_1,\dots ,y_q)\) (using the efficiently computable function h from Definition 17).

2. 2.

   Upon receiving pk from \(\textsf {Chal}\), \({\mathcal {A}}\) computes \(\mathbf {c_x}\leftarrow \textsf{Enc}_{pk}(x)\), samples a random tape r for \(\textsf{Srv}\), and executes \(\textsf{Srv}\) with randomness r on \((\mathbf {c_x}, pk)\) while answering each query of \(\textsf{Srv}\) as follows:

   1. (a)

      For the first \(q-j\) queries of \(\textsf{Srv}\), \({\mathcal {A}}\) encrypts under pk the responses \(y_1,\dots , y_{q-j}\) associated with these queries, and sends the resulting ciphertexts to \(\textsf{Srv}\).

   2. (b)

      For the \((q-j+1)\)’th query of \(\textsf{Srv}\), denoted \(({\textbf{e}},n)\), \({\mathcal {A}}\) proceeds as follows:

      1. i.

         \({\mathcal {A}}\) sets \(m_0= y_{q-j+1}\), samples uniformly random \(m_1\) from the domain of \(G_n\), and sends \(m_0\) and \(G_n(m_1)\) to \(\textsf {Chal}\).

      2. ii.

         Upon receiving from \(\textsf {Chal}\) the challenge ciphertext \(c \leftarrow \textsf{Enc}_{pk}(m_b)\) for uniformly random \(b\leftarrow \{0,1\}\), \({\mathcal {A}}\) forwards this ciphertext c to \(\textsf{Srv}\).

   3. (c)

      For the rest of the queries \(({\textbf{e}}',n')\), \({\mathcal {A}}\) samples uniformly random m in the domain of \(G_{n'}\), and sends \(\textsf{Enc}_{pk}(G_{n'}(m))\) to \(\textsf{Srv}\).

3. 3.

   \({\mathcal {A}}\) executes the distinguisher \({\mathcal {D}}\) on the view of \(\textsf{Srv}\) during the execution of Step 2 above, denoted \(\textsf {view}_{\textsf{Srv}}\), and outputs whatever \({\mathcal {D}}\) outputs.

We note that if \(b=0\), then the challenge ciphertext c is the encryption of \(y_{q-j+1}\) and since \(\pi \) is cleartext computable we get that \(\textsf {view}_{\textsf{Srv}}\) is exactly as in \(H_{j-1}\) and otherwise as in \(H_j\). Therefore, we obtain that

—a contradiction to the CPA-security of \({\mathcal {E}}\); this concludes the proof. \(\square \)

In this work we introduce the notion of funcCPAand show it is achievable for HE schemes (unlike CCA2) and sufficient for ensuring privacy against malicious servers for the wide an natural family of client-aided outsourcing protocols (unlike CPA, as we prove). In contrast, against semi-honest adversaries, we prove that CPA-security suffices for ensuring privacy in all cleartext computable client-aided outsourcing protocols.