Multi-key and Multi-input Predicate Encryption from Learning with Errors

Abstract

We put forward two natural generalizations of predicate encryption (PE), dubbed multi-key and multi-input PE. More in details, our contributions are threefold.

• Definitions. We formalize security of multi-key PE and multi-input PE following the standard indistinguishability paradigm, and modeling security both against malicious senders (i.e., corruption of encryption keys) and malicious receivers (i.e., collusions).

• Constructions. We construct adaptively secure multi-key and multi-input PE supporting the conjunction of poly-many arbitrary single-input predicates, assuming the sub-exponential hardness of the learning with errors (LWE) problem.

• Applications. We show that multi-key and multi-input PE for expressive enough predicates suffices for interesting cryptographic applications, including non-interactive multi-party computation (NI-MPC) and matchmaking encryption (ME).

In particular, plugging in our constructions of multi-key and multi-input PE, under the sub-exponential LWE assumption, we obtain the first ME supporting arbitrary policies with unbounded collusions, as well as robust (resp. non-robust) NI-MPC for so-called all-or-nothing functions satisfying a non-trivial notion of reusability and supporting a constant (resp. polynomial) number of parties. Prior to our work, both of these applications required much heavier tools such as indistinguishability obfuscation or compact functional encryption.

1 Introduction

Predicate encryption (PE) [17, 30, 37] is a powerful cryptographic primitive that enriches standard encryption with fine-grained access control to the encrypted data. In PE, the ciphertext is associated to both a message m and an attribute¹ x, whereas the secret key is associated to a predicate $\mathbb {P}$, in such a way that the decryption process reveals the message if and only if the attribute x satisfies the predicate $\mathbb {P}$ (i.e., $\mathbb {P}(x) = 1$). Typically, security of PE requires indistinguishability in the presence of collusion attacks, namely, for any pair of attributes $(x^0,x^1)$ and for any pair of messages $(m^0,m^1)$, ciphertexts corresponding to $(x^0,m^0)$ and to $(x^1,m^1)$ are computationally indistinguishable, even for an adversary possessing poly-many decryption keys $\textsf{dk}_{\mathbb {P}}$, so long as $\mathbb {P}(x^0) = \mathbb {P}(x^1) = 0$ (otherwise it is easy to distinguish).

Recently, there has been a lot of progress in constructing PE supporting expressive predicates under standard assumptions [5, 12, 17, 30, 37, 38, 42, 43, 45, 46]. In particular, Gourbunov, Vaikuntanathan and Wee [30] give a construction of selectively secure PE (with unbounded collusions) for arbitrary predicates under the learning with errors (LWE) assumption. Moreover, under sub-exponential LWE, the same construction achieves adaptive security (this requires complexity leveraging).

1.1 Our Contributions

In this paper, we put forward two natural generalizations of PE which we dub multi-key PE and multi-input PE. Furthermore, we construct both multi-key PE and multi-input PE for a particular class of predicates, under the LWE assumption. As we show, the class of predicates our schemes can handle is powerful enough to yield interesting cryptographic applications, including matchmaking encryption (ME) [10, 11] for arbitrary policies and non-interactive multi-party computation (NI-MPC) [34] satisfying a weaker (but still non-trivial) notion of reusability. We elaborate on these contributions in Sect. 1.3.

Prior to our work, all of the above applications required much stronger tools such as indistinguishability obfuscation (iO) [13]. While recent work made significant progress towards basing iO on standard assumptions [35, 36], these constructions are fairly complex and still require a careful combination of multiple assumptions (i.e., learning parity with noise, the SXDH assumption on bilinear groups, and the existence of pseudorandom generators computable in constant depth). Furthermore, such constructions are not secure in the presence of a quantum attacker. Candidate constructions of post-quantum iO also exist [18, 28, 47], but they are based on problems whose hardness is less understood.

Multi-key PE. In multi-key PE, we consider an ensemble of predicates $\mathcal {P}= \{\mathbb {P}_v\}$ indexed by a value $v\in \mathcal {V}$ which is uniquely represented as a sequence $v = (v_1,\ldots ,v_{n}) \in \mathcal {V}_1\times \ldots \times \mathcal {V}_{n}$. A sender can encrypt a message under an input $x$ using the public-key encryption algorithm $\textsf{Enc}(\textsf{mpk},x,m)$. A trusted authority generates decryption keys $\textsf{dk}_{v_{i}}$ (using the corresponding master secret key $\textsf{msk}_i$) for each $i \in [n]$, with the guarantee that, given the decryption keys $\textsf{dk}_{v_{1}},\ldots ,\textsf{dk}_{v_{n}}$, the receiver can decrypt successfully the ciphertext c (associated to plaintext m and attributes x), so long as $\mathbb {P}_v(x) =\mathbb {P}_{v_1,\ldots ,v_{n}}(x) = 1$.

Security of multi-key PE says that, for any pair of attributes $(x^0,x^1)$ and for any pair of messages $(m^0,m^1)$, ciphertexts c associated to $(x^0,m^0)$ and $(x^1,m^1)$ should be computationally indistinguishable even under unbounded collusions, where the latter essentially means that the adversary can obtain decryption keys for (poly-many) arbitrary values $v_1,\ldots ,v_{n}$ which correspond to predicates indexed by any value $v=(v_1,\ldots ,v_{n})$ such that $\mathbb {P}_{v}(x^0) = \mathbb {P}_{v}(x^1)=0$. This yields so-called CPA-1-sided security. The stronger notion of CPA-2-sided security additionally allows for predicates indexed by values v such that $\mathbb {P}_v(x^0) = \mathbb {P}_v(x^1) = 1$, so long as $m^0 = m^1$. These notions mimic the corresponding notions that are already established for standard PE.

Our first result is a construction of multi-key PE, from the sub-exponential LWE assumption, supporting conjunctions of arbitrary predicates, i.e. for predicates of the form $\mathbb {P}_v(x) = \mathbb {P}_{v_1}(x_1) \wedge \ldots \wedge \mathbb {P}_{v_{n}}(x_{n})$, where $x = (x_1,\ldots ,x_{n})$ and $v = (v_1,\ldots ,v_{n})$.

Theorem 1

(Informal). Assuming the sub-exponential hardness of LWE, there exists a CPA-1-sided adaptively secure multi-key PE scheme supporting conjunctions of $n = \textsf{poly}(\lambda )$ arbitrary predicates with unbounded collusions.

Multi-input PE. In multi-input PE, we consider predicates $\mathbb {P}$ with n inputs, i.e. predicates of the form $\mathbb {P}(x_1,\ldots ,x_{n})$. A trusted authority produces encryption keys $\textsf{ek}_i$ which are associated to the i-th slot of an input for $\mathbb {P}$; namely, given a (possibly secret)² encryption key $\textsf{ek}_i$, a sender can generate a ciphertext $c_i$ which is an encryption of message $m_i$ under attribute $x_i$. At the same time, the authority can produce a decryption key $\textsf{dk}_\mathbb {P}$ associated to an n-input predicate $\mathbb {P}$, with the guarantee that the receiver can successfully decrypt $c_1,\ldots ,c_{n}$, and thus obtain $m_1,\ldots ,m_{n}$, so long as $\mathbb {P}(x_1,\ldots ,x_{n})=1$.

As for security, we consider similar flavors as CPA-1-sided and CPA-2-sided security for standard PE. Namely, for any pair of sequences of attributes $(x_1^0,\ldots ,x_{n}^0)$ and $(x_1^1,\ldots ,x_{n}^1)$ and for any pair of sequences of messages $(m_1^0,\ldots ,m_{n}^0)$ and $(m_1^1,\ldots ,m_{n}^1)$, ciphertexts $c_1,\ldots ,c_{n}$ corresponding to either $(x_1^0,m_1^0),\ldots ,(x_{n}^0,m_{n}^0)$ or $(x_1^1,m_1^1),\ldots ,(x_{n}^1,m_{n}^1)$ should be computationally indistinguishable. Here, we additionally consider two cases:

• In the setting with no corruptions (a.k.a. the secret-key setting), all of the encryption keys $\textsf{ek}_i$ are secret and cannot be corrupted (and thus all the senders are honest).

• In the setting with adaptive corruptions, the attacker can adaptively reveal some of the encryption keys $\textsf{ek}_i$ (and thus corrupt a subset of the senders).

Naturally, for both of these flavors, one can define CPA-1-sided and CPA-2-sided security with or without collusions.

Our second result is a construction of multi-input PE, from the sub-exponential LWE assumption, supporting conjunctions of $n=\textsf{poly}(\lambda )$ arbitrary predicates with wildcards, i.e. for predicates of the form $\mathbb {P}(x_1,\ldots ,x_{n}) = \mathbb {P}_1(x_1) \wedge \ldots \wedge \mathbb {P}_{n}(x_{n})$ such that, for each $i \in [n]$, there exists a (public) wildcard input $x^\star _i$ for which $\mathbb {P}_i(x^\star _i)=1$ for every i-th predicate $\mathbb {P}_i$.³ Our multi-input PE construction retains its security only in the setting of no corruptions (i.e., the encryption keys $\textsf{ek}_i$ are kept secret) and no collusions (i.e., the adversary only knows a single decryption key $\textsf{dk}_\mathbb {P}$ for an adversarially chosen predicate $\mathbb {P}$).

Theorem 2

(Informal). Assuming the sub-exponential hardness of LWE, there exists a CPA-1-sided adaptively secure multi-input PE scheme supporting conjunctions of $n = \textsf{poly}(\lambda )$ arbitrary predicates with wildcards, without corruptions and without collusions.

Our third result is a construction of multi-input PE, from the sub-exponential LWE assumption, supporting the same class of predicates as above but tolerating adaptive corruptions of up to $n-1$ parties. However, this particular scheme only supports predicates with constant arity.

Theorem 3

(Informal). Assuming the sub-exponential hardness of LWE, there exists a CPA-1-sided adaptively secure multi-input PE scheme supporting conjunctions of $n = O(1)$ arbitrary predicates with wildcards, under $n-1$ adaptive corruptions and without collusions.

Finally, we anticipate that all our constructions are transformations that leverage single-input PE schemes (e.g., [30]) and lockable obfuscation [31, 48] as building blocks. Such transformations are general and achieve CPA-2-sided security if the underlying single-input PE schemes are CPA-2-sided secure. In particular, we obtain (i) CPA-2-sided secure multi-key PE with unbounded collusions for $n=\textsf{poly}(\lambda )$, (ii) CPA-2-sided secure multi-input PE without corruptions and without collusions for $n = O(\log (\lambda )),$⁴ and (iii) CPA-2-sided secure multi-input PE under $n-1$ corruptions and without collusions for $n = O(1)$. However, at the time of this writing, the LWE assumption is not sufficient for CPA-2-sided security. Indeed, even for single-input PE for arbitrary predicates, CPA-2-sided security implies iO [15]. The current state-of-the-art constructions of iO require much stronger assumptions compared to standard LWE.

1.2 Technical Overview

We now give a high level overview of our constructions. As explained above, both our multi-key and multi-input PE constructions handle conjunctions of arbitrary predicates, i.e., predicates of the form:

$$\begin{aligned} \mathbb {P}(x_1,\ldots ,x_{n}) = \mathbb {P}_1(x_1) \wedge \ldots \wedge \mathbb {P}_{n}(x_{n}). \end{aligned}$$

(1)

We start by explaining how to build multi-key PE for the above class of predicates by combining single-input PE and so-called lockable obfuscation [31, 48]. Informally, a lockable obfuscation scheme allows to obfuscate a circuit $\mathbb {C}$ under a lock y together with a message m, in such a way that evaluating the obfuscated circuit, on input x, returns m if $\mathbb {C}(x) = y$. As for security, an obfuscated circuit can be simulated in a virtual black-box (VBB) fashion whenever the lock is random and unknown to the adversary. Lockable obfuscation exists under the standard LWE assumption.

Then, we explain how to build multi-input PE (for the same class of predicates) by additionally using SKE and PKE. Here, we consider two settings: without corruptions (a.k.a. the secret-key setting) and with corruptions. The former assumes that all the encryption keys (each corresponding to an input) are secret. The latter is a stronger model that allows the adversary to leak one or more encryption keys (i.e., corruption of the senders). We achieve security in each setting by changing the way lockable obfuscation is used. In particular, part of the contribution of this paper is a new technique based on nested (lockable obfuscated) circuits that execute each other. This technique allows us to construct a multi-input PE that can handle adaptive corruptions. We provide a high-level overview in the remaining part of this section. For more details, we refer the reader to Sect. 4, Sect. 5, and the full version of this work [25].

Multi-key Predicate Encryption. An n-key PE allows a sender to encrypt a message $m$ under an attribute $x$, by running . Similarly to single-input PE, a receiver can correctly decrypt $c$ if it has a decryption key for a predicate $\mathbb {P}_v$, within a family $\mathcal {P}$ of predicates indexed by values $v\in \mathcal {V}$, such that $\mathbb {P}_v(x) = 1$. The main difference between single-input PE and n-key PE is that in the latter the receiver must have n independent decryption keys $(\textsf{dk}_{v_1},\ldots , \textsf{dk}_{v_{n}})$ that uniquely represent the predicate $\mathbb {P}_{v}(\cdot ) = \mathbb {P}_{v_1,\ldots ,v_{n}}(\cdot )$, i.e., the decryption key associated to a particular predicate is decomposed into n decryption keys. Each decryption key $\textsf{dk}_{v_i}$ is generated by the authority via $\textsf{KGen}(\textsf{msk}_i,v_i)$ where $(\textsf{msk}_1,\ldots ,\textsf{msk}_{n})$ are the master secret keys generated during the setup. Hence, once obtained $(\textsf{dk}_{v_1},\ldots , \textsf{dk}_{v_{n}})$ from the authority, the receiver can decrypt the ciphertext $c$ (encrypted under attribute $x$) by executing $\textsf{Dec}(\textsf{dk}_{v_1},\ldots ,\textsf{dk}_{v_{n}}, c)$. The message is returned if the predicate $\mathbb {P}_{v_1,\ldots ,v_{n}}(x) = 1$, where $\mathbb {P}_{v_1,\ldots ,v_{n}}(\cdot )$ is the predicate represented by the combination of the n decryptions keys $\textsf{dk}_{v_1},\ldots ,\textsf{dk}_{v_{n}}$. The security of n-key PE is analogous to that of single-input PE, where the validity of the adversary $\textsf{A}$ is defined with respect to the (poly-many) tuples $(\textsf{dk}_{v_1},\ldots ,\textsf{dk}_{v_n})$ of n decryption keys that the adversary has access to. In particular, we consider the well-known notion of CPA-1-sided security, i.e., the attacker cannot distinguish between $\textsf{Enc}(\textsf{mpk},x^0,m^0)$ and $\textsf{Enc}(\textsf{mpk},x^1,m^1)$ so long as it only holds combinations of n decryption keys $(\textsf{dk}_{v_1},\ldots ,\textsf{dk}_{v_n})$ such that $\mathbb {P}_{v_1,\ldots ,v_{n}}(x^0) = \mathbb {P}_{v_1,\ldots ,v_{n}}(x^1) = 0$ (i.e., the adversary cannot decrypt the challenge ciphertext).⁵

As explained above, we focus on conjunctions of arbitrary predicates $\mathbb {P}_{v_1,\ldots ,v_{n}}(x) = \mathbb {P}_{v_1,\ldots ,v_{n}}(x_1,\ldots ,x_{n}) = \mathbb {P}_{v_{1}}(x_1) \wedge \cdots \wedge \mathbb {P}_{v_{n}}(x_{n})$ as defined in Eq. (1); hence, $x=(x_1,\ldots ,x_n)$ and each $\textsf{dk}_{v_i}$ identifies the i-th predicate of the conjunction (and, in turn, any tuple of n decryption keys uniquely identifies the global predicate). We build an n-key PE handling this class of predicates by extending the technique of Goyal et al. [31], that uses lockable obfuscation to transform any CPA secure attribute-based encryption (ABE) (recall that ABE schemes only guarantee the secrecy of the message) into a CPA-1-sided secure PE (i.e., secrecy of both message and attribute). Let $\textsf{PE}_i = (\textsf{Setup}_i,\textsf{KGen}_i,\textsf{Enc}_i,\textsf{Dec}_i)$ for $i\in [n]$ be n single-input PE schemes, each with ciphertext expansion $\textsf{poly}(\lambda )+ |m_i|$ where $|m_i|$ is the message length supported by the i-th PE.⁶ In a nutshell, our n-key PE scheme $\textsf{kPE}= (\textsf{Setup},\textsf{KGen},\textsf{Enc},\textsf{Dec})$ works as follows. The setup algorithm $\textsf{Setup}$ simply executes $\textsf{Setup}_i$ of each $\textsf{PE}_i$ and outputs the master public key $\textsf{mpk} =(\textsf{mpk}_1,\ldots ,\textsf{mpk}_{n})$ and n master secret keys $(\textsf{msk}_1,\ldots ,\textsf{msk}_{n})$. To generate a decryption key (representing the i-th predicate $\mathbb {P}_{v_i}(\cdot )$ of the conjunction), the authority can use the key generation algorithm of the i-th PE, i.e., . To encrypt a message $m$ under an input $x= (x_1,\ldots ,x_{n})$, a sender samples a random lock y and encrypts it n times using $\textsf{PE}_1,\ldots ,\textsf{PE}_{n}$, i.e., . Note that, for $n =\textsf{poly}(\lambda )$, the final ciphertext will be of polynomial size since each underlying i-th PE scheme has $\textsf{poly}(\lambda )+ |m_i|$ ciphertext expansion where $|m_i|$ is the message length supported by i-th scheme.

The final ciphertext of the n-key PE $\textsf{kPE}$ will be the obfuscation of the circuit $\mathbb {C}_{c}$ under the lock y together with the message $m$ (i.e., ), where $\mathbb {C}_{c}$, on input $(\textsf{dk}_{v_1},\ldots ,\textsf{dk}_{v_{n}})$, iteratively decrypts $c$ and returns the last decrypted value, i.e., $y = \mathbb {C}_c(\textsf{dk}_{v_1},\ldots ,\textsf{dk}_{v_{n}}) = \textsf{Dec}_{1}(\textsf{dk}_{v_1},\cdots ,\textsf{Dec}_{n}(\textsf{dk}_{v_{n}},c))$. Decryption is straightforward: the receiver simply executes $\widetilde{\mathbb {C}}$ using its n decryption keys.

The CPA-1-sided security of our construction follows by the CPA security (i.e., secrecy of the message) of $\textsf{PE}_1,\ldots ,\textsf{PE}_{n}$ and by the security of lockable obfuscation.⁷ Intuitively, the proof works as follows. In order to be valid, an adversary $\textsf{A}$ cannot hold a tuple of decryption keys $(\textsf{dk}_{v_1}, \ldots , \textsf{dk}_{v_{n}})$ such that $\mathbb {P}_{v_1,\ldots ,v_{n}}(x^b) = \mathbb {P}_{v_1,\ldots ,v_{n}}(x^b_1,\ldots ,x^b_{n})=1$, where $x^b = (x^b_1,\ldots ,x^b_{n})$ is the input chosen by $\textsf{A}$ during the challenge phase, and b is the challenge bit. Since $\mathbb {P}_{v_1,\ldots ,v_{n}}(x^b_1,\ldots ,x^b_{n})$ is a conjunction of arbitrary predicates (see Eq. (1)), this implies that there exists an $i \in [n]$ such that $\mathbb {P}_{v_i}(x^b_i) = 0$ for every i-th decryption key $\textsf{dk}_{v_i}$ obtained by $\textsf{A}$. We can leverage this observation together with the CPA security of $\textsf{PE}_i$ to do a first hybrid in which the challenger computes the i-th layer of the challenge ciphertext as $\textsf{Enc}_{i}(\textsf{mpk}_i,x^b_i,0\ldots 0)$. Now, since the lock y is not encrypted anymore, we can use the security of lockable obfuscation to do a second hybrid in which the challenge ciphertext $\widetilde{\mathbb {C}}$ is simulated by using the simulator of lockable obfuscation. In this last hybrid, the challenge ciphertext does not depend on the bit b sampled by the challenger.

Despite we focused the discussion on CPA-1-sided security, we stress that the same construction achieves CPA-2-sided security if the underlying n single-input PE schemes $\textsf{PE}_1,\ldots ,\textsf{PE}_{n}$ are CPA-2-sided secure, i.e., $\textsf{Enc}(\textsf{mpk},x^0,m^0)$ and $\textsf{Enc}(\textsf{mpk},x^1,m^1)$ are indistinguishable even when $\mathbb {P}_{v_1,\ldots ,v_{n}}(x^0) = \mathbb {P}_{v_1,\ldots ,v_{n}}(x^1)=1$ and $m^0 = m^1$.

Multi-input Predicate Encryption. We now turn to the more challenging setting of multi-input PE.⁸ Here, each of the n senders can use its corresponding encryption key to independently encrypt messages under different inputs for the predicate. For this reason, the setup algorithm of n-input PE outputs n encryption keys $(\textsf{ek}_1,\ldots ,\textsf{ek}_{n})$ and a master secret key $\textsf{msk}$. Each encryption key $\textsf{ek}_i$ is given to the i-th sender and allows the latter to handle the i-th slot of a multi-input predicate. The i-th party encrypts a message $m_i$ under an input $x_i$ by using its encryption key $\textsf{ek}_i$, i.e., . On the other hand, a receiver can use the decryption key $\textsf{dk}_\mathbb {P}$ associated to an n-input predicate $\mathbb {P}$ (recall that $\textsf{dk}_\mathbb {P}$ is generated by the authority via $\textsf{KGen}(\textsf{msk},\mathbb {P})$) to execute $\textsf{Dec}(\textsf{dk}_\mathbb {P},c_1,\ldots ,c_{n})$. Intuitively, the decryption algorithm returns $(m_1,\ldots ,m_{n})$ when $\mathbb {P}(x_1,\ldots ,x_{n}) = 1$ where $(m_i,x_i)$ are the message and the input associated to the i-th ciphertext $c_i$.

The CPA-1-sided security of n-input PE is similar to that of n-key PE, but adapted to the multi-input setting. Informally, an adversary $\textsf{A}$ must not be able to distinguish between ciphertexts $(\textsf{Enc}(\textsf{ek}_i,x^0_i,m^0_i))_{i\in [n]}$ and $(\textsf{Enc}(\textsf{ek}_i,x^{1}_i,m^{1}_i))_{i\in [n]}$ where $(x^0_{1},\ldots ,x^0_{n})$, $(x^1_{1},\ldots ,x^1_{n})$ and $(m^0_1,\ldots ,m^0_{n})$, $(m^1_1,\ldots , m^1_{n})$ are chosen by $\textsf{A}$. Naturally, this is subject to the usual validity condition, informally saying that $\textsf{A}$ should not be able to decrypt (part of) the challenge ciphertext. This condition can assume different meanings depending on whether the encryption keys are all secret or some of them are public (or can be leaked). Because of this, we formalize security with and without corruptions. Throughout the rest of this section, we describe how CPA-1-sided security of n-input PE changes in these two settings, and give some intuition on our constructions for each setting.

Security in the Secret-Key Setting. Here, no corruptions are allowed and thus the encryption keys are all secrets. Hence, an adversary $\textsf{A}$ playing the CPA-1-sided security game has adaptive oracle access to both the key generation oracle $\textsf{KGen}(\textsf{msk},\cdot )$ and to n encryption oracles $\{\textsf{Enc}(\textsf{ek}_i,\cdot ,\cdot )\}_{i \in [n]}$. The latter oracles allow $\textsf{A}$ to generate ciphertexts (associated to the i-th input/sender) on adversarially chosen predicate inputs and messages. Since these ciphertexts are created independently, the adversary has the power to interleave part of the challenge ciphertext $(c^*_1,\ldots ,c^*_{n})$ with the ciphertexts obtained trough the encryption oracles. This has a huge impact on the security of the a n-input PE scheme and on the validity condition that $\textsf{A}$ must satisfy. For example, during the challenge phase, $\textsf{A}$ could choose two vectors of messages $(m^0_1,\ldots ,m^0_{n})$ and $(m^1_1,\ldots ,m^1_{n})$ and two vectors of predicate inputs $(x^0_{1},\ldots ,x^0_{n})$ and $(x^1_{1},\ldots ,x^1_{n})$ such that for every predicate $\mathbb {P}$ (submitted to oracle $\textsf{KGen}(m,\cdot )$) we have $\mathbb {P}(x^0_{1},\ldots ,x^0_{n}) = \mathbb {P}(x^1_{1},\ldots ,x^1_{n})=0$. Although the vector $(c^*_1,\ldots ,c^*_{n})$ can not be directly decrypted, $\textsf{A}$ could still be able to decrypt part of it by leveraging the encryption oracles. In more details, $\textsf{A}$ could: (i) adversarially choose $x'_i$ such that $\mathbb {P}(x^0_1,\ldots ,x'_i,\ldots x^0_{n}) = 1$ and $\mathbb {P}(x^1_1,\ldots ,x'_i, \ldots x^1_{n}) = 0$; (ii) submit $(x'_i,m'_i)$ to oracle $\textsf{Enc}(\textsf{ek}_i,\cdot ,\cdot )$ and obtain $c'_i$;and (iii) simply decrypt the vector $(c^*_1,\ldots ,c'_i,\ldots ,c^*_{n})$. When $b=0$ (resp. $b=1$), the adversary knows that the challenge ciphertext must (resp. must not) decrypt successfully. This allows it to easily win the CPA-1-sided security experiment of n-input PE. As a consequence, the condition defining when $\textsf{A}$ is valid depends on both the queries submitted to $\textsf{KGen}(\textsf{msk},\cdot )$ and to the oracles $\{\textsf{Enc}(\textsf{ek}_i,\cdot ,\cdot )\}_{i \in [n]}$. More precisely, for every decryption key $\textsf{dk}_\mathbb {P}$ corresponding to a predicate $\mathbb {P}$, for every vector of ciphertexts obtained by interleaving the challenge ciphertext $(c^*_1,\ldots ,c^*_{n})$ with the ciphertexts generated trough any of the n encryption oracles, we must have that $\mathbb {P}$ is not satisfied. This is formalized by the following condition: $\forall \mathbb {P}\in \mathcal {Q}_{\textsf{KGen}}$, $\forall j \in [n]$, $\forall i_1 \in [k_1+1], \ldots , \forall i_n \in [k_n+1]$, it holds that

$$\begin{aligned}&\mathbb {P}(x^{(i_1,0)}_1,\ldots ,x^{(i_{j-1},0)}_{j-1},x^{0}_j,x^{(i_{j+1},0)}_{j+1},\ldots ,x^{(i_n,0)}_{n}) = \nonumber \\&\mathbb {P}(x^{(i_1,1)}_1,\ldots ,x^{(i_{j-1},1)}_{j-1},x^{1}_j,x^{(i_{j+1},1)}_{j+1},\ldots ,x^{(i_n,1)}_{n})= 0, \end{aligned}$$

(2)

where $\mathcal {Q}_{\textsf{KGen}}$ are the queries submitted to oracle $\textsf{KGen}(\textsf{msk},\cdot )$, $(x^0_{1},\ldots ,x^{0}_{n}), (x^1_{1},\ldots ,x^{1}_{n})$ are the predicate inputs chosen by $\textsf{A}$ during the challenge phase, and $\mathcal {Q}^b_i = \{x^{(1,b)}_i,\ldots ,x^{(k_i,b)}_i,x^{(k_i+1,b)}_i = x^b_i\}$ is the ordered list composed of the $k_i$ predicate inputs submitted to oracle $\textsf{Enc}(\textsf{ek}_i,\cdot ,\cdot )$ and the challenge input $x^b_i$ for $b \in \{0,1\}, i \in [n]$ (observe that $\mathcal {Q}^0_i$ and $\mathcal {Q}^1_i$ are identical except for the last element). The formal security definition appears in Sect. 4.

Construction in the Secret-Key Setting. We propose a construction of n-input PE for conjunctions of arbitrary predicates (see Eq. (1)) with wildcards from single-input PE, lockable obfuscation, and SKE. In particular, we start from single-input PE for arbitrary predicates. Actually, it will suffice that the underlying PE itself supports the predicates $\mathbb {P}(x_1,\ldots ,x_{n})$ as defined in Eq. (1), where we view $(x_1,\ldots ,x_{n})$ as a single input chosen by the sender. In addition, the predicate must have a (efficiently computable) wildcard input $(x^\star _1,\ldots ,x^\star _{n})$ such that $x^\star _i$ satisfies every i-th predicate of the conjunction, i.e., $\mathbb {P}_i(x^\star _i)=1$. As we will describe next, the $n-1$ subset of wildcards $(x^\star _1,\ldots ,x^\star _{i-1},x^\star _{i+1},\ldots ,x^\star _{n})$ will permit the i-th sender to put a “don’t care” placeholder on the slots of the other senders. This will allow the construction to deal with multiple inputs without compromising the evaluation of the predicate.

The main intuition behind our construction is to evaluate the conjunction of the predicates inside lockable obfuscation in such a way that, as soon as one of the predicates (of the conjunction) is not satisfied, both the messages and the predicate inputs remain hidden (even if another predicate $\mathbb {P}_i$ is satisfied). To accomplish that, we need to create a link between the independently generated ciphertexts (each produced by different senders). This is done by leveraging an SKE scheme as follows.

In a nutshell, the i-th secret encryption key has the form $\textsf{ek}_i = (\textsf{mpk},\textsf{k}_i,\textsf{k}_{i+1})$ where $\textsf{mpk}$ is the master public key of the single-input PE, and $\textsf{k}_i$ for $i \in [n]$ is a secret key for the SKE (we also let $\textsf{ek}_{n+1} = \textsf{k}_1$). In order to encrypt a message $m_i$ under an input $x_i$, the i-th sender samples a random lock $y_i$ and encrypts $(y_i,\textsf{k}_{i+1})$ via the single-input PE, using the input made by all the wildcards $x^\star _{j}$ except for the position $j=i$, where, instead, the sender places its real input $x_i$, i.e., . The final ciphertext $c_i$ will be $c_i=(\widetilde{\mathbb {C}}_i,c^{(2)}_i)$, where and $\widetilde{\mathbb {C}}_i$ is the obfuscation of the circuit $\mathbb {C}_{c^{(2)}_i,\textsf{k}_{i+1}}$ under the lock $y_i$ and message $m_i$. Similarly to the case of multi-key PE, the latter circuit is responsible for the decryption. In particular, upon input the ciphertexts $(c^{(2)}_{i+1},\ldots , c^{(2)}_{n},c^{(2)}_1,\ldots ,c^{(2)}_{i-1})$—note the order of the ciphertexts—and the decryption key $\textsf{dk}_\mathbb {P}$ for $\mathbb {P}(x_1,\ldots ,x_{n})$, the circuit $\mathbb {C}_{c^{(2)}_i,\textsf{k}_{i+1}}$ acts as follows:

• 1. Set $\textsf{k} = \textsf{k}_{i+1}$ where $\textsf{k}_{i+1}$ is the secret key hardcoded into the circuit.

• 2. For $c^{(2)}_j \in \{c^{(2)}_{i+1},\ldots , c^{(2)}_{n},c^{(2)}_1,\ldots ,c^{(2)}_{i-1}\}$ do:

  • (a) Decrypt $c^{(2)}_{j}$ using the secret key $\textsf{k}$, i.e., $c^{(1)}_{j} = \textsf{Dec}(\textsf{k}, c^{(2)}_{j})$.

  • (b) Decrypt $c^{(1)}_{j}$ using $\textsf{dk}_{\mathbb {P}}$ in order to get $(y_j,\textsf{k}_{j+1})$. If $c^{(1)}_{j}$ decrypts correctly, $\textsf{k}_{j+1}$ is the secret key used to encrypt the next ciphertext $c^{(2)}_{j+1}$.

  • (c) Set $\textsf{k} = \textsf{k}_{j+1}$.

• 3. Compute $(y_i,\textsf{k}_{i+1}) = \textsf{Dec}(\textsf{dk}_\mathbb {P},\textsf{Dec}(\textsf{k}, c^{(2)}_{i}))$, where $c^{(2)}_i$ is the ciphertext hardcoded into the circuit.

• 4. Return $y_i$ (note that if none of the decryptions fails then $y_i$ is the lock used to obfuscate the circuit).

By the above description, decryption is immediate: Upon input $(c_i)_{i \in [n]}$, the receiver computes $m_i = \widetilde{\mathbb {C}}_i(c^{(2)}_{i+1},\ldots , c^{(2)}_{n},c^{(2)}_1,\ldots ,c^{(2)}_{i-1},\textsf{dk}_\mathbb {P})$ where $c_i = (\widetilde{\mathbb {C}}_i, c^{(2)}_i)$ and $\textsf{dk}_\mathbb {P}$ is the decryption key of the underlying single-input PE for a predicate $\mathbb {P}(x_1,\ldots ,x_{n})$. We highlight that the combination of the SKE with the PE wildcards is what allows our construction to correctly implement the predicates of Eq. (1). This is because, when $c^{(1)}_{i}$ correctly decrypts under the key $\textsf{dk}_\mathbb {P}$ (Item 2b), we are guaranteed that $\mathbb {P}_i(x_i) = 1$ (recall that $x_i$ is the input of the i-th sender). In particular, the latter holds as, in any other slot, the i-th sender has used the wildcards. By repeating this argument, we can conclude that $\mathbb {P}(x_1,\ldots ,x_{n}) = \mathbb {P}_1(x_1) \wedge \ldots \wedge \mathbb {P}_{n}(x_{n})$ is satisfied if the execution of each $\mathbb {C}_{c^{(2)}_i,\textsf{k}_{i+1}}$ goes as expected. We refer the reader to the full version [25] for the formal construction.

As for security, we show that our construction satisfies CPA-1-sided security in the presence of no collusions (i.e., the adversary can submit a single query to the oracle $\textsf{KGen}$) if the underlying PE is CPA-1-sided secure, SKE is CPA secure, and the lockable obfuscation is secure. Roughly, the proof works as follows. Let $\mathbb {P}^*$ be the only predicate submitted to $\textsf{KGen}$ by the adversary. Starting from $\textsf{A}$’s validity condition, we infer that, for any choice of the challenge bit $b \in \{0,1\}$, then attacker $\textsf{A}$ must maintain one of the following two conditions:

• (i) either $\mathbb {P}^*_1(x^b_1) = \ldots = \mathbb {P}^*_{n}(x^b_{n}) = 0$ (i.e., all the predicates of the conjunctions are false);

• (ii) or (if at least one predicate $\mathbb {P}^*_i$ is satisfied, i.e., $\mathbb {P}^*_i(x^b_i)=1$) there exists $j\ne i$ such that, for every $x_j \in \mathcal {Q}^b_j$, it holds that $\mathbb {P}^*_{j}(x_j)=0$ where $\mathcal {Q}^b_j$ is the ordered list composed of predicate inputs submitted to the oracle $\textsf{Enc}(\textsf{ek}_j,\cdot ,\cdot )$ and the challenge input $x^b_j$ (see Eq. (2)).⁹

When the first condition is satisfied, we can leverage the CPA-1-sided security of the single-input PE to show that the every lock $y_i$ (encrypted using the PE), and every input $x_i$ (encrypted in $c^{(2)}_i$), is completely hidden to the adversary. The latter allows us to use the security of lockable obfuscation to move to a hybrid experiment in which all the (obfuscated) circuits are simulated (including the messages).

On the other hand, when the second condition is satisfied, we can transition to a hybrid experiment (this time by leveraging the security of the underlying PE scheme) in which $\textsf{Enc}(\textsf{ek}_j,\cdot ,\cdot )$ computes $c^{(1)}_j$ by encrypting the all-zero string (instead of $(y_j,\textsf{k}_{j+1})$). Thus, we can use the security of lockable obfuscation to move to another hybrid in which $\textsf{Enc}(\textsf{ek}_j,\cdot ,\cdot )$ simulates all the obfuscations. At this point, the symmetric key $\textsf{k}_{j+1}$ is not used anymore. Hence, we can use the security of SKE to transition to another hybrid in which $\textsf{Enc}(\textsf{ek}_{j+1},\cdot ,\cdot )$ computes $c^{(2)}_{j+1}$ by encrypting the all-zero string (instead of $c^{(1)}_{j+1}$ that, in turn, contains the lock $y_{j+1}$ and the symmetric key $\textsf{k}_{j+2}$). After this hybrid, we can again use the security of lockable obfuscation to simulate all the obfuscations computed by $\textsf{Enc}(\textsf{ek}_{j+1},\cdot ,\cdot )$, and so on. By repeating these last two hybrids, we reach an experiment whose distribution does not depend on the challenge bit. The formal construction appears in the full version of this work [25].

We highlight that our scheme is not secure in the presence of collusions. In particular, the fact that the adversary can obtain a single decryption key $\textsf{dk}_\mathbb {P}$ is crucial in order to get the validity condition (ii), i.e., for every $b \in \{0,1\}$ there exists a j such that for every predicate (submitted to $\textsf{KGen}(\textsf{msk},\cdot )$) we have $\mathbb {P}_j(x^b_j) =0$. In fact, in the case of collusions, the adversary can ask for two decryption keys $\textsf{dk}_{\mathbb {P}}$ and $\textsf{dk}_{\mathbb {P}'}$ such that for every $b \in \{0,1\}$:

$$\begin{aligned} \mathbb {P}_1(x^b_1)&= 0 \text { and } \mathbb {P}_{2}(x^{b}_2) = \ldots = \mathbb {P}_{n}(x^{b}_{n}) = 1 \\ \mathbb {P}'_1(x^b_1)&= 1 \text { and } \mathbb {P}'_{2}(x^{b}_2) = \ldots = \mathbb {P}'_{n}(x^{b}_{n}) = 0. \end{aligned}$$

Note that these are valid queries for the CPA-1-sided security experiment of n-input PE (the ciphertext cannot be decrypted). However, such a unique j for every predicate (as per condition (ii)) does not exist. When this happens, we are not able to conclude the proof by making a reduction to the security of single-input PE (the reduction will make an invalid set of queries to the $\textsf{KGen}$ oracle of the single-input PE, making it invalid for the CPA-1-sided security of the single-input PE).¹⁰

Lastly, we stress that since we start from a single-input PE supporting conjunctions of arbitrary predicates with wildcards, we end up with an n-input PE for conjunctions of arbitrary predicates (see Eq. (1)) with wildcards. We highlight that wildcards do not play any role in the security proof of our secret-key construction. In other words, wildcards are required for functionality (correctness) and not for security. Indeed, in the secret-key setting (i.e., no corruptions), wildcards can be easily removed. This is because we can transform any secure multi-input PE for $\mathbb {P}(x_1,\ldots ,x_{n}) = \mathbb {P}_1(x_1) \wedge \ldots \wedge \mathbb {P}_{n}(x_{n})$ with a single wildcard $(x^\star _1,\ldots ,x^\star _{n})$ into a secure multi-input PE for the same class of predicates $\mathbb {P}(x_1,\ldots ,x_{n})$ without the wildcard. This can be done by requiring the senders not to encrypt the corresponding wildcard, i.e., for each $i\in [n]$, $\textsf{Enc}(\textsf{ek}_i,x^\star _i,m_i)$ outputs $\bot$ whenever $x_i = x^\star _i$. We stress that this only works in the case of no corruptions. In fact, as we will discuss later, in case of corruption, wildcards play a role in the security of our corruption-resilient multi-input PE scheme, e.g., an adversary can encrypt wildcards on its own using the leaked encryption keys.

Security Under Corruptions. Next, let us explain how to define security of multi-input PE in the presence of corruptions. Here, the adversary has the possibility to corrupt a subset of the senders and leak their encryption keys $\textsf{ek}_i$. We model this by introducing an additional corruption oracle $\textsf{Corr}(\cdot )$ that, upon input an index $i \in [n]$, returns $\textsf{ek}_i$. Note that, once obtained $\textsf{ek}_i$, the adversary $\textsf{A}$ has the possibility to produce arbitrary ciphertexts on any message and predicate input, without interacting with the challenger during the CPA-1-sided security game. As usual, the validity condition heavily depends on the queries submitted to both the encryption oracles and the corruption oracle. More precisely, the validity condition now says that, for every decryption key $\textsf{dk}_\mathbb {P}$, for every vector of ciphertexts that can be obtained by interleaving the challenge ciphertext $(c^*_1,\ldots ,c^*_{n})$ with both the ciphertexts obtain trough any of the (uncorrupted) encryption oracles and the ones that $\textsf{A}$ may autonomously produce by using the leaked encryption keys (trough oracle $\textsf{Corr}(\cdot )$), we have that $\mathbb {P}$ is not satisfied. Hence, the validity condition is identical to that of the secret-key setting (see Eq. (2)), except that:

• If the i-th encryption key $\textsf{ek}_i$ has been corrupted/leaked, then $\mathcal {Q}^b_i$ of Eq. 2 corresponds to the i-th predicate input space. This is because the adversary can produce a valid ciphertext on any input $x_i$.

• Else (i.e., the i-th encryption key $\textsf{ek}_i$ is still secret), $\mathcal {Q}^b_i$ is defined as usual, i.e., it is the ordered list of predicate inputs submitted to oracle $\textsf{Enc}(\textsf{ek}_i,\cdot ,\cdot )$ and challenge input $x^b_i$.

See Sect. 4 for the formal definition.

A Simple Attack. Before explaining our construction in details, let us show why the previous construction is not secure under corruptions. For simplicity, we focus on the 2-input setting. Suppose an adversary $\textsf{A}$ has a single decryption key $\textsf{dk}_\mathbb {P}$ for $\mathbb {P}(x_1,x_2) = \mathbb {P}_1(x_1)\wedge \mathbb {P}_2(x_2)$ and a vector of ciphertexts $(c^*_1,c^*_2) = ((\widetilde{\mathbb {C}}_1,c^{(2)}_1),(\widetilde{\mathbb {C}}_2,c^{(2)}_2))$ encrypted under the predicate input $(x_1,x_2)$ such that $\mathbb {P}_1(x_1) = 0$ and $\mathbb {P}_2(x_2)=1$. Note that this ciphertext should not decrypt under $\textsf{dk}_\mathbb {P}$, since the conjunction of $\mathbb {P}_1$ and $\mathbb {P}_2$ evaluates to 0. If $\textsf{A}$ can obtain $\textsf{ek}_2$, then it can easily determine the message $m_2$ (and thus the bit b). Indeed, once $\textsf{A}$ gets $\textsf{ek}_2 = (\textsf{mpk},\textsf{k}_2,\textsf{k}_1)$, it can compute a malicious ciphertext $\widetilde{c}^{(1)}_1$ (using the single-input PE) by encrypting $(\widetilde{y}, \textsf{k}_2)$ (where $\widetilde{y}$ is a random lock) under the predicate input composed by $(x'_1,x'_2)$ such that $\mathbb {P}_1(x'_1)=1$ and $\mathbb {P}_2(x'_2) =1$. Then, it can compute and execute $\widetilde{\mathbb {C}}_2(\widetilde{c}^{(2)}_1,\textsf{dk}_\mathbb {P})$ to get $m_2$. Note that by definition the execution of $\widetilde{\mathbb {C}}_2$ outputs the correct message, since $\mathbb {P}_1(x^\star _1) \wedge \mathbb {P}_2(x_2) = 1$ and $\widetilde{c}^{(2)}_1$ contains the correct secret encryption key $\textsf{k}_2$, allowing the circuit to correctly end the computation. Also, note that this attack does not violate the validity condition. This is because $\mathbb {P}_1(x_1) = 0$, and $\textsf{A}$ does not use the oracle $\textsf{Enc}(\textsf{ek}_1,\cdot ,\cdot )$ at all. Hence, any interleaving of the ciphertexts will involve the predicate input $x_1$ that, in turn, will make the conjunction $\mathbb {P}(x_1,x'_2) = \mathbb {P}_1(x_1)\wedge \mathbb {P}_2(x'_2)$ unsatisfied for every choice of the input predicate $x'_2$.

In light of the above attack, we can identify what we need to do in order to extend our techniques to handle corruptions: First, following the proof of the previous construction, it is important to hide the (plain) single-input PE ciphertext that a particular sender produces (e.g., in the secret-key setting we re-encrypt $c^{(1)}_i$ using SKE). As we have described for the secret-key setting, this allows us to claim that everything remains hidden whenever one of the predicate $\mathbb {P}_i$ of the conjunction is not satisfied (even if a different $\mathbb {P}_j$ is satisfied).¹¹ Second, the leakage of one (or more) encryption keys should not allow to produce a malicious ciphertext on behalf of the uncorrupted senders (or simply decrypt the ciphertexts of other parties). Otherwise, the attacker can follow a strategy similar to the one above to break security.

Construction Under Corruptions. In order to achieve the above properties, we propose a new technique based on nested (lockable obfuscated) circuits that can be executed one inside the other. This technique permits to make available secret information (e.g., secret keys) only during nested execution. For the sake of clarity, we first present our approach for the case of two inputs. As an initial attempt to deal with corruptions, we replace the SKE in our previous construction with a PKE, so that the encryption key $\textsf{ek}_1$ (resp. $\textsf{ek}_2$) is now composed of $(\textsf{mpk},\textsf{sk}_1,\textsf{pk}_1,\textsf{pk}_{2})$ (resp. $(\textsf{mpk},\textsf{sk}_2,\textsf{pk}_2,\textsf{pk}_{1})$) where $(\textsf{sk}_i,\textsf{pk}_i)$ is a secret/public key pair. Each $(\textsf{sk}_i,\textsf{pk}_i)$ is associated to the i-th sender (indeed, note that $\textsf{ek}_i$ contains also the secret key $\textsf{sk}_i$). From the perspective of the first sender, in order to encrypt a message $m_1$ under the input $x_1$, it samples two random locks $(y^\textsf{in}_1,y^\textsf{out}_1)$ and encrypts them (using the single-input PE) as before using the wildcard $x^\star _2$, i.e., .¹² At this point, the PE ciphertext $c^{(0)}_{1}$ is re-encrypted twice using $\textsf{pk}_1$ and $\textsf{pk}_2$, i.e., for $i \in [2]$. Intuitively, the two layers of PKE have the role of hiding the PE ciphertexts (that in turn contain the locks) even when the adversary leaks all encryption keys except one. The final ciphertext is composed by the two obfuscations $\widetilde{\mathbb {C}}^\textsf{out}_1$, $\widetilde{\mathbb {C}}^\textsf{in}_1$ of the circuits $\mathbb {C}^{\textsf{out}}_{\textsf{sk}_1,c^{(2)}_1}$, $\mathbb {C}^{\textsf{in}}_{\textsf{sk}_1,c^{(2)}_1}$, respectively. The former is obfuscated under the lock $y^\textsf{out}_1$ and message $m_1$, whereas the latter is obfuscated under the lock $y^{\textsf{in}}_1$ and message $\textsf{sk}_1$. The ciphertext produced by the second sender, is identical, except that it uses $\textsf{sk}_2$ (instead of $\textsf{sk}_1$) and that $c^{(0)}_2$ is computed using the predicate input $(x^\star _1,x_2)$ (instead of $(x_1,x^\star _2)$).

The crux of our nesting technique comes from the definition of the circuits $\mathbb {C}^{\textsf{out}}_{\textsf{sk}_i,c^{(2)}_i}$. More precisely, the outer circuit $\mathbb {C}^{\textsf{out}}_{\textsf{sk}_1,c^{(2)}_1}$ will take as input the obfuscation $\widetilde{\mathbb {C}}^{\textsf{in}}_2$ of the inner circuit $\mathbb {C}^{\textsf{in}}_{\textsf{sk}_{2},c^{(2)}_{2}}$ and a decryption key $\textsf{dk}_\mathbb {P}$. Then, in order to securely check the conjunction inside the lockable obfuscation, $\mathbb {C}^{\textsf{out}}_{\textsf{sk}_1,c^{(2)}_1}$ will execute $\widetilde{\mathbb {C}}^{\textsf{in}}_2(\textsf{sk}_{1},\textsf{dk}_\mathbb {P})$. At this point, $\widetilde{\mathbb {C}}^{\textsf{in}}_2$ has everything it needs to check the satisfiability of $\mathbb {P}_2(\cdot )$. It removes the PKE layers from $c^{(2)}_2$ by computing $c^{(0)}_2 = \textsf{Dec}(\textsf{sk}_2,\textsf{Dec}(\textsf{sk}_1,c^{(2)}_2))$. Then, it decrypts the PE ciphertext $(y^{\textsf{in}}_2,y^{\textsf{out}}_2)=\textsf{Dec}(\textsf{dk}_\mathbb {P},c^{(0)}_2)$—observe that the decryption succeeds if $\mathbb {P}_2(x_2) = 1$—and returns $y^\textsf{in}_2$. By correctness of lockable obfuscation, if the computation of $\mathbb {C}^{\textsf{in}}_{\textsf{sk}_{2},c^{(2)}_{2}}(\textsf{sk}_1,\textsf{dk}_\mathbb {P})$ goes as intended, then $\widetilde{\mathbb {C}}^{\textsf{in}}_2(\textsf{sk}_{1},\textsf{dk}_\mathbb {P})$ will output $\textsf{sk}_2$ (the message attached to the obfuscation). Once obtained $\textsf{sk}_2$, the computation of $\mathbb {C}^{\textsf{out}}_{\textsf{sk}_1,c^{(2)}_1}$ can continue and perform a similar computation to check the satisfiability of $\mathbb {P}_1(\cdot )$ except that, if the PE ciphertext $c^{(0)}_1$ decrypts correctly, it returns $y^{\textsf{out}}_1$. If all the decryptions (performed by $\mathbb {C}^{\textsf{out}}_{\textsf{sk}_1,c^{(2)}_1}$ and $\mathbb {C}^{\textsf{in}}_{\textsf{sk}_2,c^{(2)}_2}$) succeed, the execution of the obfuscation $\widetilde{\mathbb {C}}^{\textsf{out}}_1$ of $\mathbb {C}^{\textsf{out}}_{\textsf{sk}_1,c^{(2)}_1}$ will output $m_1$. A symmetrical argument holds for $\mathbb {C}^{\textsf{out}}_{\textsf{sk}_2,c^{(2)}_2}$ and $\mathbb {C}^{\textsf{in}}_{\textsf{sk}_1,c^{(2)}_1}$, releasing $m_2$.

We show that the above 2-input PE construction is CPA-1-sided secure under 1 corruption (i.e., one encryption key remains secret) and no collusions if the underlying single-input PE is CPA secure, PKE is CPA secure, and the lockable obfuscation is secure. The high level intuition is that $\textsf{sk}_i$ remains unknown to the adversary if $\mathbb {P}_i(\cdot )=0$ (unless the adversary invokes the oracle $\textsf{Corr}(i)$). This is reflected by the proof technique that is sketched below.

Let $\textsf{dk}_{\mathbb {P}^*}$ be the decryption key obtained by $\textsf{A}$ for the predicate $\mathbb {P}^*(\cdot ,\cdot ) = \mathbb {P}^*_1(\cdot ) \wedge \mathbb {P}^*_2(\cdot )$ (recall the presence of wildcards), and let $\mathcal {Q}_\textsf{Corr}$ be the queries submitted to the corruption oracle. Starting from the validity condition, we can infer that for any choice of the challenge bit $b \in \{0,1\}$ we have:

• (i) either $\mathbb {P}^*_1(x^b_1) = \mathbb {P}^*_2(x^b_2) = 0$;

• (ii) or (i.e., there exists an $i \in [2]$ such that predicate $\mathbb {P}_i$ is satisfied) $j \not \in \mathcal {Q}_\textsf{Corr}$ such that $j \ne i$ and, for every $x_{j} \in \mathcal {Q}^b_{j}$, $\mathbb {P}^*_{j}(x_{j}) = 0$ (recall that $x^b_j \in \mathcal {Q}^b_j$). Observe that this second condition holds because of the following:

  • If there is $x_{j} \in \mathcal {Q}^b_{j}$ such that $\mathbb {P}^*_{j}(x_{j}) = 1$, $\textsf{A}$ can use the corresponding ciphertext to decrypt the i-th part of the challenge ciphertext since $\mathbb {P}^*_i(x^b_i) =1$.

  • If $j \in \mathcal {Q}_{\textsf{Corr}}$, $\textsf{A}$ can simply use $\textsf{ek}_{j}$ to encrypt a random message under the wildcard $x^\star _{j}$ (that always exists by design of our construction) and, again, decrypt the i-th part of the challenge ciphertext. Note that, contrarily from our secret-key construction, wildcards play an important role in the security of our multi-input PE construction under corruptions (if an encryption key $\textsf{ek}_j$ gets leaked then a malicious adversary can always encrypt itself the j-th wildcards $x^\star _j$, satisfying the j-th predicate $\mathbb {P}_j$). Hence, in the corruption setting, wildcards are used for both functionality and security.

By leveraging the above two conditions, the security of our scheme follows by using a similar argument to that of the secret-key setting. In particular, when the first condition is satisfied, we can show that the locks $(y^\textsf{in}_1,y^\textsf{out}_1)$ and $(y^\textsf{in}_2,y^\textsf{out}_2)$ (used to encrypt the challenge) are completely hidden. This, in turn, allows us to use the security of lockable obfuscation and simulate the obfuscations of $(\mathbb {C}^{\textsf{out}}_{\textsf{sk}_1,c^{(2)}_1},\mathbb {C}^{\textsf{in}}_{\textsf{sk}_1,c^{(2)}_1})$, $(\mathbb {C}^{\textsf{out}}_{\textsf{sk}_2,c^{(2)}_2}, \mathbb {C}^{\textsf{in}}_{\textsf{sk}_2,c^{(2)}_2})$, and the corresponding messages.

On the other hand, when the second condition is satisfied, we can move to a hybrid (by leveraging the security of single-input PE) in which $\textsf{Enc}(\textsf{ek}_{j},\cdot ,\cdot )$ computes $c^{(0)}_{j}$ by encrypting the all-zero string (instead of $(y^\textsf{in}_{j},y^{\textsf{out}}_{j})$). Then, we can use the security of lockable obfuscation to transition to another hybrid in which $\textsf{Enc}(\textsf{ek}_{j},\cdot ,\cdot )$ simulates all the obfuscations. At this point, the secret key $\textsf{sk}_{j}$ of the uncorrupted j-th sender is not used anymore (recall that $j \not \in \mathcal {Q}_{\textsf{Corr}}$). Hence, we can leverage the security of the PKE to remove the locks $(y^\textsf{in}_i,y^\textsf{out}_i)$ chosen by the i-th sender (recall $i \ne j$). In more details, we do another hybrid in which the j-th PKE layer $c^{(j)}_{i}$ of the challenge ciphertext is an encryption of zeroes (instead of $c^{(j-1)}_{i}$ that, in turn, encrypts the locks $(y^\textsf{in}_i,y^\textsf{out}_i)$). After this hybrid, we can again use the security of lockable obfuscation to simulate all the obfuscations (and the corresponding attached messages) that compose the i-th component of the ciphertext. The distribution of this last hybrid does not depend on the challenge bit b since all the ciphertexts are simulated by the simulator of the lockable obfuscation scheme.

To sum up, we can observe that encrypting $c^{(0)}_i$ (the PE ciphertext that contains the locks) with the public keys $(\textsf{pk}_1$, $\textsf{pk}_2)$ of both senders is crucial in order for our proof to work independently of which encryption key the adversary decides to leak. So long as at least one encryption key $\textsf{ek}_i$ remains hidden, then there is a PKE layer that cannot be decrypted by the adversary. This allows the proof to go through.

Generalizing the Nesting Technique to $(n>2)$ Inputs. By carefully modifying the definition of the outer and inner circuits, we can generalize the above technique to the case of $n>2$. The structure of the encryption keys and of the encryption algorithm is similar to the case $n=2$:

• Each encryption key $\textsf{ek}_i$ is of the form $(\textsf{mpk},\textsf{sk}_i,\textsf{pk}_1,\ldots ,\textsf{pk}_{n})$.

• To compute the i-th encryption of $(x_i,m_i)$, the sender computes the initial PE ciphertext as . Then, it re-encrypts n times the ciphertext $c^{(0)}_i$ using $(\textsf{pk}_1,\ldots ,\textsf{pk}_{n})$, i.e., . As usual, the final ciphertext $c_i = (\widetilde{\mathbb {C}}^\textsf{out}_i,\widetilde{\mathbb {C}}^\textsf{in}_i)$ is composed of the obfuscations of $\mathbb {C}^{\textsf{out}}_{\textsf{sk}_i,c^{(n)}_i}$ and $\mathbb {C}^{\textsf{in}}_{\textsf{sk}_i,c^{(n)}_i}$.

We now turn on the crucial point: the definition of the outer and inner circuits. Again, for the sake of clarity, we only describe the outer circuit $\mathbb {C}^\textsf{out}_{\textsf{sk}_1,c^{(n)}_1}$ and of the inner circuits $(\mathbb {C}^\textsf{in}_{\textsf{sk}_2,c^{(n)}_2},\ldots , \mathbb {C}^\textsf{in}_{\textsf{sk}_{n},c^{(n)}_{n}})$ generated by the corresponding senders. The remaining circuits are defined similarly. First off, the input space of these circuits is a follows:

• $\mathbb {C}^{\textsf{out}}_{\textsf{sk}_1,c^{(n)}_1}$ takes as input the $n-1$ obfuscations of the circuits $(\mathbb {C}^{\textsf{in}}_{\textsf{sk}_{2},c^{(n)}_{2}}, \ldots , \mathbb {C}^{\textsf{in}}_{\textsf{sk}_{n},c^{(n)}_{n}})$ and a decryption $\textsf{dk}_{\mathbb {P}}$. These obfuscations are the inner circuits that needs to be executed in order to return the message $m_1$ attached to the obfuscation of $\mathbb {C}^{\textsf{out}}_{\textsf{sk}_1,c^{(n)}_1}$.

• On the other hand, $\mathbb {C}^{\textsf{in}}_{\textsf{sk}_i,c^{(n)}_i}$, for $i \in [n]\setminus \{1\}$, takes as input a tuple of n secret keys $(\textsf{sk}_{1},\ldots , \textsf{sk}_{n})$ (where some can be set to $\bot$), a decryption key $\textsf{dk}_\mathbb {P}$, and the obfuscations of $(\mathbb {C}^{\textsf{in}}_{\textsf{sk}_{i+1},c^{(n)}_{i+1}}, \ldots , \mathbb {C}^{\textsf{in}}_{\textsf{sk}_{n},c^{(n)}_{n}})$. Intuitively, these obfuscations are the remaining inner circuits that we need to still execute in order to complete the nested execution.

Intuitively, the decryption of $m_1$ requires the nested execution of these circuits (starting from the outer one) in order to get all the secret keys required to decrypt the PE ciphertext. This is achieved as follows.

The outer circuit $\mathbb {C}^{\textsf{out}}_{\textsf{sk}_1,c^{(n)}_1}$ starts the nested execution by invoking the obfuscation of $\mathbb {C}^{\textsf{in}}_{\textsf{sk}_{2},c^{(n)}_{2}}$ upon input $(\textsf{sk}_1,\bot ,\ldots ,\bot )$, $\textsf{dk}_\mathbb {P}$, and the remaining obfuscations of $(\mathbb {C}^{\textsf{in}}_{\textsf{sk}_{3},c^{(n)}_{3}}, \ldots , \mathbb {C}^{\textsf{in}}_{\textsf{sk}_{n},c^{(n)}_{n}})$. In turn, $\mathbb {C}^{\textsf{in}}_{\textsf{sk}_{2},c^{(n)}_{2}}$ will do a similar thing: It executes the next obfuscated circuit $\mathbb {C}^{\textsf{in}}_{\textsf{sk}_{3},c^{(n)}_{3}}$ upon input $(\textsf{sk}_1,\textsf{sk}_2,\bot ,\ldots ,\bot )$, $\textsf{dk}_\mathbb {P}$, and the remaining obfuscations $(\mathbb {C}^{\textsf{in}}_{\textsf{sk}_{4},c^{(n)}_{4}}, \ldots , \mathbb {C}^{\textsf{in}}_{\textsf{sk}_{n},c^{(n)}_{n}})$. This process is repeated until $\mathbb {C}^{\textsf{in}}_{\textsf{sk}_{n},c^{(n)}_{n}}$ is executed upon input $(\textsf{sk}_1,\ldots ,\textsf{sk}_{n-1},\bot )$ and $\textsf{dk}_\mathbb {P}$. At this point, all the secret keys are know (observe that $\textsf{sk}_{n}$ is hardcoded). From $c^{(n)}_{n}$, we can remove the n PKE layers, decrypt the PE ciphertext and, in turn, return $y^{\textsf{in}}_{n}$ if the PE ciphertext decrypts correctly (i.e., $\mathbb {P}_{n}(\cdot )$ is satisfied). Once $\mathbb {C}^{\textsf{in}}_{\textsf{sk}_{n},c^{(n)}_{n}}$ terminates, the secret key $\textsf{sk}_{n}$ is released and $\mathbb {C}^{\textsf{in}}_{\textsf{sk}_{n-1},c^{(n)}_{n-1}}$ performs the computation required to check if $\mathbb {P}_{n-1}(\cdot )$ is satisfied. Indeed, $\mathbb {C}^{\textsf{in}}_{\textsf{sk}_{n-1},c^{(n)}_{n-1}}$ has been executed on input $(\textsf{sk}_1,\ldots ,\textsf{sk}_{n-2},\bot ,\bot )$, it has $\textsf{sk}_{n-1}$ harcoded, and the execution of $\mathbb {C}^{\textsf{in}}_{\textsf{sk}_{n},c^{(n)}_{n}}$ has released $\textsf{sk}_{n}$. Hence, after the correct termination of $\mathbb {C}^{\textsf{in}}_{\textsf{sk}_{n},c^{(n)}_{n}}$, all secret keys are known.

It may seems that this argument can be iterated. However, there is a problem. Even if $\mathbb {C}^{\textsf{in}}_{\textsf{sk}_{n-1},c^{(n)}_{n-1}}$ correctly terminates, the circuit $\mathbb {C}^{\textsf{in}}_{\textsf{sk}_{n-2},c^{(n)}_{n-2}}$ that invokes it does not have access to the secret key $\textsf{sk}_{n}$. This is because the latter circuit receives as input $(\textsf{sk}_{1},\ldots ,\textsf{sk}_{n-3},\bot ,\bot ,\bot )$, it has $\textsf{sk}_{n-2}$ hardcoded, and the circuit $\mathbb {C}^{\textsf{in}}_{\textsf{sk}_{n-1},c^{(n)}_{n}}$ has returned $\textsf{sk}_{n-1}$. As a consequence, $\mathbb {C}^{\textsf{in}}_{\textsf{sk}_{n-2},c^{(n)}_{n-2}}$ must re-run $\mathbb {C}^{\textsf{in}}_{\textsf{sk}_{n},c^{(n)}_{n}}$ on input $(\textsf{sk}_1,\ldots ,\textsf{sk}_{n-1},\bot )$ in order to get $\textsf{sk}_{n}$ and decrypt every PKE layer. This needs to be done at any level of the nested execution, yielding an asymptotic running time of $O(n^n)$. Hence, this technique only works assuming $n=O(1)$, i.e. for O(1)-input predicates. The formal construction is described in Sect. 5.2.

On Achieving CPA-2-Sided Secure Multi-input PE. Until now, we only focused the discussion on achieving CPA-1-sided security. Our multi-input constructions achieve CPA-2-sided security if the underlying single-input PE is CPA-2-sided secure (we highlight that, in our secret-key multi-input PE construction, we need to reduce the n-arity from $\textsf{poly}(\lambda )$ to $O(\log (\lambda ))$ since we use complexity leveraging). We just recall here that, already for the simple notion of single-input PE for arbitrary predicates, CPA-2-sided security implies iO [15].

1.3 Applications

Finally, we explore applications of multi-key and multi-input PE. This question is particularly relevant given the fact that we are only able to obtain multi-key and multi-input PE supporting conjunctions of arbitrary predicates (with wildcards). Luckily, we can show that this class of predicates is already expressive enough to yield interesting cryptographic applications which previously required much stronger assumptions. We refer the reader to the full version [25] for more details.

Matchmaking Encryption (ME). ME is a natural generalization of ABE in which both the sender and the receiver can specify their own attributes and access policies. Previous work showed how to obtain CPA-2-sided (i.e., mismatch and match) secure ME for arbitrary policies with unbounded collusions using iO [10, 11], or for very restricted policies (i.e., for identity matching) using bilinear maps [20, 26] (and ROM [10]). To this end, our CPA-1-sided secure multi-key PE scheme (from the sub-exponential LWE assumption) for conjunction of arbitrary predicates implies the weaker (and non-trivial) notion of CPA-1-sided secure ME (i.e., mismatch only). We stress that the seminal work of ME [10, 11] defined ME in the setting of CPA-2-sided security (i.e., mismatch and match).

Non-interactive MPC (NI-MPC). NI-MPC [14, 34] allows n parties to evaluate a function $f(v_1,\ldots ,v_{n})$ on their inputs using a single round of communication (i.e., each party sends a single message ). This is achieved by assuming a trusted setup (that may depend on the function itself) that generates (possibly correlated) strings (e.g., common reference string $\textsf{crs}$ and encryption keys $\textsf{ek}_i$) that can be later used by the parties to perform function evaluation. Security is formalized using an indistinguishability-based definition: an adversary $\textsf{A}$ cannot distinguish between $(\textsf{Enc}(\textsf{crs},\textsf{ek}_i,v^0_i))_{i\in [n]}$ and $(\textsf{Enc}(\textsf{crs},\textsf{ek}_i,v^1_i))_{i\in [n]}$, so long as any combination of the messages known by the adversary (including the ones it can compute using the encryption key $\textsf{ek}_i$ of a corrupted party) yields the same function’s evaluation.¹³ Previous works [14, 29, 32, 33] showed that NI-MPC implies iO even if we consider very weak security models, like the non-reusable 1-robust (i.e., one malicious party) setting with $n=2$ parties, or the reusable 0-robust (i.e., no malicious parties) setting with $n=\textsf{poly}(\lambda )$ parties.¹⁴

We show that CPA-1-sided multi-input PE supporting predicates $\mathbb {P}(x_1,\ldots ,x_{n})$ tolerating k corruptions and no collusions implies k-robust NI-MPC for the following class of functions:

$$ f_{\mathbb {P}}((x_1,m_1),\ldots ,(x_{n},m_{n})) = {\left\{ \begin{array}{ll} (m_1,\ldots ,m_{n}) &{} \text {if } \mathbb {P}(x_1,\ldots ,x_{n}) =1\\ \bot &{} \text { otherwise.} \end{array}\right. } $$

The resulting NI-MPC satisfies a weaker notion of reusability without session identifiers (i.e., messages produced in different rounds can be interleaved by design) specifically tailored for all-or-nothing functions, which we name CPA-1-sided reusability. In a nutshell, CPA-1-sided reusable NI-MPC guarantees security even if the same setup is reused multiple times, so long as $f_\mathbb {P}$ outputs $\bot$ (i.e., $\mathbb {P}$ is not satisfied) for any combination of the honest messages and the ones the adversary can maliciously compute using the encryption key $\textsf{ek}_i$ of a corrupted party.

By plugging in our results, we obtain either CPA-1-sided reusable $(n-1)$-robust NI-MPC with $n = O(1)$, or CPA-1-sided reusable 0-robust NI-MPC with $n = \textsf{poly}(\lambda )$ where the predicate $\mathbb {P}$ of the function $f_\mathbb {P}$ is a conjunctions of arbitrary predicates (i.e., $\mathbb {P}(x_1,\ldots ,x_{n}) = \mathbb {P}_1(x_1)\wedge \ldots \wedge \mathbb {P}_{n}(x_{n})$) with wildcards under the LWE assumption. Note that a CPA-1-sided reusable NI-MPC for $f_\mathbb {P}$ where $\mathbb {P}(x_1,\ldots ,x_{n}) = \mathbb {P}_1(x_1)\wedge \ldots \wedge \mathbb {P}_{n}(x_{n})$ can be used to implement a voting protocol with message passing, i.e., only when each parties’ vote $x_i$ satisfies its dedicated set of requirements $\mathbb {P}_i(\cdot )$ (i.e., $\mathbb {P}_i(x_i) = 1$ for every $i \in [n]$) the messages are revealed to all the participants. Until this condition is not satisfied, everything remains secret.

We stress that, nonetheless CPA-1-sided reusability is a weakening of the standard reusability definition, our flavor of reusability is still non-trivial to achieve in the setting of general functions. This is because we can build null iO (and, in turn, witness encryption) [19, 31, 48] from CPA-1-sided reusable NI-MPC using the same constructions of iO from (standard) reusable NI-MPC, i.e., CPA-1-sided reusable (resp. CPA-1-sided non-reusable) 0-robust (resp. 1-robust) NI-MPC for $n=\textsf{poly}(\lambda )$ parties (resp. $n=2$ parties) and general functions implies null iO.

1.4 Relation with Witness Encryption (WE)

We observe that both multi-input and multi-key schemes imply witness encryption (WE) [27], if the former support arbitrary predicates (or any predicate that implements a desired NP relation). Brakerski et al. [19] have shown that n-input ABE (i.e., predicate inputs can be public), secure in the secret-key setting and without collusions, implies WE for NP and n-size witnesses. Similarly, we can build WE from multi-key ABE (i.e., a multi-key scheme where predicate inputs can be public) using a similar construction except that we substitute the multiple inputs with the multiple decryption keys of multi-key ABE. Unfortunately, we cannot use here our constructions of multi-key and multi-input since they only support conjunctions of arbitrary predicates (we stress that CPA-1-sided and CPA-2-sided security are not required for constructing WE).

We also observe that arbitrary predicates are not needed if we consider security under corruptions. Indeed, 2-input ABE for conjunctions of arbitrary predicates $\mathbb {P}(x_1,x_2) = \mathbb {P}_1(x_1) \wedge \mathbb {P}_2(x_2)$ without wildcards under 1 corruption and no collusions, implies WE for any relation. Even in this case, our O(1)-input scheme under corruptions fails to imply WE. This is because our construction supports conjunctions of arbitrary predicates each one having a wildcard (in other words, the wildcard is a trivial witness for any statement). We provide more details in the full version of this work [25].

From these observations, we can identify two plausible approaches that could lead to a construction of WE from standard assumptions: (i) enlarging the class of predicates of our secret-key n-input or n-key constructions, or (ii) supporting conjunctions of arbitrary predicates (without wildcards) in the setting of 2-input ABE with security under 1 corruption.

2 Related Work

Multi-input PE is a special case of multi-input FE [29]. It is well known that so-called compact FE (supporting arbitrary functions) implies multi-input FE [9, 15], which in turn implies iO. Constructions of multi-input FE from standard assumptions, in turn, exist for restricted functions [1,2,3,4, 6, 7, 16, 21, 22, 24, 39, 44]. Multi-input PE can also be seen as stronger form of multi-input ABE [19], the difference being that the attributes are not private in the case of ABE. Previously to our work, all (provably secure) constructions of n-input ABE with $n>2$ required iO (the only exception is the concurrent work of Agrawal et al. [8], which we discuss in the next paragraph).

The multi-input and multi-key settings have also been considered in the context of fully-homomorphic encryption [23, 40, 41].

Concurrent and Independent Work. The independent and concurrent work of Agrawal, Yadav, and Yamada [8] proposes two constructions of secret-key (i.e., no corruptions) 2-input key-policy ABE for $\textsf{NC}^1$ with unbounded collusions (recall that, in the ABE setting, only the secrecy of the messages is guaranteed, i.e., inputs can be public). The first construction is based on LWE and pairings, and it is provably secure in the generic group model. The second construction is based on function-hiding inner-product FE, a variant of the non-falsifiable KOALA knowledge assumption (which is proven to hold under the bilinear generic group model), and LWE. However, this second construction achieves a weaker selective flavor of security in which the adversary has to submit both the challenge and the decryption key queries before the setup phase. Additionally, they propose two heuristic constructions. The first is a 2-input ABE for $\textsf{P}$ from lattices, and the second is a 3-input ABE for $\textsf{NC}^1$ from pairings and lattices. However, the security of these heuristic constructions remains unclear.

In comparison, our work directly focuses on the PE setting (i.e., CPA-1-sided security) and provides the first secret-key n-input PE that supports $n = \textsf{poly}(\lambda )$ inputs, with (adaptive) CPA-1-sided security (i.e., secrecy of both inputs and messages) based solely on LWE. However, our construction only supports a restricted class of predicates (i.e., conjunctions of arbitrary predicates with wildcards) and it is secure only in the case of no collusions. Furthermore, differently from [8], we move away from the secret-key setting and propose a second construction of n-input PE (still for conjunctions of arbitrary predicates) that supports $n=O(1)$ inputs and can tolerate $n-1$ corruptions (i.e., up to $n-1$ encryption keys can be adaptively revealed by the adversary). Finally, we propose the notion of multi-key PE (not covered in [8]), and give the first construction of CPA-1-sided secure n-key PE for $n=\textsf{poly}(\lambda )$, with unbounded collusions and still supporting conjunctions of arbitrary predicates, based on LWE.

Regarding the techniques, we highlight that both our work and that of [8] introduce (albeit different) nesting techniques based on lockable obfuscation. In particular, the nesting technique of [8] permits to transform any secret-key n-input ABE into a secret-key n-input PE (achieving CPA-1-sided security). We stress that their approach only works in the secret-key setting. In contrast, we propose a different nesting technique which yields n-input PE for $n = O(1)$ while tolerating $n-1$ corruptions. It is important to note that our nesting technique is not generic, but it is specifically tailored to work with the class of predicates considered in this work.

Turning to applications, we highlight that the multi-input schemes of [8] fail to imply ME, since their constructions are all in the secret-key setting (whereas ME requires a public-key encryption algorithm). As for NI-MPC, the constructions in [8] can be used to obtain a CPA-1-sided 0-robust reusable NI-MPC for all-or-nothing functions defined over arbitrary predicates, but only in the case of 2 parties (3 parties if we consider also the heuristic constructions).

3 Preliminaries

We assume the reader to be familiar with standard cryptographic notation and definitions. The preliminaries can be found in the full version [25].

4 Multi-key and Multi-input Predicate Encryption

We provide the formal definitions of multi-key PE and multi-input PE. In the full version [25], we build ME from multi-key PE and CPA-1-sided reusable robust NI-MPC for all-or-nothing functions from multi-input PE.

Multi-key PE. Formally, an n-key PE with message space $\mathcal {M}$, input space $\mathcal {X}$, and predicate space $\mathcal {P}=\{\mathbb {P}_{v_1,\ldots ,v_{n}}(x)\}_{(v_1,\ldots ,v_{n}) \in \mathcal {V}}$ indexed by $\mathcal {V}= \mathcal {V}_1 \times \ldots \times \mathcal {V}_{n}$, is composed of the following polynomial-time algorithms:

• $\textsf{Setup}(1^\lambda )$: Upon input the security parameter $1^\lambda$ the setup algorithm outputs the master public key $\textsf{mpk}$ and the n master secret key $(\textsf{msk}_1,\ldots ,\textsf{msk}_{n})$.

• $\textsf{KGen}(\textsf{msk}_i, v_i)$: Let $i \in [n]$. The randomized key generator takes as input the i-th master secret key $\textsf{msk}_i$ and the i-th index $v_i\in \mathcal {V}_i$. The algorithm outputs the i-th secret decryption key $\textsf{dk}_{v_i}$ for the predicate index $v_i$.

• $\textsf{Enc}(\textsf{mpk}, x, m)$: The randomized encryption algorithm takes as the master public key $\textsf{mpk}$, an input $x\in \mathcal {X}$, and a message $m\in \mathcal {M}$. The algorithm produces a ciphertext $c$.

• $\textsf{Dec}(\textsf{dk}_{v_1}, \ldots , \textsf{dk}_{v_{n}}, c)$: The deterministic decryption algorithm takes as input n secret decryption keys $(\textsf{dk}_{v_1},\ldots , \textsf{dk}_{v_{n}})$ for the n indexes $(v_1,\ldots ,v_{n}) \in \mathcal {V}$ and a ciphertext $c$. The algorithm outputs a message $m$.

Correctness is intuitive: given the decryption keys $(\textsf{dk}_{v_1},\ldots ,\textsf{dk}_{v_{n}})$ for $(v_1,\ldots ,v_{n}) \in \mathcal {V}$, the decryption algorithm returns the message $m$ (encrypted under the input $x$) with overwhelming probability, whenever $\mathbb {P}_{v_1,\ldots ,v_{n}}(x)=1$. See [25] for the formal definition.

Fig. 1.

Game defining CPA-t-sided security of n-key PE.

As for security, we adapt the standard CPA-1-sided and CPA-2-sided security of PE to the n-key setting. In particular, an adversary (with oracle access to $\textsf{KGen}(\textsf{msk}_i,\cdot )$ for $i \in [n]$) cannot distinguish between $\textsf{Enc}(\textsf{mpk},x^0,m^0)$ and $\textsf{Enc}(\textsf{mpk},x^1,m^1)$ except with non-negligible probability. When considering CPA-1-sided security, the adversary is valid only if it cannot decrypt the challenge ciphertext, i.e., it asks to the n key generation oracles indexes $(v_1,\ldots ,v_{n})$ such that $\mathbb {P}_{v_1,\ldots ,v_{n}}(x^0) = \mathbb {P}_{v_1,\ldots ,v_{n}}(x^1) =0$. Analogously, the CPA-2-sided security captures the indistinguishability of $\textsf{Enc}(\textsf{mpk},x^0,m^0)$ and $\textsf{Enc}(\textsf{mpk},x^1,m^1)$ even when the adversary can decrypt the challenge ciphertext, i.e., $\mathbb {P}_{v_1,\ldots ,v_{n}}(x^0) = \mathbb {P}_{v_1,\ldots ,v_{n}}(x^1) = 1$ and $m^0 = m^1$. These security definitions are formalized below.

Definition 1

(CPA-1-sided and CPA-2-sided security of n-key PE). Let $t \in [2]$. We say that a n-key PE $\varPi$ is CPA-t-sided secure if for all valid PPT adversaries $\textsf{A}= (\textsf{A}_0,\textsf{A}_1)$:

$$ \left|\mathbb {P}{\big [\textbf{G}^{\mathsf {\textsf{CPA}\text {-}}t\mathsf {\text {-}\textsf{kPE}}}_{\varPi , \textsf{A}}(\lambda ) = 1\big ]} - \frac{1}{2} \right|\le \textsf{negl}(\lambda ), $$

where game $\textbf{G}^{\mathsf {\textsf{CPA}\text {-}}t\mathsf {\text {-}\textsf{kPE}}}_{\varPi , \textsf{A}}(\lambda )$ is depicted in Fig. 1. Adversary $\textsf{A}$ is called valid if $\forall v_1 \in \mathcal {Q}_{\textsf{KGen}(\textsf{msk}_1,\cdot )},\ldots ,\forall v_{n} \in \mathcal {Q}_{\textsf{KGen}(\textsf{msk}_{n},\cdot )}$, we have

$$\begin{aligned} {\textbf {Case t=1:}}&\ \mathbb {P}_{v_1,\ldots ,v_{n}}(x^0) = \mathbb {P}_{v_1,\ldots ,v_{n}}(x^1) = 0.\\ {\textbf {Case t=2:}}&\ \text {Either } \mathbb {P}_{v_1,\ldots ,v_{n}}(x^0) = \mathbb {P}_{v_1,\ldots ,v_{n}}(x^1) = 0 \\&\ \text {or } \mathbb {P}_{v_1,\ldots ,v_{n}}(x^0) = \mathbb {P}_{v_1,\ldots ,v_{n}}(x^1) \wedge m^0 = m^1. \end{aligned}$$

Multi-input PE. Formally, an n-input PE with message space $\mathcal {M}= \mathcal {M}_1 \times \ldots \times \mathcal {M}_{n}$, input space $\mathcal {X}= \mathcal {X}_1 \times \ldots \times \mathcal {X}_{n}$, and predicate space $\mathcal {P}$, is composed of the following polynomial-time algorithms:

• $\textsf{Setup}(1^\lambda )$: Upon input the security parameter $1^\lambda$ the setup algorithm outputs the encryption keys $(\textsf{ek}_1,\ldots ,\textsf{ek}_{n})$ and the master secret key $\textsf{msk}$.

• $\textsf{KGen}(\textsf{msk}, \mathbb {P})$: The randomized key generator takes as input the master secret key $\textsf{msk}$ and a predicate $\mathbb {P}\in \mathcal {P}$. The algorithm outputs a secret decryption key $\textsf{dk}_{\mathbb {P}}$ for predicate $\mathbb {P}$.

• $\textsf{Enc}(\textsf{ek}_i, x_i, m_i)$: Let $i \in [n]$. The randomized encryption algorithm takes as input an encryption key $\textsf{ek}_i$, an input $x_i\in \mathcal {X}_i$, and a message $m_i\in \mathcal {M}_i$. The algorithm produces a ciphertext $c_i$ linked to $x_i$.

• $\textsf{Dec}(\textsf{dk}_{\mathbb {P}}, c_1,\ldots , c_{n})$: The deterministic decryption algorithm takes as input a secret decryption key $\textsf{dk}_{\mathbb {P}}$ for predicate $\mathbb {P}\in \mathcal {P}$ and n ciphertexts $(c_1,\ldots ,c_{n})$. The algorithm outputs n messages $(m_1,\ldots ,m_{n})$.

Correctness states that ciphertexts $(c_1,\ldots ,c_{n})$, each linked to an input $x_i$, correctly decrypt with overwhelming probability if $\mathbb {P}(x_1,\ldots ,x_{n})=1$. See the full version of this work [25] for the formal definition.

Security with and without Corruptions. The CPA-1-sided and CPA-2-sided security of n-input PE capture the infeasibility in distinguishing between ciphertexts $(\textsf{Enc}(\textsf{ek}_1,x^0_1,m^0_1),\ldots ,\textsf{Enc}(\textsf{ek}_{n},x^0_{n},m^0_{n}))$ and $(\textsf{Enc}(\textsf{ek}_1,x^1_1,m^1_1),\ldots ,\textsf{Enc}(\textsf{ek}_{n},x^1_{n},m^1_{n}))$. This is modeled by an adversary having oracle access to a key generation oracle $\textsf{KGen}(\textsf{msk},\cdot )$ (allowing it to get decryption keys $\textsf{dk}_\mathbb {P}$ on predicates of its choice) and n encryption oracles $\textsf{Enc}(\textsf{ek}_1,\cdot ,\cdot ),\ldots , \textsf{Enc}(\textsf{ek}_{n},\cdot ,\cdot )$ (allowing it to get encryptions of arbitrary messages and inputs). Differently from the n-key setting, we consider different models of security with respect to whether the encryption keys are secret (i.e., no corruptions) or public/leaked (i.e., the adversary has the possibility to get one or more encryption keys of its choice). The corruption of an encryption key is captured by giving access to a corruption oracle $\textsf{Corr}(\cdot )$ to the adversary that, on input $i \in [n]$, it returns $\textsf{ek}_i$. Intuitively, the knowledge of $\textsf{ek}_i$ impacts the validity condition that the adversary must satisfy (e.g., the challenge ciphertext cannot be decrypted). Indeed, $\textsf{ek}_i$ would allow the adversary to produce arbitrary i-th ciphertexts on arbitrary i-th inputs $x_i$ and potentially decrypt part of the challenge ciphertext. Concretely, as for CPA-1-sided security, the validity of the adversary can be defined as follows:

• No corruptions (a.k.a. the secret-key setting). If all the encryption keys $(\textsf{ek}_1,\ldots ,\textsf{ek}_{n})$ are secret the validity conditions of CPA-1-sided security is straightforward. It intuitively states that for every $\textsf{dk}_{\mathbb {P}}$ (obtained through oracle $\textsf{KGen}(\textsf{msk},\cdot )$) and any tuple of ciphertexts $(c_1,\ldots ,c_{n})$ (each linked to an input $x_i$) obtained through the interleaving of part of the challenge ciphertext with the ciphertexts generated by invoking oracles $\{\textsf{Enc}(\textsf{ek}_i,\cdot ,\cdot )\}_{i\in [n]}$, we must have that $\mathbb {P}(x_1,\ldots ,x_{n})=0$ (otherwise part of the challenge ciphertext can be decrypted).

• With corruptions. If some of the encryption keys are known by the adversary (i.e., obtained through the corruption oracle $\textsf{Corr}(\cdot )$) then the validity condition now changes according to which keys have been obtained. This is because the adversary can now autonomously compute arbitrary ciphertext (for a particular slot i) using the leaked i-th encryption key $\textsf{ek}_i$. Taking into account this observation, the validity of CPA-1-sided security with corruptions says that any tuple of ciphertexts $(c_1,\ldots ,c_{n})$ that can be obtained by interleaving part of the challenge ciphertexts with both the ones generated through oracles $\{\textsf{Enc}(\textsf{ek}_i,\cdot ,\cdot )\}_{i\in [n]}$ and the ones that can be autonomously generated using the leaked encryption keys, we must have that $\mathbb {P}(x_1,\ldots ,x_{n})=0$.

The validity of CPA-2-sided security (with and without corruptions) can be easily obtained by adapting the above discussion. Below, we provide the formal definition.

Fig. 2.

Game defining CPA-t-sided security of n-input PE in the $\ell$-corruptions setting. Oracle $\textsf{Corr}(j)$ returns $\textsf{ek}_j$ for $j \in [n]$.

Definition 2

($\ell$-Corruptions CPA-1-sided and CPA-2-sided security of n-input PE). Let $t \in [2]$. We say that an n-input PE $\varPi$ is CPA-t-sided secure in the $\ell$-corruptions setting if for all valid PPT adversaries $\textsf{A}= (\textsf{A}_0,\textsf{A}_1)$:

$$ \left|\mathbb {P}{\big [\textbf{G}^{\ell \text {-}\textsf{CPA}\text {-}t\text {-}\textsf{iPE}}_{\varPi , \textsf{A}}(\lambda ) = 1\big ]} - \frac{1}{2} \right|\le \textsf{negl}(\lambda ), $$

where game $\textbf{G}^{\ell \text {-}\textsf{CPA}\text {-}t\text {-}\textsf{iPE}}_{\varPi , \textsf{A}}(\lambda )$ is depicted in Fig. 2. Let $\mathcal {Q}_i = \{x| \exists (x,m) \in \mathcal {Q}_{\textsf{Enc}(\textsf{ek}_i,\cdot ,\cdot )} \}$ for $i \in [n]\setminus \mathcal {Q}_{\textsf{Corr}}$ and $\mathcal {Q}_i = \mathcal {X}_{i}$ for $i \in \mathcal {Q}_{\textsf{Corr}}$. Moreover, let $\mathcal {Q}^d_i$ (for $d\in \{0,1\}$) be the ordered list composed of the predicate inputs $\mathcal {Q}_i$ and the challenge input $x^d_{i}$, i.e., $\mathcal {Q}^d_i = \{x^{(1,d)}_i,\ldots ,x^{(k_i,d)}_i,x^{(k_i+1,d)}_i = x^d_i\}$ where $k_i = |\mathcal {Q}_i|$ and $x^{(j,d)} \in \mathcal {Q}_i$ for $j \in [k_i]$.¹⁵ Adversary $\textsf{A}$ is called valid if $|\mathcal {Q}_{\textsf{Corr}}| \le \ell$ and $\forall \mathbb {P}\in \mathcal {Q}_{\textsf{KGen}}$, $\forall j \in [n]$, $\forall i_1 \in [k_1 +1],\ldots , \forall i_n \in [k_n + 1]$, we have

$$\begin{aligned} {\textbf {Case t=1:}}&\ \mathbb {P}(x^{(i_1,0)}_1,\ldots ,x^{(i_{j-1},0)}_{j-1},x^{0}_j,x^{(i_{j+1},0)}_{j+1},\ldots ,x^{(i_n,0)}_{n}) = \nonumber \\&\ \mathbb {P}(x^{(i_1,1)}_1,\ldots ,x^{(i_{j-1},1)}_{j-1},x^{1}_j,x^{(i_{j+1},1)}_{j+1},\ldots ,x^{(i_n,1)}_{n}) = 0. \\ {\textbf {Case t=2:}}&\ \text {Either } \nonumber \\&\quad \mathbb {P}(x^{(i_1,0)}_1,\ldots ,x^{(i_{j-1},0)}_{j-1},x^{0}_j,x^{(i_{j+1},0)}_{j+1},\ldots ,x^{(i_n,0)}_{n}) = \nonumber \\&\quad \mathbb {P}(x^{(i_1,1)}_1,\ldots ,x^{(i_{j-1},1)}_{j-1},x^{1}_j,x^{(i_{j+1},1)}_{j+1},\ldots ,x^{(i_n,1)}_{n}) = 0 \nonumber \\&\ \text {or } \nonumber \\&\quad \mathbb {P}(x^{(i_1,0)}_1,\ldots ,x^{(i_{j-1},0)}_{j-1},x^{0}_j,x^{(i_{j+1},0)}_{j+1},\ldots ,x^{(i_n,0)}_{n}) = \nonumber \\&\quad \mathbb {P}(x^{(i_1,1)}_1,\ldots ,x^{(i_{j-1},1)}_{j-1},x^{1}_j,x^{(i_{j+1},1)}_{j+1},\ldots ,x^{(i_n,1)}_{n}) \wedge m^0_j = m^{1}_j. \end{aligned}$$

Through the paper, for $t \in [2]$, we say that $\varPi$ is CPA-t-sided secure in the $\ell$-corruptions setting and without collusions if $|\mathcal {Q}_{\textsf{KGen}}| = 1$ (i.e., the adversary asks for a single decryption key). If $|\mathcal {Q}_\textsf{Corr}|=0$ (i.e., no corruptions), we say that $\varPi$ is CPA-t-sided secure in the secret-key setting. In case of both restrictions, we say that $\varPi$ is CPA-t-sided secure in the secret-key setting and without collusions (i.e., $|\mathcal {Q}_\textsf{Corr}|=0$ and $|\mathcal {Q}_{\textsf{KGen}}| = 1$).

Remark 1 (Relation with multi-key PE)

In the full version of this work [25], we show that CPA-t-sided secure $(n+1)$-input PE tolerating 1 corruption, naturally implies CPA-t-sided secure n-key PE.¹⁶ We stress that such a relation holds only if the $(n+1)$-input PE supports arbitrary predicates. On the other hand, if we consider restricted classes of predicates (as studied in this work), the above implication does not to hold anymore, making multi-input and multi-key PE incomparable.¹⁷

Also, we discuss the relation between the multi-key and multi-input settings when considering a weaker definition of security. In particular, if we drop the secrecy of the predicate inputs, i.e., only the the messages remain secret (which is equivalent to ABE), then we can show that multi-key ABE implies multi-input ABE only in the presence of no corruptions.

5 Constructions

In this section, we give different constructions of multi-key and multi-input PE (see also Sect. 1.2) for predicates $\mathbb {P}(x_1,\ldots ,x_{n}) = \mathbb {P}_1(x_1) \wedge \ldots \wedge \mathbb {P}_{n}(x_{n})$.

In particular, in Sect. 5.1 we give a construction of n-key PE from single-input PE and lockable obfuscation for $n = \textsf{poly}(\lambda )$. This construction is secure against unbounded collusions.

In Sect. 5.2, we give a construction of O(1)-input PE, that is CPA-1-side secure without collusions and in the $(n-1)$-corruptions setting, from single-input PE, lockable obfuscation, and PKE. It leverages a new nesting execution technique of (lockable obfuscated) circuits. Our secret-key n-input PE construction for $n=\textsf{poly}(\lambda )$ is deferred to full version [25].

Both multi-input constructions support conjunctions of arbitrary predicates with wildcards, i.e., for every $i\in [n]$, there exists (possibly unique) a wildcard $x^\star _i$ such that for every i-th predicate $\mathbb {P}_i$ we have $\mathbb {P}_i(x^\star _i) = 1$ (in [25] we discuss how to remove the wildcard when no corruptions are in place).

Also, our constructions are generic and achieve CPA-2-sided security if the underlying single-input PE is CPA-2-sided secure (our CPA-2-sided secure secret-key multi-input PE construction (see [25]) supports $n = O(\log (\lambda ))$).

Fig. 3.

Definition of the circuit $\mathbb {C}_c$ of Construction 1.

5.1 Multi-key PE from PE and Lockable Obfuscation

Construction 1

Consider the following primitives:

• 1. For $i \in [n]$, a PE scheme $\textsf{PE}_i = (\textsf{Setup}_i, \textsf{KGen}_i, \textsf{Enc}_i, \textsf{Dec}_i)$ with message space $\mathcal {M}_i$, input space $\mathcal {X}_i$, and predicate space $\mathcal {P}_i =\{\mathbb {P}_v(x)\}_{v\in \mathcal {V}_i}$ indexed by $\mathcal {V}_i$. Without loss of generality, we assume that $\textsf{PE}_i$ has ciphertext space $\mathcal {Y}_{i}$, $\mathcal {M}_{1} = \{0,1\}^{m(\lambda )}$, and $\mathcal {M}_{i} = \mathcal {Y}_{i-1}$ for every $i \in [n] \setminus \{1\}$. In order to do not incur into an exponential ciphertext growth (e.g., for $n = \textsf{poly}(\lambda )$), each i-th PE scheme must have a ciphertext expansion of $\textsf{poly}(\lambda )+ |m_i|$ where $|m_i|$ is the length of the messages $m_i \in \mathcal {M}_i$ supported by the i-th PE scheme (this can be obtained generically from any PE scheme by leveraging hybrid encryption, i.e., $\textsf{Enc}_i(\textsf{mpk},x,s) || \textsf{PRG}(s) \oplus m_i$ where ).

• 2. A lockable obfuscation scheme $\textsf{LOBF}= (\textsf{Obf}, \textsf{Eval})$ with message space $\mathcal {M}$ for the family of circuits $\mathcal {C}_{n,s,d}(\lambda ) = \{\mathbb {C}_{c}\}$ as defined in Fig. 3, where $n(\lambda )$, $s(\lambda )$, $d(\lambda )$ depends on the schemes $\textsf{PE}_1,\ldots ,\textsf{PE}_{n}$ used, and the circuits $\mathcal {C}_{n,s,d}(\lambda )$.

We build a n-key PE scheme $\varPi$ with message space $\mathcal {M}$, input space $\mathcal {X}= \mathcal {X}_1 \times \ldots \times \mathcal {X}_{n}$, and predicate space $\mathcal {P}=\{\mathbb {P}_{v_1,\ldots ,v_{n}}(x_1,\ldots ,x_{n})=\mathbb {P}_{v_1}(x_1)\wedge \ldots \wedge \mathbb {P}_{v_{n}}(x_{n})\}_{(v_1,\ldots ,v_{n}) \in \mathcal {V}}$ indexed by $\mathcal {V}= \mathcal {V}_1 \times \ldots \times \mathcal {V}_{n}$ (and $\mathbb {P}_{v_i} \in \mathcal {P}_i$ for $i \in [n]$), as follows:

• $\textsf{Setup}(1^\lambda )$: Upon input the security parameter $1^\lambda$ the randomized setup algorithm outputs $\textsf{mpk} = (\textsf{mpk}_1,\ldots ,\textsf{mpk}_{n})$ and $\textsf{msk}_1,\ldots ,\textsf{msk}_{n}$ where for $i \in [n]$.

• $\textsf{KGen}(\textsf{msk}_i, v_i)$: Let $i \in [n]$. Upon input the i-th master secret key $\textsf{msk}_i$ and the i-th predicate index $v_i\in \mathcal {V}_i$, the randomized key generator outputs where $\mathbb {P}_{v_i} \in \mathcal {P}_i$.

• $\textsf{Enc}(\textsf{mpk}, x, m)$: Upon input the master public key $\textsf{mpk} = (\textsf{mpk}_1,\ldots ,\textsf{mpk}_{n})$, an input $x= (x_1,\dots ,x_{n}) \in \mathcal {X}$, and a message $m\in \mathcal {M}$, the randomized encryption proceeds as follows:

  • 1. Sample and let $c_{0} = y$.

  • 2. For $i\in [n]$, compute .

  Finally, it outputs $c= \widetilde{\mathbb {C}}$ where .

• $\textsf{Dec}(\textsf{dk}_{v_1}, \ldots , \textsf{dk}_{v_{n}}, c)$: Upon input n decryption keys $\textsf{dk}_{v_1}, \ldots , \textsf{dk}_{v_{n}}$ and a ciphertext $c= \widetilde{\mathbb {C}}$, the deterministic decryption algorithm outputs $m= \textsf{Eval}(\widetilde{\mathbb {C}},(\textsf{dk}_{v_1},\ldots , \textsf{dk}_{v_{n}}))$.

Correctness follows from the correctness of the underlying schemes. We establish the following result whose proof is deferred to full version [25].

Theorem 4

Let $n=\textsf{poly}(\lambda )$, $\textsf{PE}_1,\ldots ,\textsf{PE}_{n}$ and $\textsf{LOBF}$ be as above. If $\textsf{LOBF}$ is secure and

• 1. each $\textsf{PE}_1,\ldots ,\textsf{PE}_{n}$ is CPA secure, then the n-key PE scheme $\varPi$ from Construction 1 is CPA-1-sided secure (Definition 1).

• 2. each $\textsf{PE}_1,\ldots ,\textsf{PE}_{n}$ is CPA-2-sided secure, then the n-key PE scheme $\varPi$ from Construction 1 is CPA-2-sided secure (Definition 1).

We stress that CPA secure single-input PE (see the above theorem) guarantees only the secrecy of the message (whereas predicate inputs can be public). This is equivalent to the notion of single-input ABE.

5.2 Multi-input PE from PE, Lockable Obfuscation and PKE

Fig. 4.

Definitions of the circuits $\mathbb {C}^{\textsf{in}}_{c,\textsf{sk},i}$ and $\mathbb {C}^{\textsf{out}}_{c,\textsf{sk},i}$ supported by the lockable obfuscation schemes $\textsf{LOBF}_3$ and $\textsf{LOBF}_4$ of Construction 2.

Corruption Setting. We present our construction of n-input PE that is CPA-1-sided secure in the $(n-1)$-corruptions setting without collusions. This construction handles constant-arity (i.e., $n \in O(1)$) since the decryption running time is $O(n^n)$. It is based on CPA secure single-input PE, lockable obfuscation, and PKE and it leverages the nested execution technique described in Sect. 1.2. Also, the same construction achieves CPA-2-sided security if the initial single-input PE is CPA-2-sided secure.

Construction 2

(n-input PE in the corruption setting). Consider the following primitives:

• 1. A PE scheme $\textsf{PE}= (\textsf{Setup}_1, \textsf{KGen}_1, \textsf{Enc}_1, \textsf{Dec}_1)$ with message space $\mathcal {M}_1 = \{0,1\}^{m_3(\lambda ) + m_4(\lambda )}$, input space $\mathcal {X}_1 = \mathcal {X}_{1,1} \times \ldots \times \mathcal {X}_{1,n}$, and predicate space $\mathcal {P}_1 =\{\mathbb {P}(x_1,\ldots ,x_{n})\} = \{\mathbb {P}_1(x_1) \wedge \ldots \wedge \mathbb {P}_{n}(x_{n})\}$. Without loss of generality, we assume that $\textsf{PE}$ has ciphertext space $\mathcal {Y}_1$ and there exists a (single) wildcard input $(x^\star _1,\ldots ,x^\star _{n}) \in \mathcal {X}_1$ such that $\forall (\mathbb {P}_1(x_1)\wedge \ldots \wedge \mathbb {P}_{n}(x_{n})) \in \mathcal {P}_1,\forall i \in [n], \mathbb {P}_i(x^\star _i)=1$.

• 2. For $i \in [n]$, a PKE scheme $\textsf{PKE}_{2,i} = (\textsf{KGen}_{2,i},\textsf{Enc}_{2,i},\textsf{Dec}_{2,i})$ with message space $\mathcal {M}_{2,i}$. Without loss of generality, we assume that $\textsf{PKE}_i$ has ciphertext space $\mathcal {Y}_{2,i}$ and secret-key space $\mathcal {K}_{2,i}$. Moreover, we assume that $\mathcal {M}_{2,1} = \mathcal {Y}_{1}$, and $\mathcal {M}_{2,i} = \mathcal {Y}_{2,i-1}$ for every $i \in [n]\setminus \{1\}$.

• 3. A lockable obfuscation scheme $\textsf{LOBF}_3 = (\textsf{Obf}_3, \textsf{Eval}_3)$ with message space $\mathcal {M}_3 = (\mathcal {K}_{2,1}\cup \ldots \cup \mathcal {K}_{2,n}) \times \{0,1\}^{\lfloor \log _2(n)\rfloor +1}$ for the family of circuits $\mathcal {C}^{\textsf{in}}_{n_3,s_3,d_3}(\lambda )= \{\mathbb {C}^{\textsf{in}}_{c,\textsf{sk},i}\}$ defined in Fig. 4, where $n_3(\lambda )$, $s_3(\lambda )$, $d_3(\lambda )$ depends on the schemes $\textsf{PE},\textsf{PKE}_{2,1},\ldots ,\textsf{PKE}_{2,n}$ used, and the circuits $\mathcal {C}^{\textsf{in}}_{n_3,s_3,d_3}(\lambda )$.

• 4. A lockable obfuscation scheme $\textsf{LOBF}_4 = (\textsf{Obf}_4, \textsf{Eval}_4)$ with message space $\mathcal {M}_4$ for the family of circuits $\mathcal {C}^{\textsf{out}}_{n_4,s_4,d_4}(\lambda ) = \{\mathbb {C}^{\textsf{out}}_{c,\textsf{sk},i}\}$ defined in Fig. 4, where $n_4(\lambda )$, $s_4(\lambda )$, $d_4(\lambda )$ depends on the schemes $\textsf{PE},\textsf{PKE}_{2,1},\ldots ,\textsf{PKE}_{2,n},\textsf{LOBF}_3$ used, and the circuits $\mathcal {C}^{\textsf{out}}_{n_4,s_4,d_4}(\lambda )$.

We build a n-input PE scheme with message space $\mathcal {M}= \overbrace{\mathcal {M}_{4} \times \ldots \times \mathcal {M}_{4}}^{n}$, input space $\mathcal {X}= \mathcal {X}_1$, and predicate space $\mathcal {P}= \mathcal {P}_1 =\{\mathbb {P}(x_1,\ldots ,x_{n})\} = \{\mathbb {P}_1(x_1) \wedge \ldots \wedge \mathbb {P}_{n}(x_{n})\}$ with wildcard (i.e., there exists a (single) wildcard $(x^\star _1,\ldots ,x^\star _n) \in \mathcal {X}$ such that $\forall (\mathbb {P}_1(x_1)\wedge \ldots \wedge \mathbb {P}_n(x_n)) \in \mathcal {P}$, $\forall i \in [n]$, $\mathbb {P}_i(x^\star _i) =1$), as follows:

• $\textsf{Setup}(1^\lambda )$: Upon input the security parameter $1^\lambda$ the randomized setup algorithm outputs $(\textsf{ek}_1,\ldots ,\textsf{ek}_{n})$ and $\textsf{msk}$ where , $\textsf{ek}_i = (\textsf{mpk}, \textsf{sk}_i,\textsf{pk}_1,\ldots ,\textsf{pk}_{n})$, and for $i \in [n]$.

• $\textsf{KGen}(\textsf{msk}, \mathbb {P})$: Upon input the master secret key $\textsf{msk}$ and a predicate $\mathbb {P}\in \mathcal {P}$, the randomized key generator algorithm outputs .

• $\textsf{Enc}(\textsf{ek}_i, x_i, m_i)$: Let $i \in [n]$. Upon input an encryption key $\textsf{ek}_i = (\textsf{mpk}, \textsf{sk}_i,\textsf{pk}_1,\ldots ,\textsf{pk}_{n})$, an input $x_i \in \mathcal {X}_{1,i}$, and a message $m_i\in \mathcal {M}_4$, the randomized encryption algorithm samples and proceeds as follows:

  • 1. Compute where $x_j = x^\star _j$ for $j \in [n]\setminus \{i\}$.

  • 2. For $j \in [n]$, compute .

  Finally, it outputs $c_i=(\widetilde{\mathbb {C}}^{\textsf{out}}_i,\widetilde{\mathbb {C}}^{\textsf{in}}_i)$, where and .

• $\textsf{Dec}(\textsf{dk}_{\mathbb {P}}, c_1,\ldots , c_{n})$: Upon input a decryption key $\textsf{dk}_{\mathbb {P}}$ for predicate $\mathbb {P}\in \mathcal {P}$, and n ciphertexts $(c_1, \ldots , c_{n})$ such that $c_i = (\widetilde{\mathbb {C}}^{\textsf{out}}_i,\widetilde{\mathbb {C}}^{\textsf{in}}_i)$ for $i \in [n]$. The deterministic decryption algorithm returns $(m_1,\ldots ,m_{n})$ where $m_i = \textsf{Eval}_4(\widetilde{\mathbb {C}}^{\textsf{out}}_{i},(\widetilde{\mathbb {C}}^{\textsf{in}}_{1},\ldots ,\widetilde{\mathbb {C}}^{\textsf{in}}_{i-1}, \widetilde{\mathbb {C}}^{\textsf{in}}_{i+1},\ldots , \widetilde{\mathbb {C}}^{\textsf{in}}_{n}, \textsf{dk}_\mathbb {P}))$ for $i \in [n]$.

Correctness follows from the one of the underlying primitives (see also Fig. 4 for the definitions of $\mathbb {C}^{\textsf{in}}_{c,\textsf{sk},i}$ and $\mathbb {C}^{\textsf{out}}_{c,\textsf{sk},i}$). Moreover, decryption is polynomial time when $n \in O(1)$. Below, we establish the following result whose proof is deferred to full version [25].

Theorem 5

Let $n = O(1)$, $\textsf{PE}$, $\textsf{PKE}_{2,1},\ldots ,\textsf{PKE}_{2,n}$, $\textsf{LOBF}_3$, and $\textsf{LOBF}_4$ be as above. If each $\textsf{PKE}_{2,i}$ (for $i \in [n]$) is CPA secure, both $\textsf{LOBF}_3$ and $\textsf{LOBF}_4$ are secure, and

• 1. $\textsf{PE}$ is CPA secure without collusions, then the n-input PE scheme $\varPi$ from Construction 2 is CPA-1-sided secure in the $(n-1)$-corruptions setting without collusions (Definition 2).

• 2. $\textsf{PE}$ is CPA-2-sided secure without collusions, then the n-input PE scheme $\varPi$ from Construction 2 is CPA-2-sided secure in the $(n-1)$-corruptions setting without collusions (Definition 2).

As for Theorem 4, CPA secure single-input PE (see the above theorem) guarantees only the secrecy of the message (whereas predicate inputs can be public). This is equivalent to the notion of single-input ABE.