Keywords

1 Introduction

Attribute based encryption (\({\textsf{ABE}}\)) is a generalization of public key encryption which enables fine grained access control on encrypted data. In an \({\textsf{ABE}}\) scheme, the ciphertext is associated with a secret message m and a public attribute vector \(\textbf{x}\) while a secret key is associated with a function f. Decryption succeeds to reveal m if and only if \(f(\textbf{x})=1\). Security seeks ciphertext indistinguishability in the presence of collusion attacks, namely an adversary possessing a collection of keys \(\{\textsf{sk}_{f_i}\}_{i \in [\textrm{poly}]}\) should not be able to distinguish between ciphertexts corresponding to \((\textbf{x}, m_0)\) and \((\textbf{x}, m_1)\) unless one of the keys \(\textsf{sk}_{f_{i^*}}\) is individually authorised to decrypt, i.e. \(f_{i^*}(\textbf{x})=1\). \({\textsf{ABE}}\) comes in two flavours – “key-policy” and “ciphertext-policy”, depending on whether the function f is embedded in the key or the ciphertext.

The stronger notion of predicate encryption (\({\textsf{PE}}\)) [18, 29, 36, 49] further requires the attribute vector \(\textbf{x}\) to be hidden so that ciphertexts corresponding to \((\textbf{x}_0, m_0)\) and \((\textbf{x}_1, m_1)\) remain indistinguishable so long as \(f_i(\textbf{x}_0)=f_i(\textbf{x}_1)=0\) for all secret keys \(\{\textsf{sk}_{f_i}\}_{i \in [\textrm{poly}]}\) seen by the adversary.

Both \({\textsf{ABE}}\) and \({\textsf{PE}}\) have been widely studied, and possess elegant instantiations from a variety of assumptions [6, 13, 16, 18, 18, 20, 22, 28, 29, 29, 30, 32, 36, 36,37,38,39, 46,47,48,49, 51, 52]. Despite all this amazing progress, however, all known constructions support the single input setting – namely, the function f embedded in the secret key \(\textsf{sk}_f\) has arity one, so that the secret key can be used to decrypt only a single ciphertext at a time. While the more realistic multi-input setting has been studied for other closely related notions such as fully homomorphic encryption [24, 44, 45] and functional encryption [1,2,3,4, 7, 11, 23, 25, 27, 40, 50], this has not been investigated at all in the context of predicate encryption, and only sparingly [19] in the context of attribute based encryption.

Supporting Multiple Sources. We argue that the multi-input setting is important even in the context of \({\textsf{ABE}}\) and \({\textsf{PE}}\) and generalizing these primitives to support multiple sources enables a host of new and natural applications. At the heart of the multi-input setting, for any primitive, is the fact that data generated independently in multiple locations may be correlated in meaningful ways, and it is often pertinent to consider the input as a concatenation of these correlated partial inputs. For instance, a patient is likely to visit different medical centres for treatment of different diseases and her overall medical record is a concatenation of the medical data generated at different centers. Similarly, a company is likely to conduct research and development related to a given technology in different locations but the complete data pertaining to that technology is a concatenation of these. Moreover, to organize data logically and to benefit from cloud storage and computing, it is useful for each source to upload this encrypted data to a central server. Now, it may be desirable to provide restricted access to relevant consumers of the data, exactly as in \({\textsf{ABE}}\) for encrypted access control (say) or \({\textsf{PE}}\) for encrypted search (say), but with the caveat that the input was generated in a distributed manner and is encoded in multiple ciphertexts.

For concreteness, consider a doctor who is treating Covid patients and wants to understand the relation between Covid and other medical conditions such as asthma or cancer, each of which are treated at different locations. The records of a given patient are encrypted independently and stored in a central repository, and the doctor can be given a key that filters stored (encrypted) records according to criteria such as condition = ‘Covid’ and condition = ‘asthma’ and age group =‘60–80’ and enables decryption of these. Similarly, a company (e.g. IBM) which conducts research in quantum technologies is likely to have different teams for theoretical and experimental research, and these teams are likely to work in different locations – indeed, even members of the same team may not be co-located. Data pertaining to the research could be stored encrypted in a central location where individual ciphertexts are generated independently, and the company may desire to give restricted access to a patent office. As a third example, a company may have been sued for some malpractice, and the data pertinent to the case could span multiple locations. Now the company may wish to provide restricted access to a law firm which enables decryption only of the data pertaining to the lawsuit, encrypted independently by multiple sources. A possible solution may be to gather all the information at a central entity and then use single input \({\textsf{ABE}}\) or \({\textsf{PE}}\) as before, but there are two problems with this approach: (i) if data is transmitted unencrypted to the central server it creates vulnerability – this can be avoided by each source encrypting to the server’s public key, and the server decrypting and re-encrypting using single input schemes, but this is wasteful and cumbersome, (ii) one may desire to use an untrusted commercial cloud server to store the encrypted data, in which case the step of creating the ciphertext at a central server in step (i) is completely redundant and doubly inefficient.

Multi-input attribute based encryption (\(\textsf{miABE}\)) or predicate encryption (\(\textsf{miPE}\)) arise as natural fits to the above applications. Similarly to the single input case, the secret key corresponds to a function f but the arity of this function can now be \(k > 1\) – we may have k ciphertexts generated independently encoding \((\textbf{x}_i, m_i)_{i \in [k]}\), and decryption reveals \((m_1,\ldots ,m_k)\) if and only if \(f(\textbf{x}_1,\ldots ,\textbf{x}_k)=1\). Indeed, any application of single input \({\textsf{ABE}}\) and \({\textsf{PE}}\) where the underlying data is generated in multiple locations and is correlated in meaningful ways can benefit from the abstraction of multi-input \({\textsf{ABE}}\) and \({\textsf{PE}}\).

Prior Work. Brakerski et al. [19] studied the notion of \(\textsf{miABE}\) and showed that \(\textsf{miABE}\) for polynomial arity implies witness encryption (\(\textsf{WE}\)). However, though they provided the first definition of \(\textsf{miABE}\), they only used it as a new pathway for achieving witness encryption, not as a notion with its own applications – in their definition, only the first encryptor has any input, since this suffices for \(\textsf{WE}\). They do not consider strong notions of security or provide any constructions of \(\textsf{miABE}\). They also defined the notion of non-trivially exponentially efficient witness encryption (\(\textsf{XWE}\)), where the encryption run-time is only required to be much smaller than the trivial \(2^m\) bound for NP relations with witness size m. They show how to construct such \(\textsf{XWE}\) schemes for all of NP with encryption run-time \(2^{m/2}\) using the single input \({\textsf{ABE}}\) by [28]. For encryption run-time \(2^{\gamma \cdot m}\), the term \(\gamma \) is denoted as compression factor, and they explicitly left open the problem of constructing \(\textsf{XWE}\) schemes with an improved compression factor.

Both \({\textsf{ABE}}\) and \({\textsf{PE}}\) can be captured as special cases of functional encryption [17, 48], which has been studied extensively, in both the single-input [16, 17, 28, 48] and multi-input setting [1,2,3,4, 7, 11, 23, 25, 27, 40, 50]. Recall that in functional encryption (\(\textsf{FE}\)), a secret key is associated with a function f, a ciphertext is associated with an input \(\textbf{x}\) and decryption allows to recover \(f(\textbf{x})\) and nothing else. It is easy to see that \({\textsf{PE}}\) and \({\textsf{ABE}}\) are both special cases of \(\textsf{FE}\) – in particular, both \({\textsf{PE}}\) and \({\textsf{ABE}}\) achieve the same functionality but restrict the security requirements of \(\textsf{FE}\). In \({\textsf{PE}}\), we ask that the attribute \(\textbf{x}\) be hidden but only when the adversary does not see any decrypting keys, namely \(f_i(\textbf{x})=0\) for all function keys \(f_i\) received by the adversary. On the other hand, in \(\textsf{FE}\), the attacker may request a key \(\textsf{sk}_f\), so long as f does not distinguish the challenge messages \((\textbf{x}_0, m_0), (\textbf{x}_1, m_1)\), namely, we may have \(f(\textbf{x}_0) = f(\textbf{x}_1) =1\) so long as \(m_0 = m_1\)Footnote 1. In the even weaker \({\textsf{ABE}}\), we do not ask any notion of hiding for \(\textbf{x}\), and this may be provided in the clear with the ciphertext.

Why not Functional Encryption? The informed reader may wonder what is the advantage of studying primitives like \(\textsf{miPE}\) or \(\textsf{miABE}\) when these are special cases of multi-input functional encryption (\({\textsf{miFE}}\)), which has recently been constructed from standard assumptions [11, 34]. It was shown by [11, 15] that \(\textsf{FE}\) satisfying a certain efficiency property (known as compactness) implies multi-input functional encryption, which in turn implies the powerful primitive of indistinguishability obfuscation (\(\textsf{iO}\)) [14]. A long line of exciting works endeavoured to construct compact \(\textsf{FE}\) (and hence \(\textsf{iO}\)) from standard assumptions [5, 12, 26, 33, 41,42,43], coming ever-closer, until the very recent work of Jain, Lin and Sahai closed the last remaining gap and achieved this much sought after goal [34, 35]. In [34, 35], the authors provide a construction for compact \(\textsf{FE}\), which in turn implies \({\textsf{miFE}}\) for polynomial arity (albeit with exponential loss in the reduction).

Going via the route of compact \(\textsf{FE}\), we obtain an exciting feasibility result for \({\textsf{miFE}}\) and hence \(\textsf{miABE}\) as well as \(\textsf{miPE}\). However, we argue that using something as strong as \({\textsf{miFE}}\) or \(\textsf{iO}\) to construct \(\textsf{miABE}\) and \(\textsf{miPE}\) is undesirable, and indeed an “overkill” for the following reasons:

  • Assumptions: Compact \(\textsf{FE}\) of [34] is constructed via a careful combination of 4 assumptions – Learning Parity with Noise (\(\textsf{LPN}\)), Learning With Errors (\(\textsf{LWE}\)), \(\textsf{SXDH}\) assumption on Pairings, and pseudorandom generators computable in constant depth. In the follow-up work of [35], this set of assumptions was trimmed to exclude \(\textsf{LWE}\). Therefore any construction built using compact \(\textsf{FE}\) must make at least this set of assumptions, which is restrictive. A major goal in the theory of cryptography is developing constructions from diverse assumptions.

  • Complexity: The construction of compact \(\textsf{FE}\) is extremely complex, comprising a series of careful steps, and this must then be lifted to \({\textsf{miFE}}\) using another complex construction [11]. Unlike \(\textsf{FE}\), both \({\textsf{PE}}\) and \({\textsf{ABE}}\) are much simpler, “all or nothing” primitives and permit direct constructions in the single-input setting [16, 28, 29]. Do we need the full complexity of an \({\textsf{miFE}}\) construction to get \(\textsf{miPE}\) or \(\textsf{miABE}\)? Indeed, even in the context of \({\textsf{miFE}}\), there is a large body of work that studies direct constructions for smaller function classes such as linear and quadratic functions [1,2,3,4, 7, 23, 25, 40, 50].

  • New Techniques: Finally and most importantly, we believe that it is extremely useful to develop new techniques for simpler primitives that are not known to be in obfustopia, and provide direct constructions. While direct constructions are likely to be more efficient, and are interesting in their own right, they may also lead to new pathways even for obfustopia primitives such as witness encryption or compact \(\textsf{FE}\). Note that the only known construction of \(\textsf{FE}\) from standard assumptions is by [34, 35], which makes crucial (and surprising) use of \(\textsf{LPN}\) in order to overcome a technical barrier – is \(\textsf{LPN}\) necessary for other primitives implied by compact \(\textsf{FE}\)? We believe that exploring new methods to construct weaker primitives is of central importance in developing better understanding of cryptographic assumptions, their power and limits.

1.1 Our Results

In this work, we initiate the study of multi-input predicate and attribute based encryption (\(\textsf{miABE}\) and \(\textsf{miPE}\)) and make the following contributions:

  1. 1.

    Formalizing Security: We provide definitions for \(\textsf{miABE}\) and \(\textsf{miPE}\) in the symmetric key setting and formalize two security notions in the standard indistinguishability (IND) paradigm, against unbounded collusions. The first (regular) notion of security assumes that the attacker does not receive any decrypting keys, as is standard in the case of \({\textsf{PE}}\)/\({\textsf{ABE}}\). The second strong notion, allows some decrypting queries in restricted settings.

  2. 2.

    Two-input \({\textsf{ABE}}\) for \({\textsf{NC}}_1\) from \(\textsf{LWE}\) and Pairings: We provide the first constructions for two-input key-policy \({\textsf{ABE}}\) for \({\textsf{NC}}_1\) from \(\textsf{LWE}\) and pairings. Our construction leverages a surprising connection between techniques recently developed by Agrawal and Yamada [10] in the context of succinct single-input ciphertext-policy \({\textsf{ABE}}\), to the seemingly unrelated problem of two-input key-policy \({\textsf{ABE}}\). Similarly to [10], our construction is proven secure in the bilinear generic group model. By leveraging inner product functional encryption and using (a variant of) the KOALA knowledge assumption, we obtain a construction in the standard model analogously to Agrawal, Wichs and Yamada [8].

  3. 3.

    Heuristic two-input \({\textsf{ABE}}\) for \(\textsf{P}\) from Lattices: We show that techniques developed for succinct single-input ciphertext-policy \({\textsf{ABE}}\) by Brakerski and Vaikuntanathan [21] can also be seen from the lens of \(\textsf{miABE}\) and obtain the first two-input key-policy \({\textsf{ABE}}\) from lattices for \(\textsf{P}\). Similarly to [21], this construction is heuristic.

  4. 4.

    Heuristic three-input \({\textsf{ABE}}\) and \({\textsf{PE}}\) for \({\textsf{NC}}_1\) from Pairings and Lattices: We obtain the first three-input \({\textsf{ABE}}\) for \({\textsf{NC}}_1\) by harnessing the powers of both the Agrawal-Yamada [10] and the Brakerski-Vaikuntanathan [21] constructions.

  5. 5.

    Multi-input \({\textsf{ABE}}\) to multi-input \({\textsf{PE}}\) via Lockable Obfuscation: We provide a generic compiler that lifts multi-input \({\textsf{ABE}}\) to multi-input \({\textsf{PE}}\) by relying on the hiding properties of Lockable Obfuscation (\(\textsf{LO}\)) by Wichs-Zirdelis and Goyal-Koppula-Waters (FOCS 2018), which can be based on \(\textsf{LWE}\). Our compiler generalises such a compiler for single-input setting to the much more challenging setting of multiple inputs. By instantiating our compiler with our new two and three-input \({\textsf{ABE}}\) schemes, we obtain the first constructions of two and three-input \({\textsf{PE}}\) schemes.

Our constructions of multi-input \({\textsf{ABE}}\) provide the first improvement to the compression factor (from 1/2 to 1/3 or 1/4) of non-trivially exponentially efficient Witness Encryption defined by Brakerski et al. [19] without relying on compact functional encryption or indistinguishability obfuscation. We believe that the unexpected connection between succinct single-input ciphertext-policy \({\textsf{ABE}}\) and multi-input key-policy \({\textsf{ABE}}\) may lead to a new pathway for witness encryption. We remark that our constructions provide the first candidates for a nontrivial class of \({\textsf{miFE}}\) without needing \(\textsf{LPN}\) or low depth \(\textsf{PRG}\).

1.2 Our Techniques

Modeling Multi-Input Attribute Based and Predicate Encryption. Our first contribution is to model multi-input attribute based encryption (\(\textsf{miABE}\)) and predicate encryption (\(\textsf{miPE}\)) as relevant primitives in their own right. To begin, we observe that similarly to multi-input functional encryption (\({\textsf{miFE}}\)) [27], these primitives are meaningful primarily in the symmetric key setting where the encryptor requires a secret key to compute a ciphertext. This is to prevent the primitive becoming trivial due to excessive leakage occurring by virtue of functionality. In more detail, let us say k encryptors compute an unbounded number ciphertexts in each slot, i.e. \(\{(\textbf{x}^j_1, m^j_1), \ldots (\textbf{x}^j_k, m^j_k)\}_{j \in [\textrm{poly}]}\) and the adversary obtains secret keys corresponding to functions \(\{f_i\}_{i \in [\textrm{poly}]}\). In the multi-input setting, ciphertexts across slots can be combined, allowing the adversary to compute \(f_i(\textbf{x}^{j_1}_1, \textbf{x}^{j_2}_2, \ldots , \textbf{x}^{j_k}_k)\) for any indices \(i, j_1, \ldots , j_k \in [\textrm{poly}]\). In the public key setting, an adversary can easily encrypt messages for various attributes of its choice and decrypt these with the challenge ciphertext in a given slot to learn a potentially unbounded amount of information. Due to this, we believe that the primitives of \(\textsf{miABE}\) and \(\textsf{miPE}\) are meaningful in the symmetric key setting where encryption also requires a secret key.

For security, we require the standard notion of ciphertext indistinguishability in the presence of collusion attacks, as in the single-input setting. Recall that in the single-input setting, the adversary cannot request any decrypting keys for challenge ciphertexts to prevent trivial attacks. However, since we are in the symmetric key setting where the adversary cannot encrypt herself, we propose an additional notion of strong security which also permits the adversary to request decrypting ciphertexts in some cases. In more detail, for the case of \(\textsf{miABE}\), our strong security game allows the attacker to request function keys for \(\{f_i\}_{i \in [\textrm{poly}]}\) and ciphertexts for tuples \(\{(\textbf{x}_{1}^{j}, m_{\beta ,1}^j),\ldots ,(\textbf{x}_{k}^{j}, m_{\beta ,k}^j)\}_{\beta \in \{0,1\},j \in [\textrm{poly}]}\) so that it may hold that \(f_i(\textbf{x}_{1}^{j_1}, \ldots , \textbf{x}_{k}^{j_k}) = 1\) for some \(i, j_1,\ldots , j_k\in [\textrm{poly}]\) as long as the challenge messages do not distinguish, i.e. \((m_{1,0}^{j_1} = m_{1,1}^{j_1}), \ldots , (m_{k,0}^{j_k} = m_{k,1}^{j_k})\). For the case of \(\textsf{miPE}\), we analogously define a strong version of security by asking that if \(f_i(\textbf{x}_{1,\beta }^{j_1}, \ldots , \textbf{x}_{k,\beta }^{j_k}) = 1\) holds for some \(i, j_1,\ldots , j_k\in [\textrm{poly}]\) and \(\beta \in \{0,1\}\), then it is also true that \((\textbf{x}_{1,0}^{j_1}, \ldots , \textbf{x}_{k,0}^{j_k}) = (\textbf{x}_{1,1}^{j_1}, \ldots , \textbf{x}_{k,1}^{j_k})\) and \((m_{1,0}^{j_1}, \ldots , m_{k,0}^{j_k}) = (m_{1,1}^{j_1}, \ldots , m_{k,1}^{j_k})\). For more details, please see Sect. 2.

Constructing Two Input \({\textsf{ABE}}\) from \(\textsf{LWE}\) and Bilinear GGM. In constructing two input \({\textsf{ABE}}\) (\(\textsf{2ABE}\)), the main difficulty is to satisfy two seemingly contradicting requirements at the same time: (1) the two ciphertexts should be created independently, (2) these ciphertexts should be combined in a way that decryption is possible. If we look at specific \({\textsf{ABE}}\) schemes (e.g., [16, 32]), it seems that these requirements cannot be satisfied simultaneously. If we want to satisfy the second requirement, the two ciphertexts should have common randomness. However to satisfy the first requirement, the randomness in the two ciphertexts needs to be sampled independently. An approach might be to fix the randomness and put it into the master secret key which is then used by both ciphertexts – but this will compromise security since fresh randomness is crucial in safeguarding semantic security.

Generating Joint Randomness: For resolving this problem, we consider a scheme that modifies two independently generated ciphertexts so that they have common randomness and then “joins” them. This common randomness is jointly generated using independently chosen randomness in each ciphertext by using a pairing operation. Specifically, we compute a ciphertext for slot 1 with randomness \(t_1\) and encode it in \(\mathbb {G}_1\) and similarly, for slot 2 with randomness \(t_2\) in \(\mathbb {G}_2\), where \(\mathbb {G}:\mathbb {G}_1 \times \mathbb {G}_2 \rightarrow \mathbb {G}_T\) is a pairing group with prime order q. Then, both ciphertexts may be combined to form a new ciphertext with respect to the randomness \(t_1t_2\) on \(\mathbb {G}_T\). This approach seems to be promising, because we can uniquely separate every pair of ciphertexts, since each pair (i, j) will have unique randomness \(t^i_1 t^j_2\). In the generic group model, this is sufficient to prohibit “mix and match” attacks that try to combine components of different ciphertexts in the same slot.

Moving Beyond Degree 2: However, since we “used up” the pairing operation here, it appears we cannot perform more than linear operations on the generated ciphertext, which would severely restrict the function class supported by our construction. In particular, pairing based \({\textsf{ABE}}\) schemes seem not to be compatible with the above approach, because these require additional multiplication in the exponent during decryption, which cannot be supported using a bilinear map. However, at this juncture, a trick suggested by Agrawal and Yamada [10] comes to our rescue – to combine lattice based \({\textsf{ABE}}\) with bilinear maps in a way that lets us get the “best of both”.

At a high level, the Agrawal-Yamada trick rests on the observation that in certain lattice based \({\textsf{ABE}}\) schemes [16, 30], decryption is structured as follows: (i) evaluate the circuit f on ciphertext encodings of \(\textbf{x}\), (ii) compute a matrix-vector product of the ciphertext matrix and secret key vector, (iii) perform a rounding operation to recover the message. Crucially, step (i) in the above description is in fact a linear operation over the encodings, even for circuits in \(\textsf{P}\), and the only nonlinear part of decryption is the rounding operation in step (iii). They observe that steps (i) and (ii) may be done “upstairs” in the exponent and step (iii) may be done “downstairs” by recovering the exponent brute force, when it is small enough. Importantly, the exponent is small enough when the circuit class is restricted to \({\textsf{NC}}_1\) using asymmetry in noise growth [28, 30]. While this idea was developed in the context of a single-input ciphertext-policy \({\textsf{ABE}}\), it appears to be exactly what we need for two-input key-policy \({\textsf{ABE}}\)!

Perspective: Connection to Broadcast Encryption: In hindsight, the application of optimal broadcast encryption requires succinctness of the ciphertext, which recent constructions [8, 10, 21] obtain by relying on the decomposability of specific \({\textsf{ABE}}\) schemes [16, 30] – this decomposability is also what the multi-input setting intrinsically requires, albeit for a different reason. In more detail, decomposability means that the ciphertext for a vector \(\textbf{x}\) can be decomposed into \(|\textbf{x}|\) ciphertext components each encoding a single bit \(\textbf{x}_i\), and these components can be tied together using common randomness to yield a complete ciphertext. The bit by bit encoding of the vector allows \(2|\textbf{x}|\) ciphertext components, each component encoding both bits for a given position, to together encode \(2^{|\textbf{x}|}\) possible values of \(\textbf{x}\), which leads to the succinctness of ciphertext in optimal broadcast encryption schemes [8, 10, 21]. In the setting of multi-input \({\textsf{ABE}}\), decomposability allows to morph independently generated full ciphertexts with distinct randomness to components of a single ciphertext with common randomness. The randomness is “merged” using pairings (or lattices, see below) and the resultant ciphertext can now be treated like the ciphertext of a single input scheme.

Adapting to the \(\textsf{2ABE}\) Setting: Let us recall the structure of the ciphertext in scheme of Boneh et al. [16], which is denoted as \(\textsf{BGG}^{\mathsf +}\) hereafter. As discussed above, a ciphertext for an attribute \(\textbf{x}\in [2\ell ]\)Footnote 2 in \(\textsf{BGG}^{\mathsf +}\) is generated by first generating \(\textsf{LWE}\) encodings (their exact structure is not important for this overview) for all possible values of the attribute \(\textbf{x}\), namely, \( \{ \psi _{i,b} \}_{i\in [2\ell ],b\in \{0,1\}} \) (along with other components which are not relevant here) and then selecting \( \{ \psi _{i,x_i} \}_{i\in [2\ell ]} \) based on \(\textbf{x}\), where \(x_i\) is the i-th bit of the attribute string \(\textbf{x}\).

Given the above structure, a candidate scheme works as follows. The setup algorithm computes encodings for all possible \(\textbf{x}\), namely \(\{ \psi _{i,b} \}_{i,b}\) and puts them into the master secret key. The encryptor for slot 1 chooses \(t_1 \leftarrow {\mathbb Z}_q\) and encodes \(( t_1, \{ t_1 \psi _{i,x_{1,i}} \}_{i\in [\ell ]} )\) in the exponent of \({\mathbb G}_1\). Similarly, the encryptor for slot 2 chooses \(t_2 \leftarrow {\mathbb Z}_q\) and encodes \(( t_2, \{ t_2 \psi _{i,x_{2,i-\ell }} \}_{i\in [\ell +1,2\ell ]} )\) in the exponent of \({\mathbb G}_2\). In decryption, we compute a pairing of matching components of the two ciphertexts to obtain \(( t_1 t_2, \{ t_1 t_2 \psi _{i,x_{i}} \}_{i\in [2\ell ]} )\) in the exponent of \({\mathbb G}_T\). Using the \(\textsf{BGG}^{\mathsf +}\) decryption procedure described above, we may perform linear operations to evaluate the circuit, apply the \(\textsf{BGG}^{\mathsf +}\) secret key and obtain the message plus noise in the exponent, which is brought “downstairs” by brute force to perform the rounding and recover the message.

Challenges in Proving Security. While the above sketch provides a construction template, security is far from obvious. Indeed, some thought reveals that the multi-input setting creates delicate attack scenarios that need care to handle. As an example, consider the strong security definition which allows the adversary to request ciphertexts that are decryptable by secret keys so long as they do not lead to a distinguishing attack. For simplicity, let us restrict to the setting where only the slot 1 ciphertext carries a message and slot 2 ciphertexts carry nothing except attributes (this restriction can be removed). Now, a slot 1 ciphertext may carry a message that depends on the challenger’s secret bit as long as it is not decryptable by any key. However, slot 2 ciphertexts may participate in decryption with other slot 1 ciphertexts that do not encode the challenge bit, and decryption can (and does) lead to randomness leakage of participating ciphertexts. When such a “leaky” slot 2 ciphertext is combined with the challenge slot 1 ciphertext for decryption, security breaks down.

For concreteness, let us consider the setting where the adversary makes slot 1 ciphertext queries for \((\textbf{x}_1, (m_0,m_1))\) and \((\textbf{x}'_1, (m'_0,m'_1))\) and slot 2 ciphertext query for \((\textbf{x}_2)\). Furthermore, the adversary makes a single key query for a circuit F such that \(F(\textbf{x}_1,\textbf{x}_2)=0\) (unauthorized) and \(F(\textbf{x}'_1,\textbf{x}_2)=1\) (authorized). Note that to prevent trivial attacks, we pose the restriction that \(m'_0= m'_1\), but we may have \(m_0\ne m_1\). In this setting, the \(\textsf{2ABE}\) construction described above is not secure since the noise associated with the slot 2 ciphertext for \(\textbf{x}_2\) leaks during decryption of the jointly generated ciphertext for \((\textbf{x}'_1,\textbf{x}_2)\) and this prevents using \(\textsf{BGG}^{\mathsf +}\) security for the pair \((\textbf{x}_1,\textbf{x}_2)\).

To resolve the above problem, we need to somehow “disconnect” randomness used in the challenge ciphertexts of slot 1 from randomness used in leaky/decrypting ciphertexts of other slots. This is tricky since the multi-input setting insists that ciphertexts be combined across slots in an unrestricted way. Fortunately, another technique developed [10] for a completely different reason comes to our assistance – we discontinue encoding the \(\textsf{BGG}^{\mathsf +}\) ciphertexts in \(\textsf{2ABE}\) ciphertexts for slot 2, so that even if a slot 2 ciphertext is decrypted, this does not affect the security of the \(\textsf{BGG}^{\mathsf +}\) encoding. Instead, we encode a binary “selection vector” in the exponent of \(\mathbb {G}_2\), which enables the decryptor to recover \(\psi _{2,x_{2,i}}\) when matching positions of slot 1 and slot 2 ciphertext components are paired. In the context of broadcast encryption (i.e. succinct ciphertext-policy \({\textsf{ABE}}\)) [10] this trick was developed because the key generator could not know the randomness used by the encryptor, and moreover this randomness is unbounded across unbounded ciphertexts. In our setting, this trick instead allows to break the leakage of correlated randomness caused by combining ciphertexts across different slots, some of which may be challenge ciphertexts and others of which may be decrypting ciphertexts. However, though we made progress we are still not done and the formal security argument still be required to address several issues – please see Sect. 3 for more details.

Constructing \(\textsf{2ABE}\) in the Standard Model. We next turn to adapting the construction to the standard model – a natural starting point is the standard model adaptation of [10] by Agrawal, Wichs and Yamada [8] which is based on a non-standard knowledge type assumption \(\textsf{KOALA}\) on bilinear groups. Our proof begins with these ideas but again departs significantly due to the nuanced security game of the multi-input setting – indeed, we will run into subtle technical issues related to the distribution of auxiliary information which will require us to formulate a variant of \(\textsf{KOALA}\).

We first outline our construction, which uses a version of inner product functional encryption (\(\textsf{IPFE}\)), where one can directly encrypt group elements (rather than \({\mathbb Z}_q\) elements) and can generate a secret key for group elements. Thus, a ciphertext may encrypt a vector \([\textbf{v}]_1\) and a secret key is for \([\textbf{w}]_2\) and the decryption result of the ciphertext using the secret key is \([\langle \textbf{v},\textbf{w}\rangle ]_T\). Using \(\textsf{IPFE}\) and ideas similar to our first construction discussed above, we encode vectors into ciphertexts and secret keys so that the decryption result ends up with the \(\textsf{BGG}^{\mathsf +}\) ciphertext randomized by a secret key specific randomness t. In more detail, a slot 1 ciphertext is an \(\textsf{IPFE}\) ciphertext encoding \([\textbf{v},0]_2\) and a slot 2 ciphertext is an \(\textsf{IPFE}\) secret key encoding \([t \textbf{w},0]_2\) so that \([t \langle \textbf{v},\textbf{w}\rangle ]_T\) is recovered upon decryption, which is a corresponding \(\textsf{BGG}^{\mathsf +}\) ciphertext randomized by t on the exponent. Here, the last 0 entries are used for the security proof. We note that compared to the solution in bilinear generic group model we explained, we dropped the randomness on the ciphertext encoding and only the secret key encoding is randomized by t. The reason why the randomness on the ciphertext encoding can be removed is that the encoding is already protected by the \(\textsf{IPFE}\) and this change allows to simplify the construction and proof.

In the security game, we will have \(\{ \textsf{ct}^{(i)} := \textsf{IPFE}.\textsf{Enc}( [ \textbf{v}^{(i)},0]_1 ) \}_i\) and \(\{ \textsf{sk}^{(i)} :=\textsf{IPFE}.\textsf{sk}( [t^{(i)}\textbf{w}^{(i)},0 ]_2 ) \}_i\), where \(\textsf{ct}^{(i)}\) is the i-th slot 1 ciphertext and \(\textsf{sk}^{(i)}\) is the i-th slot 2 ciphertext. Let us say that the adversary requests Q ciphertexts in each slot. The security proof is by hybrid argument, where slot 1 ciphertexts are changed from ciphertexts for challenge bit 0 to 1 one by one. Now, to change the message in a slot 1 ciphertext \(i^*\), we must account for its combination with all slot 2 ciphertexts – note that such a constraint does not arise in single input \({\textsf{ABE}}/\textsf{BE}\) [8]. To handle this, we leverage the power of \(\textsf{IPFE}\) so that the Q second slot ciphertexts hardcode the decryption value for the chosen slot 1 ciphertext \(i^*\) and behave as before with other slot 1 ciphertexts. A bit more explicitly, the j-th secret key may be hardwired with \(( [t^{(j)}]_2, [ t^{(j)} \textsf{BGG}^{\mathsf +}.\textsf{ct}^{(j)}]_2 )\), where \( \textsf{BGG}^{\mathsf +}.\textsf{ct}^{(j)} \) is a set of \(\textsf{BGG}^{\mathsf +}\) ciphertexts derived from \(\textbf{v}^{(i^\star )}\) and \(\textbf{w}^{(j)}\). We note that since \(\{ \textsf{BGG}^{\mathsf +}.\textsf{ct}^{(j)} \}_j\) are derived from the same vector \(\textbf{v}^{(i^\star )}\), their distribution is mutually correlated.

At this stage, we have a vector of \(\textsf{BGG}^{\mathsf +}\) ciphertexts encoded in the exponent, randomized with a unique random term \(t^{(j)}\) and would like to change the ciphertexts \(\textsf{BGG}^{\mathsf +}.\textsf{ct}^{(j)}\) into random strings using the security of \(\textsf{BGG}^{\mathsf +}\). A similar situation was dealt with by [8], who essentially showed that if \(\textsf{BGG}^{\mathsf +}.\textsf{ct}^{(j)}\) is individually pseudorandom given an auxiliary information \(\textsf{aux}\), then by a variant of the \(\textsf{KOALA}\) assumption, \(\{ [t^{(j)}]_2, [ t^{(j)} \textsf{BGG}^{\mathsf +}.\textsf{ct}^{(j)}]_2 \}_{j}\) looks pseudorandom, even if ciphertexts are mutually correlated for \(j \in [Q]\). However, this idea is insufficient for our setting due to the distribution of the auxiliary information. In more detail, for the construction of [8], it sufficed to have a single \(\textsf{BGG}^{\mathsf +}\) secret key in \(\textsf{aux}\), since their construction only needed a single key secure \(\textsf{BGG}^{\mathsf +}\). By applying a standard trick in lattice cryptography, they could sample the secret key first (setting other parameters accordingly) and thus regard \(\textsf{aux}\) as a random string. In contrast, our scheme crucially requires multiple \(\textsf{BGG}^{\mathsf +}\) secret keys, which can no longer be considered as random strings. This necessitates formulating a variant of the \(\textsf{KOALA}\) assumption whose distribution of the auxiliary input is structured rather than random. We do not know how to weaken this assumption using our current techniques and leave this improvement as an interesting open problem. For more details, please see full version of the paper [9, Sect. 5].

Compiling Multi-input \({\textsf{ABE}}\) to Multi-input \({\textsf{PE}}\). Next, we discuss how to lift k-input \(\textsf{miABE}\) to k-input \(\textsf{miPE}\). For the purposes of the introduction, let us focus on the case of \(k=2\). As a warm-up, we begin with the simpler setting of standard security, i.e. where there are no decrypting ciphertexts.

The natural first idea to construct \(\textsf{miPE}\) is to replace the single input \({\textsf{ABE}}\) \(\textsf{BGG}^{\mathsf +}\) in our \(\textsf{2ABE}\) scheme by single input \({\textsf{PE}}\), which has been constructed for all polynomial circuits by Gorbunov, Vaikuntanathan and Wee [29]. However, this idea quickly runs into an insurmountable hurdle – for our construction template, we need to bound the decryption noise by polynomial so that it can be recovered by brute force computation of discrete log in the final step. This is possible for \({\textsf{ABE}}\) supporting \({\textsf{NC}}_1\) using asymmetric noise growth [30]. In the context of \({\textsf{PE}}\) however, we do not know how to restrict the noise growth to polynomial – this is due to the usage of the fully homomorphic encryption in the scheme, which extends the depth of the evaluated circuit beyond what can be handled.

An alternative path to convert \({\textsf{ABE}}\) to \({\textsf{PE}}\) in the single input setting uses the machinery of Lockable Obfuscation (\(\textsf{LO}\)) [31, 53]. Lockable obfuscation allows to obfuscate a circuit C with respect to a lock value \(\beta \) and a message m. The obfuscated circuit on input x outputs m if \(C(x)=\beta \) and \(\bot \) otherwise. For security, \(\textsf{LO}\) requires that if \(\beta \) has high entropy in the view of the adversary, the obfuscated circuit should be indistinguishable from a garbage program that does not carry any information.

Single to Multiple Inputs. The conversion in the single input setting is as follows. To encrypt a message m for an attribute \(\textbf{x}\), we first encrypt a random value \(\beta \) using the \({\textsf{ABE}}\) to obtain an \({\textsf{ABE}}\) cipheretxt \(\textsf{ct}\). We then construct a circuit \(C[\textsf{ct}]\) that hardwires \(\textsf{ct}\) in it, takes as input an \({\textsf{ABE}}\) secret key and decrypts the hardwired ciphertext using it. We obfuscate \(C[\textsf{ct}]\) with respect to the lock value \(\beta \) and the message m. The final \({\textsf{PE}}\) ciphertext is the obfuscated circuit. It is easy to see that the \({\textsf{PE}}\) scheme has correctness, since if the decryption is possible, \(\beta \) is recovered inside the obfuscated circuit and the lock is unlocked. By the correctness of \(\textsf{LO}\), the message is revealed. In the security proof, we first change \(\beta \) encrypted inside \(\textsf{ct}\) to a zero string. This is possible using the security of \({\textsf{ABE}}\). Now the lock value \(\beta \) has high entropy from the view of the adversary. We then erase the information inside the obfuscated circuit, which includes the attribute information, using the security of \(\textsf{LO}\).

Some thought reveals that the above conversion breaks down completely in the multi-input setting. For instance, if we apply the above conversion to a slot 1 ciphertext, the resulting obfuscation expects to receive slot 2 ciphertext in the clear. However, a slot 2 ciphertext of \({\textsf{PE}}\) must also constitute an obfuscated circuit since otherwise the attribute associated with it will be leaked. But then there is no way to communicate between the two ciphertexts, both of which are obfuscated circuits!

To overcome this barrier, we develop a delicate nested approach which takes advantage of the fact that \(\textsf{LO}\) is powerful enough to handle general circuits. To restore communication between two ciphertexts while maintaining attribute privacy, we obfuscate a circuit for slot 1 that takes as input another obfuscated circuit for slot 2 and runs this inside itself. In more detail, the outer \(\textsf{LO}\) takes as input the “inner” \(\textsf{LO}\) circuit and the \(\textsf{2ABE}\) secret key \(\textsf{2ABE}.\textsf{sk}_f\). The inner \(\textsf{LO}\) instance encodes the circuit for \(\textsf{2ABE}\) decryption with the \(\textsf{LO}\) message as an \(\textsf{SKE}\) secret and the lock value as random tag \(\beta \). It also has hardcoded in it the slot 2 \(\textsf{2ABE}\) ciphertext \(\textsf{2ABE}.\textsf{ct}_2\) with message \(\beta \). The other piece of \(\textsf{2ABE}\), namely the slot 1 ciphertext \(\textsf{2ABE}.\textsf{ct}_1\) is hardwired in the outer \(\textsf{LO}\). The outer \(\textsf{LO}\) encodes a circuit which runs the inner \(\textsf{LO}\) on inputs \(\textsf{2ABE}.\textsf{ct}_1\) and \(\textsf{2ABE}.\textsf{sk}_f\). By correctness of the inner \(\textsf{LO}\), the \(\textsf{2ABE}\) decryption with \(\textsf{2ABE}.\textsf{ct}_1\), \(\textsf{2ABE}.\textsf{ct}_2\) and \(\textsf{2ABE}.\textsf{sk}_f\) is executed and if the functionality is satisfied, the inner \(\textsf{LO}\) outputs the \(\textsf{SKE}\) secret key. Thus, the \(\textsf{SKE}\) secret key signals whether the inner \(\textsf{LO}\) is unlocked, and if so, uses the recovered key to decrypt an \(\textsf{SKE}\) ciphertext which is hardcoded in the circuit. This ciphertext encrypts some random \(\gamma \) which is also set as the lock value of outer \(\textsf{LO}\). If the \(\textsf{SKE}\) decryption succeeds, the lock value matches the decrypted value and outputs the message m which is the message in the outer \(\textsf{LO}\). We note that the same \(\textsf{SKE}\) secret key must be used for both the inner and outer \(\textsf{LO}\) for them to effectively communicate.

Supporting Strong Security. This construction lends itself to a proof of security for the standard game where decrypting ciphertexts are not allowed, although via an intricate sequence of hybrids especially for the case of general k. We refer the reader to Sect. 4 for details and turn our attention to the far more challenging case of strong security. In the setting of strong security, the proof fails – note that once any slot 2 ciphertext is decrypted, we no longer have the guarantee that the message value of the inner obfuscation is hidden. Since this message is a secret key of an \(\textsf{SKE}\) scheme and is used to encrypt the lock values for slot 1 ciphertexts, security breaks down once more.

To overcome this hurdle, we must make the construction more complex so that the message value of the inner obfuscation is no longer a global secret and does not compromise security even if revealed. To implement this intuition, we let the inner obfuscation output a slot 2 (strong) \(\textsf{2ABE}\) ciphertext when the lock is unlocked, which is then used to perform \(\textsf{2ABE}\) decryption in the circuit of the outer \(\textsf{LO}\). Now, even if the security of a inner obfuscated circuit is compromised, this does not necessarily mean that the security of the entire system is compromised because of the guarantees of the strong security game of \(\textsf{2ABE}\). While oversimplified, this intuition may now be formalized into a proof. For more details, please see Sect. 5.

Constructing \(\textsf{3ABE}\) from Pairings and Lattices. Finally, we discuss our candidate construction for three input \({\textsf{ABE}}\) scheme based on techniques developed by Brakerski and Vaikuntanathan [21] in conjunction with our \(\textsf{2ABE}\) construction in Sect. 3. The work of Brakerski and Vaikuntanathan [21] provided a clever candidate for succinct ciphertext-policy \({\textsf{ABE}}\) for \(\textsf{P}\) from lattices. Their construction also uses decomposability in order to achieve succinctness which is the starting point for the multi-input setting as discussed above. Additionally, they provide novel ways to handle the lack of shared randomness between the key generator and encryptor – while [10] use pairings to generate shared randomness, [21] use lattice ideas and it is this part which makes their construction heuristic. Here, we show that the algebraic structure of their construction not only fits elegantly to the demands of the two-input setting, but can also be made compatible with our current \(\textsf{2ABE}\) construction to amplify arity to three! This surprising synergy between two completely different candidates of broadcast encryption, namely Agrawal-Yamada and Brakerski-Vaikuntanathan, created by decomposability and novel techniques of handling randomness, already provides an \(\textsf{XWE}\) of compression factor 1/4 as against the previous best known 1/2 [19], and may lead to other applications as well.

Recap of the Brakerski-Vaikuntanathan Construction. To dig deeper into our construction, let us first recap the core ideas of [21]. First recall the well known fact that security of \(\textsf{BGG}^{\mathsf +}\) encodings is lost when we have two encodings for the same position encoding a different bit, namely, \(\psi _{i,0}=\textbf{s}\textbf{B}_i + \textbf{e}_{i,0}\) and \(\psi _{i,1}=\textbf{s}(\textbf{B}_i +\textbf{G}) + \textbf{e}_{i,1}\), where \(\textbf{s}\) is a \(\textsf{LWE}\) secret, \(\textbf{B}_i\) is a matrix, and \(\textbf{e}_{1,b}\) is an error vector for \(b\in \{0,1\}\). What [21] suggested is, if we augment \(\textsf{BGG}^{\mathsf +}\) encodings and mask them appropriately, then both encodings can be published and still hope to be secure. Namely, they change \(\textsf{BGG}^{\mathsf +}\) encodings to be \(\psi _{i,b}=\textbf{S}(\textbf{B}_i +b\textbf{G}) + \textbf{E}_{i,b}\), where we replace the vector \(\textbf{s}\) with a matrix \(\textbf{S}\). They then mask the encodings by public (tall) matrices \(\{ \textbf{C}_{i,b} \}_{i,b}\) as

$$ \widehat{\psi }_{i,b}:= \textbf{C}_{i,b}\widehat{\textbf{S}}_{i,b} + \textbf{S}(\textbf{B}_i +b\textbf{G}) + \textbf{E}_{i,b} $$

where \(\{ \widehat{\textbf{S}}_{i,b} \}_{i,b}\) are random secret matrices. By releasing appropriate information, one can recover \(\textsf{BGG}^{\mathsf +}\) encodings with different \(\textsf{LWE}\) secrets. In more detail, we can publish a short vector \(\textbf{t}_\textbf{x}\) for any binary string \(\textbf{x}\) that satisfies \(\textbf{t}_\textbf{x}\textbf{C}_{i,x_i}=\textbf{0}\) (and \(\textbf{t}_\textbf{x}\textbf{C}_{i,1-x_i}\) is random) for all i. This allows us to compute

$$ \textbf{t}_\textbf{x}\left( \textbf{C}_{i,x_i} \widehat{\textbf{S}}_{i,x_i} + \textbf{S}(\textbf{B}_i +x_i\textbf{G}) + \textbf{E}_{i,x_i} \right) = \textbf{t}_\textbf{x}\textbf{S}(\textbf{B}_i +x_i \textbf{G}) + \textbf{t}_\textbf{x}\textbf{E}_{i,x_i } = \textbf{s}_\textbf{x}(\textbf{B}_i +x_i \textbf{G}) + \textbf{e}_{\textbf{x},i,x_i } $$

where we set \(\textbf{s}_\textbf{x}= {\textbf{t}}_\textbf{x}\textbf{S}\) and \( \textbf{e}_{\textbf{x},i,b} = \textbf{t}_\textbf{x}\textbf{E}_{i,b}\). Namely, we can obtain \(\textsf{BGG}^{\mathsf +}\) samples specific to the string \(\textbf{x}\). This is similar to the idea of using pairings to choose the appropriate encoding based on the attribute string, which is used in our two-input \({\textsf{ABE}}\) with strong security. Similarly to that case, the obtained encodings are randomized by the user specific randomness. One of the heuristic aspects of [21] is that in order for their scheme to be secure, we have to assume that there is no meaningful way to combine the \(\textsf{BGG}^{\mathsf +}\) samples obtained from different vectors \(\textbf{t}_\textbf{x}\) and \(\textbf{t}_{\textbf{x}'}\).

Let us now adapt these techniques to provide a construction of two-input \({\textsf{ABE}}\). In our candidate, \(\{ \textbf{B}_i \}_i\) and \(\{ \textbf{C}_{i,b} \}_{i,b}\) matrices are made public.Footnote 3 An encryptor for the slot 1 computes for \(i\in [\ell ], b\in \{0,1\}\):

$$ \left\{ \psi _{i,x_{1,i}}:= \textbf{S}(\textbf{B}_i +x_{1,i} \textbf{G}) + \textbf{E}_{i,x_{1,i}} \right\} _{i}, ~ \left\{ \widehat{\psi }_{i,b} := \textbf{C}_{\ell + i,b}\widehat{\textbf{S}}_{\ell + i,b} + \textbf{S}(\textbf{B}_{\ell +i} +b \textbf{G}) + \textbf{E}_{\ell +i,b} \right\} _{i, b} $$

where \(x_{1,i}\) denotes the i-th bit of the attribute \(\textbf{x}_1\) for slot 1, \(\ell \) denotes the length of an attribute, and \(\textbf{S}\) and \(\widehat{\textbf{S}}_{i,b}\) are freshly chosen by the encryptor. Intuitively, this is a partially stripped off version of the encodings in [21]. We believe this does not harm security, because the encryptor provides one out of two encodings for each position that is not masked by \(\textbf{C}_{i,b} \widehat{\textbf{S}}_{i,b}\). The encryptor for slot 2 generates a vector \(\textbf{t}_{\textbf{x}_2}\) such that \(\textbf{t}_{\textbf{x}_2} \textbf{C}_{i, x_{2,\ell + i}}=\textbf{0}\) for all \(i\in [\ell ]\). The secret key for function F is simply \(\textsf{BGG}^{\mathsf +}\) secret key for the same function. In the decryption, the decryptor uses \(\textbf{t}_{\textbf{x}_2}\) to choose \(\textsf{BGG}^{\mathsf +}\) encodings for attribute \(\textbf{x}_2\) from \(\{ \widehat{\psi }_{i,b} \}_{i,b}\). The obtained encodings are with respect to the \(\textsf{LWE}\) secret \(\textbf{t}_\textbf{x}\textbf{S}\). The decryptor can also choose \(\textsf{BGG}^{\mathsf +}\) encodings for attribute \(\textbf{x}_1\) from \(\{ {\psi }_{i} \}_{i}\). These obtained encodings constitutes a \(\textsf{BGG}^{\mathsf +}\) ciphertext for attribute \((\textbf{x}_1,\textbf{x}_2)\), which can be decrypted by the \(\textsf{BGG}^{\mathsf +}\) secret key. The intuition about security in [21] is that the \(\textsf{BGG}^{\mathsf +}\) encodings obtained by using \(\textbf{t}_\textbf{x}\) vectors cannot be combined in a meaningful way due to the different randomness.

Amplifying Arity. We now amplify arity by leveraging the above techniques in conjunction with our pairing based construction. Our idea is to develop the scheme so that the decryptor can recover the above partially stripped off version of the encoding in the exponent from slot 1 and slot 2 ciphertexts by using the pairing operations, where the encodings may be randomized. Then, slot 3 ciphertext corresponds to a vector \(\textbf{t}_{\textbf{x}_3}\), which annihilates \(\textbf{C}_{i,b}\) matrices for corresponding positions to the attribute \(\textbf{x}_3\). To do so, an encryptor for the first slot encodes

$$ \{ t_1 \psi _{i,x_i} \}_{i\in [\ell ]}, \quad \{ t_1 \psi _{i,b} \}_{i\in [\ell +1, 2\ell ] , b\in \{0,1\}}, \quad \{ t_1 \widehat{\psi _{i,b}} \}_{i\in [2\ell +1, 3\ell ], b\in \{0,1\}} $$

of the exponent of \(\mathbb {G}_1\), where \(t_1\) is freshly chosen randomness by the encryptor. An encryptor for the second slot encodes \(t_2,\; t_2 \textbf{d}_{\textbf{x}_2} \) in the exponent of \(\mathbb {G}_2\), where \(t_2\) is freshly chosen randomness by the encryptor and \(\textbf{d}_{\textbf{x}_2} \) is a selector vector that chooses \(\psi _{i,x_{2,i}}\) out of \((\psi _{i,0}, \psi _{i,1})\) by the pairing operation. Concretely, \(\textbf{d}_{\textbf{x}_2}= \{ d_{i,b} \}_{i,b}\), where \(d_{i,b}=1\) if \(b=x_{2,i}\) and 0 otherwise. These vectors are randomized by position-wise randomness as is the case for our other schemes. Finally, an encryptor for slot 3 with attribute \(\textbf{x}_3\) chooses \(\textbf{t}_{\textbf{x}_3}\) such that \(\textbf{t}_{\textbf{x}_3}\textbf{C}_{2\ell +i,x_{3,i}} = \textbf{0}\).

A somewhat worrying aspect of the candidate above may be that both \(t_1\psi _{i,0}\) and \(t_1\psi _{i,1}\) are encoded on \(\mathbb {G}_1\). However, this is also the case for [10] and as in that work, these two encodings are randomized by the position-wise randomness and cannot be combined in a meaningful way (at least in the GGM). The only way to combine them is to take a pairing product with \(\mathbb {G}_2\) elements. However, after the operation, we end up with partially stripped encoding that is randomized with \(t_1 t_2\). Therefore, a successful attack against the scheme may end up with attacking a partially stripped version of [21], which we expect to be as secure as the original scheme. Please see Sect. 6 for more details.

2 Multi-input Attribute Based and Predicate Encryption

We define multi-input Attribute Based Encryption (\({\textsf{ABE}}\)) and Predicate Encryption (PE) below. Since the only difference between the two notions is in the security game, we unify the syntax for the algorithms in what follows.

A k-input \({\textsf{ABE}}\)/PE scheme is parametrized over an attribute space \(\{(A_{\lambda })^k\}_{\lambda \in \mathbb {N}}\) and function space \(\{\mathcal{F}_\lambda \}_{\lambda \in \mathbb {N}}\), where each function maps \(\{(A_\lambda )^ k\}_{\lambda \in \mathbb {N}}\) to \(\{0, 1\}\). Such a scheme is described by procedures \((\textsf{Setup}, \textsf{KeyGen}, \textsf{Enc}_1,\ldots ,\) \(\textsf{Enc}_k, \textsf{Dec})\) with the following syntax:

  • \(\textsf{Setup}(1^\lambda )\rightarrow (\textsf{pp}, \textsf{msk})\): The \(\textsf{Setup}\) algorithm takes as input a security parameter and outputs some public parameters \(\textsf{pp}\) and a master secret key \(\textsf{msk}\).

  • \(\textsf{KeyGen}(\textsf{pp}, \textsf{msk}, f)\rightarrow \textsf{sk}_f\): The \(\textsf{KeyGen}\) algorithm takes as input the public parameters \(\textsf{pp}\), a master secret key \(\textsf{msk}\) and a function \(f \in \mathcal{F}_\lambda \) and outputs a key \(\textsf{sk}_f\).

  • \(\textsf{Enc}_1(\textsf{pp}, \textsf{msk}, \alpha , b )\rightarrow \textsf{ct}_{\alpha ,b, 1}\): The encryption algorithm for slot 1 takes as input the public parameters \(\textsf{pp}\), a master secret key \(\textsf{msk}\), an attribute \(\alpha \in A_\lambda \), and message \(b \in \{0, 1\}\), and outputs a ciphertext \(\textsf{ct}_{\alpha , b, 1}\). For the case of \(\textsf{ABE}\), the attribute string \(\alpha \) is included as part of the ciphertext.

  • \(\textsf{Enc}_i(\textsf{pp}, \textsf{msk}, \alpha )\rightarrow \textsf{ct}_{\alpha , i}\) for \(i\ge 2\): The encryption algorithm for the \(i^{th}\) slot where \(i \in [2,k]\), takes as input the public parameters \(\textsf{pp}\), a master secret key \(\textsf{msk}\), and an attribute \(\alpha \in A_\lambda \) and outputs a ciphertext \(\textsf{ct}_{\alpha , i}\). For the case of \(\textsf{ABE}\), the attribute string \(\alpha \) is included as part of the ciphertext.

  • \(\textsf{Dec}(\textsf{pp}, \textsf{sk}_f, \textsf{ct}_{\alpha _1, b, 1},\textsf{ct}_{\alpha _2, 2}, \ldots , \textsf{ct}_{\alpha _k, k})\rightarrow b'\): The decryption algorithm takes as input the public parameters \(\textsf{pp}\), a key for the function f and a sequence of ciphertext of \((\alpha _1, b),\alpha _2, \ldots , \alpha _k\) and outputs a string \(b'\).

Next, we define correctness and security. For ease of notation, we drop the subscript \(\lambda \) in what follows.

Correctness: For every \(\lambda \in \mathbb {N}, b \in \{0, 1\}\), \(\alpha _1, \ldots , \alpha _k \in A\), \(f \in \mathcal{F}\), it holds that if \(f(\alpha _1, \ldots , \alpha _k) = 1\), then

$$\begin{aligned} \Pr \left[ \begin{array}{c} \textsf{Dec}\left( \begin{array}{c} \textsf{pp}, \textsf{KeyGen}(\textsf{pp}, \textsf{msk}, f), \\ \textsf{Enc}_1(\textsf{pp}, \textsf{msk}, \alpha _1, b), \ldots , \textsf{Enc}_k(\textsf{pp}, \textsf{msk}, \alpha _k) \end{array} \right) = b \end{array}\right] = 1 - {{\,\textrm{negl}\,}}(\lambda ) \end{aligned}$$

where the probability is over the choice of \((\textsf{pp}, \textsf{msk})\leftarrow \textsf{Setup}(1^\lambda )\) and over the internal randomness of \(\textsf{KeyGen}\) and \(\textsf{Enc}_1,\ldots ,\textsf{Enc}_k\).

Definition 1

(\(\textsf{Ada}\text{- }\textsf{IND}\) security for \(\mathsf {k\text{- }ABE}\)). For a \(\mathsf {k\text{- }ABE}\) scheme \(\mathsf {k\text{- }ABE}=\{ \textsf{Setup}, \textsf{KeyGen}, \textsf{Enc}_1,\ldots , \textsf{Enc}_k, \textsf{Dec}\}\) for an attribute space \(\{(A_{\lambda })^k\}_{\lambda \in \mathbb {N}}\), function space \(\{\mathcal{F}_\lambda \}_{\lambda \in \mathbb {N}}\) and an adversary \(\mathcal {A}\), we define the \(\textsf{Ada}\text{- }\textsf{IND}\) security game as follows.

  1. 1.

    Setup phase: On input \(1^\lambda \), the challenger samples \((\textsf{pp}, \textsf{msk}) \leftarrow \textsf{Setup}(1^{\lambda })\) and gives \(\textsf{pp}\) to \(\mathcal {A}\).

  2. 2.

    Query phase: The challenger samples a bit \(\beta \leftarrow \{0,1\}\). During the game, \(\mathcal {A}\) adaptively makes the following queries, in an arbitrary order.

    1. (a)

      Key Queries: \(\mathcal {A}\) makes polynomial number of key queries, say \(p=p(\lambda )\). As an i-th key query, \(\mathcal {A}\) chooses a function \(f_i \in \mathcal{F}_\lambda \). The challenger replies with \(\textsf{sk}_{f_i} \leftarrow \textsf{KeyGen}(\textsf{pp}, \textsf{msk}, f_i)\).

    2. (b)

      Ciphertext Queries: \(\mathcal {A}\) issues polynomial number of ciphertext queries for each slot, say \(p=p(\lambda )\). As an i-th query for a slot \(j\in [k]\), \(\mathcal {A}\) declares

      $$ {\left\{ \begin{array}{ll} (\alpha ^i_j, (b^i_0,b^i_1)) &{}~\text {if}~j=1 \\ \alpha ^i_j&{}~\text {if}~j\ne 1 \end{array}\right. } $$

      to the challenger, where \(\alpha ^i_j\in A_\lambda \) is an attribute and \( (b^i_0,b^i_1)\in \{0,1\}\times \{0,1\}\) is the pair of messages. Then, the challenger computes

      $$ \textsf{ct}_{j,\beta }^{i} = {\left\{ \begin{array}{ll} \textsf{Enc}_j(\textsf{pp}, \textsf{msk}, \alpha ^{i}_{j}, b^i_{\beta } ) &{}~\text {if}~j=1 \\ \textsf{Enc}_j(\textsf{pp}, \textsf{msk}, \alpha ^{i}_{j}) &{}~\text {if}~j\ne 1 \end{array}\right. } $$

      and returns it to \(\mathcal {A}\).

  3. 3.

    Output phase: \(\mathcal {A}\) outputs a guess bit \(\beta '\) as the output of the experiment.

For the adversary to be admissible, we require that for every \(f_1, \ldots , f_p\in \mathcal{F}\), it holds that \(f_i(\alpha _1^{i_1}, \ldots , \alpha _k^{i_k}) = 0\) for every \(i, i_1, \ldots , i_k\in [p]\).

We define the advantage \(\textsf{Adv}^{\textsf{Ada}\text{- }\textsf{IND}}_{\mathsf {k\text{- }ABE}, \mathcal {A}}(1^\lambda )\) of \(\mathcal {A}\) in the above game as

$$ \textsf{Adv}^{\textsf{Ada}\text{- }\textsf{IND}}_{\mathsf {k\text{- }ABE}, \mathcal {A}}(1^\lambda ) := \left| \Pr [\textsf{Exp}_{\mathsf {k\text{- }ABE}, \mathcal {A}}(1^\lambda ) = 1 | \beta =0] - \Pr [\textsf{Exp}_{\mathsf {k\text{- }ABE}, \mathcal {A}}(1^\lambda ) = 1 | \beta =1]\right| . $$

The \(\mathsf {k\text{- }ABE}\) scheme \(\mathsf {k\text{- }ABE}\) is said to satisfy \(\textsf{Ada}\text{- }\textsf{IND}\) security (or simply adaptive security) if for any stateful PPT adversary \(\mathcal {A}\), there exists a negligible function \({{\,\textrm{negl}\,}}(\cdot ) \) such that \(\textsf{Adv}^{\textsf{Ada}\text{- }\textsf{IND}}_{\mathsf {k\text{- }ABE}, \mathcal {A}}(1^\lambda ) = {{\,\textrm{negl}\,}}(\lambda )\).

Definition 2

(\(\textsf{Ada}\text{- }\textsf{IND}\) security for k-\(\textsf{PE}\)). For an k-PE scheme \(\mathsf {k\text{- }PE}=\{ \textsf{Setup}, \textsf{KeyGen}, \textsf{Enc}_1,\ldots , \textsf{Enc}_k, \textsf{Dec}\}\) for an attribute space \(\{(A_{\lambda })^k\}_{\lambda \in \mathbb {N}}\), function space \(\{\mathcal{F}_\lambda \}_{\lambda \in \mathbb {N}}\) and an adversary \(\mathcal {A}\), we define the \(\textsf{Ada}\text{- }\textsf{IND}\) security game as follows.

  1. 1.

    Setup phase: On input \(1^\lambda \), the challenger samples \((\textsf{pp}, \textsf{msk}) \leftarrow \textsf{Setup}(1^{\lambda })\) and gives \(\textsf{pp}\) to \(\mathcal {A}\).

  2. 2.

    Query phase: The challenger samples a bit \(\beta \leftarrow \{0,1\}\). During the game, \(\mathcal {A}\) adaptively makes the following queries, in an arbitrary order.

    1. (a)

      Key Queries: \(\mathcal {A}\) makes polynomial number of key queries, say \(p=p(\lambda )\). For each key query \(i \in [p]\), \(\mathcal {A}\) chooses a function \(f_i \in \mathcal{F}_\lambda \). The challenger replies with \(\textsf{sk}_{f_i} \leftarrow \textsf{KeyGen}(\textsf{pp}, \textsf{msk}, f_i)\).

    2. (b)

      Ciphertext Queries: \(\mathcal {A}\) issues polynomial number of ciphertext queries for each slot, say \(p=p(\lambda )\). As an i-th query for a slot \(j\in [k]\), \(\mathcal {A}\) declares

      $$ {\left\{ \begin{array}{ll} ((\alpha ^i_{j,0}, \alpha ^i_{j,1}), (b^i_0,b^i_1)) &{}~\text {if}~j=1 \\ (\alpha ^i_{j,0}, \alpha ^i_{j,1}) &{}~\text {if}~j\ne 1 \end{array}\right. } $$

      to the challenger, where \((\alpha ^i_{j,0}, \alpha ^i_{j,1})\) is a pair of attributes and \( (b^i_0,b^i_1)\) is the pair of messages. Then, the challenger computes and returns to \(\mathcal{A}\)

      $$ \textsf{ct}_{j,\beta }^{i} = {\left\{ \begin{array}{ll} \textsf{Enc}_j(\textsf{pp}, \textsf{msk}, \alpha ^{i}_{j,\beta }, b^i_{\beta } ) &{}~\text {if}~j=1 \\ \textsf{Enc}_j(\textsf{pp}, \textsf{msk}, \alpha ^{i}_{j,\beta }) &{}~\text {if}~j\ne 1 \end{array}\right. } $$
  3. 3.

    Output phase: \(\mathcal {A}\) outputs a guess bit \(\beta '\) as the output of the experiment.

For the adversary to be admissible, we require that for every \(f_1, \ldots , f_p\in \mathcal{F}\), it holds that \(f_{i}(\alpha _{1, \beta }^{i_1}, \ldots , \alpha _{k, \beta }^{i_k}) = 0\) for every \(i, i_1, \ldots , i_k\in [p]\) and \(\beta \in \{0,1\}\).

We define the advantage \(\textsf{Adv}^{\textsf{Ada}\text{- }\textsf{IND}}_{\mathsf {k\text{- }PE}, \mathcal {A}}(1^\lambda )\) of \(\mathcal {A}\) in the above game as

$$ \textsf{Adv}^{\textsf{Ada}\text{- }\textsf{IND}}_{\mathsf {k\text{- }PE}, \mathcal {A}}(1^\lambda ) := \left| \Pr [\textsf{Exp}_{\mathsf {k\text{- }PE}, \mathcal {A}}(1^\lambda ) = 1 | \beta =0] - \Pr [\textsf{Exp}_{\mathsf {k\text{- }PE}, \mathcal {A}}(1^\lambda ) = 1 | \beta =1]\right| . $$

The k-PE scheme \(\mathsf {k\text{- }PE}\) is said to satisfy \(\textsf{Ada}\text{- }\textsf{IND}\) security (or simply adaptive security) if for any stateful PPT adversary \(\mathcal {A}\), there exists a negligible function \({{\,\textrm{negl}\,}}(\cdot ) \) such that \(\textsf{Adv}^{\textsf{Ada}\text{- }\textsf{IND}}_{\mathsf {k\text{- }PE}, \mathcal {A}}(1^\lambda ) = {{\,\textrm{negl}\,}}(\lambda )\).

2.1 Strong Security for \(\mathsf {k\text{- }ABE}\) and \(\mathsf {k\text{- }PE}\)

We also consider a stronger security notion for both \(\mathsf {k\text{- }ABE}\) as well as \(\mathsf {k\text{- }PE}\) where the adversary is allowed to make decrypting key requests for ciphertexts so long as they do not distinguish the challenge bit.

Definition 3

(Strong \(\textsf{Ada}\text{- }\textsf{IND}\) security for k-\(\textsf{ABE}\)). The definition for strong \(\textsf{Ada}\text{- }\textsf{IND}\) security for \(\mathsf {k\text{- }ABE}\) is the same as standard \(\textsf{Ada}\text{- }\textsf{IND}\) security (Definition 1) except for the following modification. For the \(\mathsf {k\text{- }ABE}\) adversary to be admissible in the strong \(\textsf{Ada}\text{- }\textsf{IND}\) game, we require that

  • If \(f_i(\alpha _{1}^{i_1}, \ldots , \alpha _{k}^{i_k}) = 1\) holds for some \(i, i_1,\ldots , i_k\in [p]\), then \(b_{0}^{i_1} = b_{1}^{i_1}\).

Let \((\alpha ^i, (b^i_0,b^i_1))\) be the \(i^{th}\) ciphertext query in slot 1. Then, if \(b^i_0 \ne b^i_1\), we call the ciphertext returned by the challenger as a challenge ciphertext as it encodes the challenge bit \(\beta \). Otherwise, we refer to it as decrypting ciphertext, as the adversary may potentially request a key to decrypt it.

Definition 4

(Strong \(\textsf{Ada}\text{- }\textsf{IND}\) security for k-\(\textsf{PE}\)). The definition for strong \(\textsf{Ada}\text{- }\textsf{IND}\) security for \(\mathsf {k\text{- }PE}\) is the same as standard \(\textsf{Ada}\text{- }\textsf{IND}\) security (Definition 2) except for the following modification. For the \(\mathsf {k\text{- }PE}\) adversary to be admissible in the strong \(\textsf{Ada}\text{- }\textsf{IND}\) game, we require that

  • If \(f_i(\alpha _{1,\beta }^{i_1}, \ldots , \alpha _{k,\beta }^{i_k}) = 1\) holds for some \(i, i_1,\ldots , i_k\in [p]\) and \(\beta \in \{0,1\}\), then \((\alpha _{1,0}^{i_1}, \ldots , \alpha _{k,0}^{i_k}) = (\alpha _{1,1}^{i_1}, \ldots , \alpha _{k,1}^{i_k})\) and \(b_{0}^{i_1} = b_{1}^{i_1} \).

Let \(\big ((\alpha ^i_0, \alpha ^i_1), (b^i_0, b^i_1)\big )\) be the \(i^{th}\) ciphertext query in slot 1. Then, if \(\alpha ^i_0 \ne \alpha ^i_1\) or \(b^i_0 \ne b^i_1\), we call the ciphertext returned by the challenger as a challenge ciphertext as it encodes the challenge bit \(\beta \). Otherwise, we refer to it as decrypting ciphertext, as the adversary may potentially request a key to decrypt it.

Definition 5

(Strong \(\textsf{VerSel}\text{- }\textsf{IND}\) security for k-\(\textsf{ABE}\) and k-\(\textsf{PE}\)). The definitions for strong \(\textsf{VerSel}\text{- }\textsf{IND}\) security for \(\mathsf {k\text{- }ABE}\) and \(\mathsf {k\text{- }PE}\) are the same as strong \(\textsf{Ada}\text{- }\textsf{IND}\) security above except that the adversary \(\mathcal {A}\) is required to submit the challenge queries and secret key queries to the challenger before it samples the public key.

2.2 Generalization to Multi-Slot Message Scheme

In the above, we focus our attention on \(\mathsf {k\text{- }ABE}\) and \(\mathsf {k\text{- }PE}\) schemes that only contain a message in a single slot, the remaining slots being free of messages. We can also consider a generalized version of the notions where each slot carries a message and all the messages are recovered in successful decryption. For k polynomial, it is easy to extend a construction with single slot message to the generalized version where each slot contains a message, simply by running k instances of the scheme in parallel and rotating the slot which contains the message in each instance to cover all k slots. Moreover we claim that since the k message scheme is a concatenation of k one message schemes, security of the latter implies security of the former. In more detail, suppose there exists an adversary against the k message scheme with non-negligible advantage \(\epsilon \). This can be used to construct an adversary against one of the underlying one message schemes with non-negligible advantage \(\epsilon /k\).

3 Two-Input ABE for \({\textsf{NC}}_1\) from Pairings and LWE

In this section, we construct two input \({\textsf{ABE}}\) for \({\textsf{NC}}_1\) circuits. More formally, our construction can support attribute space \(A_\lambda = \{0,1\}^{\ell (\lambda )}\), and any circuit class \(\mathcal{F}=\{ \mathcal{F}_\lambda \}_\lambda \) that is subclass of \(\{ \mathcal{C}_{2\ell (\lambda ), d(\lambda )} \}_\lambda \) with arbitrary \(\ell (\lambda ) \le \textrm{poly}(\lambda )\) and \(d(\lambda ) = O( \log \lambda )\), where \(\mathcal{C}_{2\ell (\lambda ), d(\lambda )}\) is a set of circuits with input length \(2\ell (\lambda )\) and depth at most \(d(\lambda )\). We can prove that the scheme satisfies strong security as per Definition 3 assuming LWE in bilinear generic group model. Since the intuition was described in Sect. 1, we proceed directly with the construction. We refer to the full version of the paper [9] for backgrounds on lattices and pairings respectively and for description of the \(\textsf{kpABE}\) scheme by Boneh et al. [16] on which our construction is based.

Construction. We proceed to describe our construction.

  • \(\textsf{Setup}(1^\lambda )\): On input \(1^\lambda \), the setup algorithm defines the parameters \(n=n(\lambda )\), \(m=m(\lambda )\), noise distribution \(\chi \) over \(\mathbb {Z}\), \(\tau _0=\tau _0(\lambda )\), \(\tau =\tau (\lambda )\), and \(B=B(\lambda )\) as specified for the \(\textsf{kpABE}\) scheme of Boneh et al. (pl. see [9, Sect. 2.5]). It samples a group description \(\mathbb {G}= (q, \mathbb {G}_1,\mathbb {G}_2,\mathbb {G}_T, e, [1]_1, [1]_2)\). Sets \(L := (3\ell + 1)m + 2\) and proceeds as follows.

    1. 1.

      Sample \(\textsf{BGG}^{\mathsf +}\) scheme:

      1. (a)

        Sample \((\textbf{A}, \textbf{A}_{\tau _0}^{-1})\leftarrow \textsf{TrapGen}(1^n, 1^m, q)\) such that \(\textbf{A}\in \mathbb {Z}_q^{n\times m}\).

      2. (b)

        Sample random matrix \( \textbf{B}=( \textbf{B}_1,\ldots , \textbf{B}_{2\ell } ) \leftarrow (\mathbb {Z}_q^{n\times m})^{2\ell }\) and a random vector \(\textbf{u}\leftarrow \mathbb {Z}_q^n \).

    2. 2.

      Sample \(\textbf{w}\leftarrow (\mathbb {Z}_q^*)^L\).

    3. 3.

      Output \(\textsf{pp}= (\textbf{A}, \textbf{B}, \textbf{u}),\;\;\;\textsf{msk}=\big ( \textbf{A}^{-1}_{\tau _0}, \textbf{w},\;[1]_1,\;[1]_2\big ).\)

  • \(\textsf{KeyGen}(\textsf{pp}, \textsf{msk}, F)\): Given input the public parameters \(\textsf{pp}\), master secret key \(\textsf{msk}\) and a circuit F, compute \(\textsf{BGG}^{\mathsf +}\) function key for circuit F as follows:

    1. 1.

      Compute \(\textbf{H}_F = \textsf{EvalF}( \textbf{B}, F )\) and \(\textbf{B}_F = \textbf{B}\textbf{H}_F\).

    2. 2.

      Compute \([ \textbf{A}\Vert \textbf{B}_F ]_\tau ^{-1}\) from \(\textbf{A}^{-1}_{\tau _0}\) and sample \(\textbf{r}\in \mathbb {Z}^{2m}\) as \( \textbf{r}^\top \leftarrow [ \textbf{A}\Vert \textbf{B}_F ]_\tau ^{-1} ( \textbf{u}^\top ) \).

    3. 3.

      Output the secret key \(\textsf{sk}_F := \textbf{r}\).

  • \(\textsf{Enc}_1(\textsf{pp}, \textsf{msk}, \textbf{x}_1, b)\): Given input the public parameters \(\textsf{pp}\), master secret key \(\textsf{msk}\), attribute vector \(\textbf{x}_1\), message bit b, encryption for slot 1 is defined as follows:

    1. 1.

      Sample LWE secret \(\textbf{s}\leftarrow \mathbb {Z}_q^n\) and noise terms \(e_{0} \leftarrow \chi \), \(\textbf{e}\leftarrow \chi ^m \), \(\textbf{e}_i, \textbf{e}_{\ell +i, b} \leftarrow \widetilde{\chi ^m}\) for \(i\in [\ell ], b\in \{0,1\}\), where \(\widetilde{\chi ^m}\) is defined as in [9, Sect. 2.4].

    2. 2.

      For \(i \in [\ell ]\), compute \( \psi _{i} := \textbf{s}(\textbf{B}_i-x_{1,i} \textbf{G})+\textbf{e}_{i}.\)

    3. 3.

      For \(i \in [\ell +1,2\ell ]\), \(b \in \{0,1\}\), compute \(\psi _{i,b} := \textbf{s}(\textbf{B}_i-b\textbf{G})+\textbf{e}_{i,b}.\)

    4. 4.

      Compute \(\psi _{2\ell +1} := \textbf{s}\textbf{A}+\textbf{e}\) and \(\psi _{2\ell +2} := \textbf{s}\textbf{u}^\top + e_{0}\).

    5. 5.

      Set \(\mu = \lceil \frac{q}{2} \rceil b\); \(\textbf{c}= ( 1, \{\psi _{i}\}_{i\in [\ell ]}, \{\psi _{i, b}\}_{i\in [\ell +1,2\ell ], b \in \{0,1\}}, \psi _{2\ell +1}, \psi _{2\ell +2} + \mu )\).

    6. 6.

      Sample \(t_1 \leftarrow \mathbb {Z}_q^*\) and output \(\textsf{ct}_1=[t_1\textbf{c}\odot \textbf{w}]_1\).

  • \(\textsf{Enc}_2(\textsf{pp}, \textsf{msk}, \textbf{x}_2)\): Given input the public parameters \(\textsf{pp}\), master secret key \(\textsf{msk}\), attribute vector \(\textbf{x}_2\), encryption for slot 2 is defined as follows:

    1. 1.

      Let \(\textbf{1}_a:= (1,\ldots ,1) \in \mathbb {Z}_q^{a}\) and \(\textbf{0}_a:= (0,\ldots ,0) \in \mathbb {Z}_q^{a}\). Set

      $$\begin{aligned} \hat{\psi }_{i,b} := {\left\{ \begin{array}{ll} \textbf{1}_m \in \mathbb {Z}_q^m &{} \text {if}~b=x_{2,i} \\ \textbf{0}_m \in \mathbb {Z}_q^m &{} \text {if}~b\ne x_{2,i} \end{array}\right. } \quad \text {for}~i\in [\ell +1, 2\ell ]~\text {and}~b\in \{0,1\}. \end{aligned}$$
    2. 2.

      Set \(\textbf{d}= ( 1, \textbf{1}_{\ell m}, \{\hat{\psi }_{i,b}\}_{i\in [\ell +1,2\ell ], b \in \{0,1\}}, \textbf{1}_m, 1 )\).

    3. 3.

      Sample \(t_2 \leftarrow \mathbb {Z}_q^*\) and output \(\textsf{ct}_2=[t_2\textbf{d}\oslash \textbf{w}]_2\).

  • \(\textsf{Dec}(\textsf{pp}, \textsf{sk}_F, \textsf{ct}_1, \textsf{ct}_2)\): The decryption algorithm takes as input the public parameters \(\textsf{pp}\), the secret key \(\textsf{sk}_F\) for circuit F and ciphertexts \(\textsf{ct}_1\) and \(\textsf{ct}_2\) corresponding to the two attributes \(\textbf{x}_1\) and \(\textbf{x}_2\) and proceeds as follows:

    1. 1.

      Take the coordinate-wise pairing between ciphertexts:

      Compute \([\textbf{v}]_T = [t_1t_2 \textbf{c}\odot \textbf{d}]_T\) as \(\textsf{ct}_1\odot \textsf{ct}_2\).

    2. 2.

      De-vectorize obtained vector:

      Expand \([\textbf{v}]_T\) for \(i \in [\ell ]\), \(j \in [\ell +1,2\ell ], b \in \{0,1\}\), to obtain:

      $$\begin{aligned}&[v_0]_T = [t_1 t_2]_T,\; [\textbf{v}_{i}]_T = [t_1 t_2 \psi _{i}]_T,\\ {}&[\textbf{v}_{j,b}]_T = [t_1 t_2 \psi '_{j,b}]_T,~\text {where}~ \psi '_{j,b} = {\left\{ \begin{array}{ll} \left( \textbf{s}( \textbf{B}_j - x_{2,j}\textbf{G}) + \textbf{e}_{j,b} \right) , &{} \text {if}~b=x_{2,j} \\ \textbf{0}, &{} \text {if}~b= 1- x_{2,j} \end{array}\right. },\\&[\textbf{v}_{2\ell +1}]_T = [t_1 t_2 \psi _{2\ell +1} ]_T,\; [v_{2\ell +2}]_T = [t_1 t_2 (\psi _{2\ell +2} +\mu )]_T.\; \end{aligned}$$
    3. 3.

      \(\underline{\text {Compute Evaluation function for}~\textsf{BGG}^{\mathsf +}~\text {ciphertexts in exponent:}}\)

      Let \(\textbf{x}=(\textbf{x}_1, \textbf{x}_2)\). Compute \(\widehat{\textbf{H}}_{F,\textbf{x}} = \textsf{EvalFX}( F, \textbf{x}, \textbf{B})\).

    4. 4.

      \(\underline{\text {Perform}~\textsf{BGG}^{\mathsf +}~\text {decryption in the exponent:}}\)

      Form \([ \textbf{v}_\textbf{x}]_T =[\textbf{v}_{1}, \ldots , \textbf{v}_{\ell }, \textbf{v}_{\ell +1, x_{2,1}}, \ldots \textbf{v}_{2\ell , x_{2,\ell }} ]_T \) and parse \(\textsf{sk}_F=\textbf{r}\) as \(\textbf{r}= (\textbf{r}_1 \in \mathbb {Z}_q^m , \textbf{r}_2 \in \mathbb {Z}_q^m )\). Then compute

      $$ [v']_T := [ (v_{2\ell +2}- \big (\textbf{v}_{2\ell +1}\textbf{r}_1^\top + \textbf{v}_\textbf{x}\widehat{\textbf{H}}_{F,\textbf{x}}\textbf{r}_2^\top ) \big ) ]_T $$
    5. 5.

      \(\underline{\text {Recover exponent via brute force if}~F(\textbf{x})=0}\):

      Find \(\eta \in [-B, B] \cup [-B + \lceil q/2 \rceil , B + \lceil q/2 \rceil ] \) such that \([v_0]_T^\eta = [v']_T\) by brute-force search. If there is no such \(\eta \), output \(\bot \). To speed up the operation, one can employ the baby-step giant-step algorithm.

    6. 6.

      Output 0 if \(\eta \in [-B, B]\) and 1 if \([-B + \lceil q/2 \rceil , B + \lceil q/2 \rceil ] \).

Correctness: Due to space constraints, we argue correctness in the full version [9, Sect. 4].

Proof of Security: We prove the security via the following theorem.

Theorem 1

Our \(\textsf{2ABE}\) scheme for function class \({\textsf{NC}}_1\) satisfies strong \(\textsf{Ada}\text{- }\textsf{IND}\) security in the generic group model assuming that the \(\textsf{kpABE}\) scheme \(\textsf{BGG}^{\mathsf +}\) for function class \({\textsf{NC}}_1\) satisfies \(\textsf{Ada}\text{- }\textsf{INDr}\) security (please see full version [9] for definition of \(\textsf{Ada}\text{- }\textsf{INDr}\) security).

The proof is provided in the full version of the paper [9, Sect. 4].

4 Compiling k-\({\textsf{ABE}}\) to k-\({\textsf{PE}}\) via Lockable Obfuscation

In this section we describe our compiler to lift k-input \({\textsf{ABE}}\) to k-input \({\textsf{PE}}\). Namely, we construct k-input predicate encryption using k-input \({\textsf{ABE}}\) and lockable obfuscation. The conversion preserves \(\textsf{Ada}\text{- }\textsf{IND}\) security. The extension of the conversion that preserves strong security is provided in Sect. 5.

Construction. Our construction uses the following building blocks:

  1. 1.

    A secret key encryption scheme \(\textsf{SKE}= (\textsf{SKE}.\textsf{Setup}, \textsf{SKE}.\textsf{Enc}, \textsf{SKE}.\textsf{Dec})\).

  2. 2.

    A Lockable Obfuscator \(\textsf{LO}= (\textsf{LO}.\textsf{Obf}, \textsf{LO}.\textsf{Eval})\) with lock space \(\mathcal {L} = \{0,1\}^{m}\) and input space \(\mathcal{X}= \{0,1\}^{n}\).

  3. 3.

    A k-input \({\textsf{ABE}}\) scheme \(\textsf{kABE}=(\textsf{kABE}.\textsf{Setup}, \textsf{kABE}.\textsf{KeyGen}, \textsf{kABE}.\textsf{Enc}_1, \ldots ,\) \(\textsf{kABE}.\textsf{Enc}_k, \textsf{kABE}.\textsf{Dec})\) in which the message bit is associated with the last slot, \(\textsf{kABE}.\textsf{Enc}_k\). We require \(k=O(1)\). In the construction below, we require the message space of the \(\textsf{SKE}\) scheme to be the same as the lock space \(\mathcal{L}\) of the lockable obfuscator scheme \(\textsf{LO}\) and the message space of \(\textsf{kABE}\) to be the same as the key space of \(\textsf{SKE}\).

We now describe the construction of k-input predicate encryption scheme. Our k-input \({\textsf{PE}}\) construction has the same attribute space and the function class as the underlying k-input \({\textsf{ABE}}\), when we consider the function class of \({\textsf{NC}}_1\) circuits or polynomial-size circuits.

  • \(\textsf{Setup}(1^\lambda ):\) On input the security parameter \(1^\lambda \), the \(\textsf{Setup}\) algorithm does the following:

    1. 1.

      Run \((\textsf{kABE}.\textsf{msk}, \textsf{kABE}.\textsf{pp})\leftarrow \textsf{kABE}.\textsf{Setup}(1^\lambda )\).

    2. 2.

      Run \(\textsf{SKE}.\textsf{Setup}(1^\lambda )\) k times and obtain secret keys \(K_1, K_2, \ldots , K_k\).

    3. 3.

      Output \(\textsf{msk}= (\textsf{kABE}.\textsf{msk}, K_1, \ldots , K_k)\) and \(\textsf{pp}= \textsf{kABE}.\textsf{pp}\).

  • \(\textsf{KeyGen}(\textsf{pp}, \textsf{msk}, F):\) On input the public parameters \(\textsf{pp}\), the master secret key \(\textsf{msk}= (\textsf{kABE}.\textsf{msk}, K_1, \ldots , K_k)\) and a circuit F, the \(\textsf{KeyGen}\) algorithm does the following:

    1. 1.

      Run \(\textsf{kABE}.\textsf{sk}_F\leftarrow \textsf{kABE}.\textsf{KeyGen}(\textsf{pp}, \textsf{kABE}.\textsf{msk}, F)\).

    2. 2.

      Output \(\textsf{sk}_F = \textsf{kABE}.\textsf{sk}_F\).

  • \(\textsf{Enc}_1(\textsf{pp}, \textsf{msk},\textbf{x}_1, m)\): On input the public parameters \(\textsf{pp}\), master secret key \(\textsf{msk}= (\textsf{kABE}.\textsf{msk}, K_1, \ldots , K_k)\), attribute \(\textbf{x}_1\) for position 1 and message m, the encryption algorithm does the following:

    1. 1.

      Sample \(\gamma _1\leftarrow \mathcal{L}\) and let \(\textsf{ct}_1^* = \textsf{SKE}.\textsf{Enc}(K_1, \gamma _1)\)

    2. 2.

      Compute \(\textsf{ct}_1 = \textsf{kABE}.\textsf{Enc}_1(\textsf{pp}, \textsf{kABE}.\textsf{msk}, \textbf{x}_1)\).

    3. 3.

      Define a function \(f_1[\textsf{ct}_1,\textsf{ct}_1^*]\) as in Fig. 1.

    4. 4.

      Output \(\textsf{ct}_1' = \textsf{LO}.\textsf{Obf}(1^\lambda , f_1[{\textsf{ct}_1,\textsf{ct}_1^*], m, \gamma _1})\).

  • \(\textsf{Enc}_i(\textsf{pp}, \textsf{msk},\textbf{x}_i)\) for \(2\le i \le k\): On input the public parameters \(\textsf{pp}\), master secret key \(\textsf{msk}=(\textsf{kABE}.\textsf{msk}, K_1, \ldots , K_k)\), attribute \(\textbf{x}_i\) for position i, the encryption algorithm does the following:

    1. 1.

      Sample a random value \(\gamma _i \leftarrow \mathcal{L}\) and let \(\textsf{ct}_i^* = \textsf{SKE}.\textsf{Enc}(K_i, \gamma _i)\).

    2. 2.

      Compute \(\textsf{ct}_i = {\left\{ \begin{array}{ll} \textsf{kABE}.\textsf{Enc}_i(\textsf{pp}, \textsf{kABE}.\textsf{msk}, \textbf{x}_i)&{}~\text {for}~ 2\le i < k \\ \textsf{kABE}.\textsf{Enc}_k(\textsf{pp}, \textsf{kABE}.\textsf{msk}, \textbf{x}_k, K_k)&{}~\text {for}~ i=k \end{array}\right. } \).

    3. 3.

      Define a function \(f_i[\textsf{ct}_i,\textsf{ct}_i^*]\) as in Fig. 1.

    4. 4.

      Output \(\textsf{ct}_i' = \textsf{LO}.\textsf{Obf}(1^\lambda , f_i[{\textsf{ct}_i,\textsf{ct}_i^*], K_{i-1}, \gamma _i})\).

  • \(\textsf{Dec}(\textsf{sk}_F, \textsf{ct}_1', \dots , \textsf{ct}_k'):\) On input the secret key \(\textsf{sk}_F\) for function F, and \(\textsf{kPE}\) ciphertexts \(\textsf{ct}_1', \ldots , \textsf{ct}_k'\), do the following:

    1. 1.

      Parse \(\textsf{ct}'_1\) as an \(\textsf{LO}\) obfuscation.

    2. 2.

      Compute and output \(\textsf{LO}.\textsf{Eval}(\textsf{ct}_1', (\textsf{ct}_2', \ldots , \textsf{ct}'_k, \textsf{sk}_F))\).

Fig. 1.
figure 1

Circuit Obfuscated by Slot i Encryption for \(1\le i \le k\)

Full size image

Correctness. Here, we briefly discuss the correctness of the scheme. For the full proof, we refer to the full version of the paper [9, Sect. 6]. If we run \(\textsf{LO}.\textsf{Eval}(\textsf{ct}_1', (\textsf{ct}_2', \ldots , \textsf{ct}'_k, \textsf{sk}_F))\), we end up with running the inner most obfuscation that obfuscates \(f_k[\textsf{ct}_k, \textsf{ct}^*_k]\) on input \((\textsf{ct}_1, \ldots , \textsf{ct}_{k-1}, \textsf{sk}_F)\). Within the circuit, \(K_k\) is retrieved by the \(\textsf{kABE}\) decryption and thus it recovers the lock value \(\gamma _k\), which unlocks the obfuscation. The circuit outputs \(K_{k-1}\) and this is then input to the second-innermost obfuscated circuit, which outputs \(K_{k-2}\) because of the similar reason. This process continues until the outermost circuit is unlocked and outputs the hardwired message m.

Security. We can prove that the above PE construction satisfies \(\textsf{Ada}\text{- }\textsf{IND}\) security if so does the underlying \(\textsf{kABE}\). We refer to the full version of the paper [9, Sect. 6] for the full proof. Here, we provide an intuition. First, we replace \(K_k\) encrypted in \(\textsf{kABE}.\textsf{Enc}_k\) with \(\textbf{0}\). This is possible by using the security of the underlying \(\textsf{kABE}\). Then, we can use the security of \(\textsf{SKE}\) to change all \(\textsf{ct}^*_k\) hardwired in the slot k ciphertexts, since \(K_k\) is not used except for the encrypting the lock value \(\gamma _k\) due to the change introduced in the previous step. This allows us to change the circuit \(\textsf{ct}'_k\) into a simulated one rather than honestly obfuscated one, since the lock value \(\gamma _k\) is erased in the previous step. This in particular erases \(K_{k-1}\), which allows to invoke the security of \(\textsf{SKE}\) to erase the lock value \(\gamma _{k-1}\). This process continues until we can convert \(\textsf{ct}'_1\) into a simulated circuit. At this point, every ciphertext is a simulated circuit and does not convey any information of attribute or message, as desired.

Applications. The conversion above can be applied to all the multi-input ABE schemes in this paper. Here, we focus on the applications to the candidate two input ABE scheme from lattices provided in the full version of the paper [9, Sect. 9] and the candidate three input ABE scheme in Sect. 6. The other schemes will be discussed in Sect. 5 because they satisfy strong (very selective) security and thus we can apply the conversion in Sect. 5. A nice property of the PE scheme obtained from the two input ABE scheme in [9, Sect. 9] is that it can handle any polynomial-size circuits. Besides, we can expect that it is post-quantum secure, because it does not use pairings and only uses lattice tools. By applying the conversion to the three input ABE scheme in Sect. 6, we can obtain a three-input \({\textsf{PE}}\) scheme that can handle \({\textsf{NC}}_1\) circuits.

5 Two-Input PE with Stronger Security

In this section we describe our compiler to lift 2-input \({\textsf{ABE}}\) to 2-input \({\textsf{PE}}\) that preserves strong security. The conversion uses lockable obfuscation similarly to Sect. 4. Unlike the conversion in Sect. 4, we do not know how to extend it to general arity k and it is set to be \(k=2\) here. It uses the following building blocks:

  1. 1.

    Two instances of 2-input \({\textsf{ABE}}\) scheme. In one instance the message is associated with encryption for position 2, while in the other instance, the message is associated with the encryption for position 1. We represent the two instances as \(\textsf{2ABE}= (\textsf{2ABE}.\textsf{Setup}, \textsf{2ABE}.\textsf{KeyGen}, \textsf{2ABE}.\textsf{Enc}_1, \textsf{2ABE}.\textsf{Enc}_2, \textsf{2ABE}.\textsf{Dec})\) and \(\textsf{2ABE}'=(\textsf{2ABE}'.\textsf{Setup}, \textsf{2ABE}'.\textsf{KeyGen}, \textsf{2ABE}'.\textsf{Enc}_1, \textsf{2ABE}'.\textsf{Enc}_2, \textsf{2ABE}'.\textsf{Dec})\).

  2. 2.

    A Lockable Obfuscator \(\textsf{Obf}= (\textsf{LO}.\textsf{Obf}, \textsf{LO}.\textsf{Eval})\).

Construction. Our two-input \({\textsf{PE}}\) construction has the same attribute space and the function class as the underlying two-input \({\textsf{ABE}}\), when we consider the function class of \({\textsf{NC}}_1\) circuits or polynomial-size circuits.

  • \(\textsf{Setup}(1^\lambda ):\) On input \(1^\lambda \), the \(\textsf{Setup}\) algorithm does the following:

    1. 1.

      Run \((\textsf{2ABE}.\textsf{msk}, \textsf{2ABE}.\textsf{pp})\leftarrow \textsf{2ABE}.\textsf{Setup}(1^\lambda )\) and \((\textsf{2ABE}'.\textsf{msk}, \textsf{2ABE}'.\textsf{pp})\leftarrow \textsf{2ABE}'.\textsf{Setup}(1^\lambda )\).

    2. 2.

      Output \(\textsf{msk}= (\textsf{2ABE}.\textsf{msk}, \textsf{2ABE}'.\textsf{msk})\) and \(\textsf{pp}= (\textsf{2ABE}.\textsf{pp}, \textsf{2ABE}'.\textsf{pp})\).

  • \(\textsf{KeyGen}(\textsf{pp}, \textsf{msk}, F):\) On input the public parameters \(\textsf{pp}\), the master secret key \(\textsf{msk}\) and a circuit F, the keygen algorithm does the following:

    1. 1.

      Parse \(\textsf{msk}\) as \((\textsf{2ABE}.\textsf{msk}, \textsf{2ABE}'.\textsf{msk})\) and \(\textsf{pp}= (\textsf{2ABE}.\textsf{pp}, \textsf{2ABE}'.\textsf{pp})\).

    2. 2.

      Run \(\textsf{2ABE}.\textsf{sk}_F\leftarrow \textsf{2ABE}.\textsf{KeyGen}(\textsf{2ABE}.\textsf{pp}, \textsf{2ABE}.\textsf{msk}, F)\) and \(\textsf{2ABE}'.\textsf{sk}_F\leftarrow \textsf{2ABE}'.\textsf{KeyGen}(\textsf{2ABE}'.\textsf{pp}, \textsf{2ABE}'.\textsf{msk}, F)\).

    3. 3.

      Output \(\textsf{sk}_F = (\textsf{2ABE}.\textsf{sk}_F, \textsf{2ABE}'.\textsf{sk}_F)\).

  • \(\textsf{Enc}_1(\textsf{pp}, \textsf{msk}, \textbf{x}_1, m)\): On input the public parameters, \(\textsf{pp}\), master secret key \(\textsf{msk}\), attribute \(\textbf{x}_1\) for position 1 and message m, the encryption algorithm does the following:

    1. 1.

      Parses \(\textsf{msk}\) as \((\textsf{2ABE}.\textsf{msk}, \textsf{2ABE}'.\textsf{msk})\) and \(\textsf{pp}\) as \((\textsf{2ABE}.\textsf{pp}, \textsf{2ABE}'.\textsf{pp})\).

    2. 2.

      Computes \(\textsf{ct}_1 = \textsf{2ABE}.\textsf{Enc}_1(\textsf{2ABE}.\textsf{pp}, \textsf{2ABE}.\textsf{msk}, \textbf{x}_1)\).

    3. 3.

      Sample \(\alpha \leftarrow \mathcal{M}\) and compute \(\textsf{ct}_1' = \textsf{2ABE}'.\textsf{Enc}_1(\textsf{2ABE}'.\textsf{pp},\)\( \textsf{2ABE}'.\textsf{msk}, \textbf{x}_1, \alpha )\).

    4. 4.

      Define a function \(f_1[{\textsf{ct}_1, \textsf{ct}_1'}]\), with \(\textsf{ct}_1, \textsf{ct}_1'\) being hardwired (Fig. 2).

    5. 5.

      Output \(\textsf{ct}_1'' = \textsf{LO}.\textsf{Obf}(1^\lambda , f_1[{\textsf{ct}_1, \textsf{ct}_1'}], m, \alpha )\).

  • \(\textsf{Enc}_2(\textsf{pp}, \textsf{msk}, \textbf{x}_2)\):

    1. 1.

      Parse \(\textsf{msk}\) as \((\textsf{2ABE}.\textsf{msk}, \textsf{2ABE}'.\textsf{msk})\) and \(\textsf{pp}\) as \((\textsf{2ABE}.\textsf{pp}, \textsf{2ABE}'.\textsf{pp})\).

    2. 2.

      Compute \(\textsf{ct}_2 = \textsf{2ABE}.\textsf{Enc}_2(\textsf{2ABE}.\textsf{pp}, \textsf{2ABE}.\textsf{msk}, \textbf{x}_2, \beta )\), where \(\beta \leftarrow \mathcal{M}\).

    3. 3.

      Compute \(\textsf{ct}_2' = \textsf{2ABE}.\textsf{Enc}_2'(\textsf{2ABE}'.\textsf{pp}, \textsf{2ABE}'.\textsf{msk}, \textbf{x}_2)\).

    4. 4.

      Define a function \(f_2[{\textsf{ct}_2}]\), with \(\textsf{ct}_2\) being hardwired, as in Fig. 3.

    5. 5.

      Output \(\textsf{ct}_2'' = \textsf{LO}.\textsf{Obf}(1^\lambda , f_2[{\textsf{ct}_2}], \textsf{ct}_2', \beta )\).

  • \(\textsf{Dec}(\textsf{sk}_F, \textsf{ct}_1'', \textsf{ct}_2''):\) On input the secret key \(\textsf{sk}_F\) for function F, and \(\textsf{2PE}\) ciphertexts \(\textsf{ct}_1''\) and \(\textsf{ct}_2''\), do the following:

    1. 1.

      Parse \(\textsf{sk}_F\) as \((\textsf{2ABE}.\textsf{sk}_F, \textsf{2ABE}'.\textsf{sk}_F)\) .

    2. 2.

      Output \(\textsf{LO}.\textsf{Eval}(\textsf{ct}_1'', (\textsf{ct}_2'', \textsf{2ABE}.\textsf{sk}_F, \textsf{2ABE}'.\textsf{sk}_F)\).

Fig. 2.
figure 2

Circuit Obfuscated by Slot 1 Encryption

Full size image
Fig. 3.
figure 3

Circuit Obfuscated by Slot 2 Encryption

Full size image

Correctness. Recall that \(\textsf{ct}_1'' = \textsf{LO}.\textsf{Obf}(1^\lambda , f_1[{\textsf{ct}_1, \textsf{ct}_1'}], m, \alpha )\). We claim that

$$f_1[{\textsf{ct}_1, \textsf{ct}_1'}](\textsf{ct}_2'', \textsf{2ABE}.\textsf{sk}_F, \textsf{2ABE}'.\textsf{sk}_F) = \alpha .$$

This may be argued via the following steps:

  1. 1.

    Recall that \(\textsf{ct}_2'' = \textsf{LO}.\textsf{Obf}(1^\lambda , f_2[{\textsf{ct}_2}], \textsf{ct}_2', \beta )\) and \(f_2[{\textsf{ct}_2}](\textsf{ct}_1, \textsf{2ABE}.\textsf{sk}_F ) = \textsf{2ABE}.\textsf{Dec}(\textsf{2ABE}.\textsf{pp}, \textsf{2ABE}.\textsf{sk}_F, \textsf{ct}_1, \textsf{ct}_2) = \beta \). The second equality follows by correctness of \(\textsf{2ABE}\) and the fact that \(\textsf{ct}_1\) and \(\textsf{ct}_2\) encrypt \(\beta \) under attributes \(\textbf{x}_1, \textbf{x}_2\). Since \(\textsf{ct}_2''\) has lock value \(\beta \) and message value \(\textsf{ct}_2'\), we have by correctness of \(\textsf{LO}\) that \(\textsf{LO}.\textsf{Eval}( \textsf{ct}_2'', (\textsf{ct}_1, \textsf{2ABE}.\textsf{sk}_F) )= \textsf{ct}_2'\).

  2. 2.

    Next, following the description of \(f_1[{\textsf{ct}_1, \textsf{ct}_1'}]\) (Fig. 2), we evaluate \(\textsf{2ABE}'.\textsf{Dec}\) \((\textsf{2ABE}'.\textsf{sk}_F, \textsf{ct}_1', \textsf{ct}_2')\) and recover \(\alpha \) by correctness of \(\textsf{2ABE}'\) decryption and the construction of \(\textsf{ct}_1'\) and \(\textsf{ct}_2'\) as encryptions of \(\alpha \) under attributes \(\textbf{x}_1, \textbf{x}_2\).

Thus, we get that \(f_1[{\textsf{ct}_1, \textsf{ct}_1'}](\textsf{ct}_2'', \textsf{2ABE}.\textsf{sk}_F, \textsf{2ABE}'.\textsf{sk}_F) = \alpha \). Now, by correctness of \(\textsf{LO}\), we have that \(\textsf{LO}.\textsf{Eval}(\textsf{ct}_1'', (\textsf{ct}_2'', \textsf{2ABE}.\textsf{sk}_F, \textsf{2ABE}'.\textsf{sk}_F)) = m\) as desired. This concludes the proof.

Security. We prove security via the following theorem.

Theorem 2

Assume \(\textsf{LO}\) is a secure lockable obfuscation scheme as per Definition 2.9 in [9] and that \(\textsf{2ABE}\) and \(\textsf{2ABE}'\) are secure two input \({\textsf{ABE}}\) schemes satisfying strong security as in Definition 3 (resp., strong very selective security as in Definition 5). Then, the \(\textsf{2PE}\) construction presented above satisfies strong security as per Definition 4 (resp., strong very selective security as in Definition 5).

Due to space constraints, the proof is provided in the full version [9, Sect. 7].

Applications. By applying the above conversion to two input ABE scheme with strong security in Sect. 3, we obtain a candidate construction of two input PE scheme with strong security. A caveat here is that the resulting scheme cannot necessarily be proven secure under \(\textsf{LWE}\) in the bilinear generic group model as one might expect. The problem here is that our conversion uses the decryption algorithm of the underlying two input ABE scheme in a non-black box way, which especially uses the code of the group operations. To claim the security of the resulting scheme, we heuristically assume that the two-input ABE scheme in Sect. 3 is strongly secure even in the standard model if we implement the bilinear generic group model with concrete well-chosen bilinear group and then apply the above conversion. We note that this kind of heuristic instantiation is widely used in the context of cryptographic hash functions and bilinear maps. We also mention that we can apply the above conversion to the two input ABE scheme in standard model provided in the full version [9, Sect. 5]. Since the scheme is proven secure in the standard model, the construction does not suffer from the above problem.

6 Three-Input ABE from Pairings and Lattices

In this section, we provide a candidate construction for \(\textsf{3ABE}\) using the structure of [21] and [10] as discussed in Sect. 1. Leveraging ideas from the Brakerski-Vaikuntanathan construction [21], we also obtain a candidate for \(\textsf{2ABE}\) for \(\textsf{P}\) – due to space constraints, we provide this construction in the full version [9]. Our \(\textsf{3ABE}\) scheme supports \({\textsf{NC}}_1\) circuits. More formally, it supports attribute space \(A_\lambda = \{0,1\}^{\ell (\lambda )}\) and any circuit class \(\mathcal{F}=\{ \mathcal{F}_\lambda \}_\lambda \) that is subclass of \(\{ \mathcal{C}_{3\ell (\lambda ), d(\lambda )} \}_\lambda \) with arbitrary \(\ell (\lambda ) \le \textrm{poly}(\lambda )\) and \(d(\lambda ) = O( \log \lambda )\), where \(\mathcal{C}_{3\ell (\lambda ), d(\lambda )}\) is a set of circuits with input length \(3\ell (\lambda )\) and depth at most \(d(\lambda )\).

  • \(\textsf{Setup}(1^\lambda )\): On input \(1^\lambda \), the setup algorithm defines the parameters \(n=n(\lambda )\), \(m=m(\lambda )\), \(k=k(\lambda )\), noise distribution \(\chi \), \(\hat{\chi }\) over \(\mathbb {Z}\), \(\tau _0 = \tau _0(\lambda )\), \(\tau = \tau (\lambda )\), \(\tau _0'= \tau _0'(\lambda )\), \(\tau _t= \tau _t(\lambda )\) and \(B=B(\lambda )\) as specified later. It samples a group description \(\mathbb {G}= (q, \mathbb {G}_1,\mathbb {G}_2,\mathbb {G}_T, e, [1]_1, [1]_2)\). It then sets \(L := (5\ell + 1)m+1\) and proceeds as follows.

    1. 1.

      Samples \(\textsf{BGG}^{\mathsf +}\) scheme:

      1. (a)

        Samples \((\textbf{A}, \textbf{A}_{\tau _0}^{-1})\leftarrow \textsf{TrapGen}(1^n, 1^m, q)\) such that \(\textbf{A}\in \mathbb {Z}_q^{n\times m}\).

      2. (b)

        Samples random matrix \( \textbf{B}=( \textbf{B}_1,\ldots , \textbf{B}_{3\ell } ) \leftarrow (\mathbb {Z}_q^{n\times m})^{3\ell }\) and a random vector \(\textbf{u}\leftarrow \mathbb {Z}_q^{n}\).

    2. 2.

      Samples \(w_0\leftarrow \mathbb {Z}_q^*\), \(\textbf{W}\leftarrow (\mathbb {Z}_q^*)^{k\times L}\).

    3. 3.

      Samples \(\textsf{BV}\) scheme:

      1. (a)

        Samples \(\textbf{C}\) along with its trapdoor \(\textbf{C}_{\tau _0'}^{-1}\) as

        \((\textbf{C}, \textbf{C}_{\tau _0'}^{-1})\leftarrow \textsf{TrapGen}(1^{2(\ell +1) n}, 1^k, q), \, \, \text {where}\)

        \(\textbf{C}^\top = (\textbf{C}_{2\ell +1,0}\Vert \textbf{C}_{2\ell +1,1}\Vert \ldots \Vert \textbf{C}_{3\ell , 0}\Vert \textbf{C}_{3\ell ,1}\Vert \textbf{C}_{3\ell +1}\Vert \textbf{C}_{3\ell +2})\in (\mathbb {Z}_q^{k\times n})^{2(\ell +1)}.\)

    4. 4.

      Outputs \(\textsf{pp}= (\textbf{A}, \textbf{B}, \textbf{C}, \textbf{u}), \, \, \textsf{msk}=\left( \;\textbf{A}_{\tau _0}^{-1}, \textbf{C}_{\tau _0'}^{-1}, w_0, \textbf{W}\;\right) .\)

  • \(\textsf{KeyGen}(\textsf{pp}, \textsf{msk}, F)\): On input the public parameters \(\textsf{pp}\), master secret key \(\textsf{msk}\) and a circuit F, compute \(\textsf{BGG}^{\mathsf +}\) function key for circuit F as follows:

    1. 1.

      Compute \(\textbf{H}_F = \textsf{EvalF}( \textbf{B}, F )\) and \(\textbf{B}_F = \textbf{B}\textbf{H}_F\).

    2. 2.

      Compute \([ \textbf{A}\Vert \textbf{B}_F ]_\tau ^{-1}\) from \(\textbf{A}^{-1}_{\tau _0}\) and sample \(\textbf{r}\in \mathbb {Z}^{2m}\) as \( \textbf{r}^\top \leftarrow [ \textbf{A}\Vert \textbf{B}_F ]_\tau ^{-1} ( \textbf{u}^\top ) \).

    3. 3.

      Output the secret key \(\textsf{sk}_F := \textbf{r}\).

  • \(\textsf{Enc}_1(\textsf{pp}, \textsf{msk}, \textbf{x}_1, \mu )\): On input the public parameters \(\textsf{pp}\), master secret key \(\textsf{msk}\), attribute vector \(\textbf{x}_1\), message bit \(\mu \), encryption for slot 1 is defined as follows:

    1. 1.

      Set \(\textbf{m}= \lceil \frac{q}{K} \rceil \mu (1, \ldots , 1)\in \mathbb {Z}_q^k\). We define \(K=2\tau _t\sqrt{n} k\). .

    2. 2.

      Samples LWE secret \(\textbf{S}\leftarrow \mathbb {Z}_q^{k\times n}\) and error terms \(\textbf{e}_{0} \leftarrow \chi ^k\), \(\textbf{E}\leftarrow \chi ^{k\times m}\), \(\textbf{E}_{i, x_{1,i}}\leftarrow \hat{\chi }^{k\times m}\), for \(i\in [\ell ]\), \(\textbf{E}_{i,b} \leftarrow \hat{\chi }^{k\times m} \), for \(i\in [\ell +1, 3\ell ]\), \(b\in \{0,1\}\).

    3. 3.

      For \(i \in [\ell ]\), computes \(\psi _{i,x_{1,i}} := \textbf{S}(\textbf{B}_i-x_{1,i}\textbf{G})+\textbf{E}_{i,x_{1,i}} \in \mathbb {Z}_q^{k \times m}.\)

    4. 4.

      For \(i \in [\ell +1, 3\ell ]\), \(b \in \{0,1\}\), computes \(\psi _{i,b} := \textbf{S}(\textbf{B}_i-b\textbf{G})+\textbf{E}_{i,b} \in \mathbb {Z}_q^{k \times m}.\)

    5. 5.

      Computes \(\psi _{3\ell +1} := \textbf{S}\textbf{A}+\textbf{E}\in \mathbb {Z}_q^{k\times m}\) and \(\psi _{3\ell +2}^\top := \textbf{S}\textbf{u}^\top + \textbf{e}_{0}^\top \in \mathbb {Z}_q^{k\times 1}\).

    6. 6.

      Sample \(\widehat{\textbf{S}}_{3\ell +1}\leftarrow \mathbb {Z}_q^{n\times m}\), \(\widehat{\textbf{s}}_{3\ell +2}\leftarrow \mathbb {Z}_q^{n}\), \(\{\widehat{\textbf{S}}_{2\ell +i, b}\}_{i\in [\ell ], b\in \{0,1\}}\leftarrow (\mathbb {Z}_q^{n\times m})^{2\ell }\), \(\widehat{\textbf{E}}\leftarrow \chi ^{k\times m}\),  \(\widehat{\textbf{e}}_{0} \leftarrow \chi ^{k}\),   \(\widehat{\textbf{E}}_{2\ell +i,b}\leftarrow \hat{\chi }^{k\times m}\) for \(i\in [\ell ], b\in \{0,1\}\).

    7. 7.

      Compute all possible “\(\textsf{BV}\) encodings” for slot 3 attribute \(\textbf{x}_3\) and construct \(\widehat{\textbf{C}}_1\) as follows:

      \(\widehat{\textbf{C}}_1 = ( \{\psi _{i, x_{1i}}\}_{i\in [\ell ]}\), \(\{\psi _{i,b}\}_{\begin{array}{c} i\in [\ell +1, 2\ell ],\\ b\in \{0,1\} \end{array}}\), \(\{\textbf{C}_{i,b}\widehat{\textbf{S}}_{i,b}\) + \(\widehat{\textbf{E}}_{i, b}\)+ \(\psi _{i,b}\}_{\begin{array}{c} i\in [2\ell +1, 3\ell ],\\ b\in \{0,1\} \end{array}}\),

      \(~~~~~~~~~~~~~~~~~~~\textbf{C}_{3\ell +1}\widehat{\textbf{S}}_{3\ell +1}+\widehat{\textbf{E}} +\psi _{3\ell +1}, \textbf{C}_{3\ell +2}\widehat{\textbf{s}}_{3\ell +2}^\top +\widehat{\textbf{e}}_0^\top +\psi _{3\ell +2}^\top + \textbf{m}^\top ) \in \mathbb {Z}_q^{k \times L}\).

      Here, we assume that the entries of \(\widehat{\textbf{C}}_1\) are vectorized in some fixed order.

    8. 8.

      Sample \(t_{\textbf{x}_1} \leftarrow \mathbb {Z}_q^*\) and output \(\textsf{ct}_1=([t_{\textbf{x}_1} w_0]_1, [t_{\textbf{x}_1}\widehat{\textbf{C}}_1\odot \textbf{W}]_1\).

  • \(\textsf{Enc}_2(\textsf{pp}, \textsf{msk}, \textbf{x}_2)\): On input the public parameters \(\textsf{pp}\), master secret key \(\textsf{msk}\), attribute vector \(\textbf{x}_2\), encryption for slot 2 is defined as follows:

    1. 1.

      Set \(\widehat{\textbf{C}}_2 = ( \textbf{1}_{k\times \ell m}, \{\hat{\psi }_{\ell +i, x_{2,i}}\}_{i\in [\ell ]}, \textbf{1}_{k\times 2\ell m}, \textbf{1}_{k\times m}, \textbf{1}_{k\times 1} )\), where

      $$\begin{aligned} \hat{\psi }_{\ell +i,b} := {\left\{ \begin{array}{ll} \textbf{1}_m \in \mathbb {Z}_q^m &{} \text {if}~b=x_{2,i} \\ \textbf{0}_m \in \mathbb {Z}_q^m &{} \text {if}~b\ne x_{2,i} \end{array}\right. } \quad \text {for}~i\in [\ell ]~\text {and}~b\in \{0,1\}. \end{aligned}$$
    2. 2.

      Sample \(t_{\textbf{x}_2} \leftarrow \mathbb {Z}_q^*\) and output \(\textsf{ct}_2=([t_{\textbf{x}_2}/ w_0]_2, [t_{\textbf{x}_2}\widehat{\textbf{C}}_2\oslash \textbf{W}]_2\).

  • \(\textsf{Enc}_3(\textsf{pp}, \textsf{msk}, \textbf{x}_3)\): Given input the public parameters \(\textsf{pp}\), master secret key \(\textsf{msk}\), attribute vector \(\textbf{x}_3\), encryption for slot 3 is defined as follows:

    1. 1.

      Compute \([(\textbf{C}_{2\ell +1, \textbf{x}_{3,1}}\Vert \ldots \Vert \textbf{C}_{3\ell , \textbf{x}_{3,\ell }}\Vert \textbf{C}_{3\ell +1}\Vert \textbf{C}_{3\ell +2})^\top ]^{-1}_{\tau _t}\) from \(\textbf{C}^{-1}_{\tau _0'}\) and sample short vector \({\textbf{t}}_{\textbf{x}_3}\) such that

      \({\textbf{t}}_{\textbf{x}_3} \textbf{C}_{2\ell +i, \textbf{x}_{3,i}} = \textbf{0} \text{ for } \text{ all } i\in [\ell ], \, {\textbf{t}}_{\textbf{x}_3} \textbf{C}_{3\ell +1}= {\textbf{t}}_{\textbf{x}_3} \textbf{C}_{3\ell +2} = \textbf{0}\), as

      \({\textbf{t}}_{\textbf{x}_3}^\top \leftarrow [(\textbf{C}_{2\ell +1, \textbf{x}_{3,1}}\Vert \ldots \Vert \textbf{C}_{3\ell , \textbf{x}_{3,\ell }}\Vert \textbf{C}_{3\ell +1}\Vert \textbf{C}_{3\ell +2})^\top ]^{-1}_{\tau _t}(\textbf{0}^\top ). \)

    2. 2.

      Output \(\textsf{ct}_3 = {\textbf{t}}_{\textbf{x}_3}\).

  • \(\textsf{Dec}(\textsf{pp}, \textsf{sk}_F, \textsf{ct}_1, \textsf{ct}_2, \textsf{ct}_3)\): On input the public parameters \(\textsf{pp}\), the secret key \(\textsf{sk}_F\) for circuit F and ciphertexts \(\textsf{ct}_1\), \(\textsf{ct}_2\) and \(\textsf{ct}_3\) corresponding to the three attributes \(\textbf{x}_1\), \(\textbf{x}_2\) and \(\textbf{x}_3\), the decryption algorithm proceeds as follows:

    1. 1.

      Takes the coordinate-wise pairing between ciphertexts for slot 1 and slot 2:

      Computes \([v_0]_T = [t_{\textbf{x}_1} t_{\textbf{x}_2}]_T\) and \([\textbf{V}]_T = [t_{\textbf{x}_1}t_{\textbf{x}_2} \widehat{\textbf{C}}_1\odot \widehat{\textbf{C}}_2]_T\) as \(e(\textsf{ct}_1, \textsf{ct}_2)\).

    2. 2.

      Expands obtained matrix:

      Let \(\textbf{x}=(\textbf{x}_1, \textbf{x}_2, \textbf{x}_3)\). Expands \([\textbf{V}]_T\) to obtain:

      \([\textbf{V}_{i}]_T = [t_{\textbf{x}_1} t_{\textbf{x}_2} \psi _{i, x_i}]_T ~ \text{ for } i\in [\ell ]\), \([\textbf{V}_{i, b}]_T = [t_{\textbf{x}_1} t_{\textbf{x}_2} \psi '_{i, b}]_T\), where

      \(\psi '_{i,b} = {\left\{ \begin{array}{ll} \psi _{i, x_i} &{} \text{ if } b = x_i\\ \textbf{0}&{} \text{ if } b = 1-x_i \end{array}\right. }, \text{ for } i\in [\ell +1, 2\ell ], b\in \{0,1\}.\)

      $$\begin{aligned}&[\textbf{V}_{i, b}]_T = [t_{\textbf{x}_1} t_{\textbf{x}_2} (\psi _{i, b}+\textbf{C}_{i,b}\widehat{\textbf{S}}_{i,b}+\widehat{\textbf{E}}_{i, b})]_T~ \text{ for } i\in [2\ell +1, 3\ell ], b\in \{0,1\},\\&[\textbf{V}_{3\ell +1}]_T = [t_{\textbf{x}_1} t_{\textbf{x}_2} (\textbf{C}_{3\ell +1}\widehat{\textbf{S}}_{3\ell +1}+\widehat{\textbf{E}}+\psi _{3\ell +1}) ]_T,\\&[\textbf{v}_{3\ell +2}^\top ]_T = [t_{\textbf{x}_1} t_{\textbf{x}_2} (\textbf{C}_{3\ell +2}\widehat{\textbf{s}}_{3\ell +2}^\top +\widehat{\textbf{e}}_0^\top +\psi _{3\ell +2}^\top +\textbf{m}^\top )]_T. \end{aligned}$$
    3. 3.

      \(\underline{\text {Recovers}~\textsf{BGG}^{\mathsf +}~\text {ciphertext components for third slot:}}\) Let us denote \(\textbf{V}_{i,x_i}\) as \(\textbf{V}_{i}\) for \(i\in [2\ell +1, 3\ell ]\).

      Computes \([{\textbf{t}}_{\textbf{x}_3} \textbf{V}_{i}]_T = [t_{\textbf{x}_1} t_{\textbf{x}_2} {\textbf{t}}_{\textbf{x}_3} (\psi _{i,x_i}+\widehat{\textbf{E}}_{i, x_i})]_T\) for \(i\in [2\ell +1, 3\ell ]\),

      \([{\textbf{t}}_{\textbf{x}_3}\textbf{V}_{3\ell +1}]_T = [t_{\textbf{x}_1} t_{\textbf{x}_2} {\textbf{t}}_{\textbf{x}_3} (\psi _{3\ell +1}+\widehat{\textbf{E}})]_T\) and \([{\textbf{t}}_{\textbf{x}_3}\textbf{v}_{3\ell +2}^\top ]_T =\)\( [t_{\textbf{x}_1} t_{\textbf{x}_2}{\textbf{t}}_{\textbf{x}_3} (\psi _{3\ell +2}^\top +\textbf{m}^\top +\widehat{\textbf{e}}_0^\top )]_T\).

      (because \({\textbf{t}}_{\textbf{x}_3}\textbf{C}_{i,x_i} = \textbf{0}\) for \(i\in [2\ell +1, 3\ell ]\), \({\textbf{t}}_{\textbf{x}_3}\textbf{C}_{3\ell +1} = {\textbf{t}}_{\textbf{x}_3}\textbf{C}_{3\ell +2} = \textbf{0}\))

    4. 4.

      \(\underline{\text {Computes function to be applied on}~\textsf{BGG}^{\mathsf +}~\text {ciphertexts:}}\)

      Computes \(\widehat{\textbf{H}}_{F,\textbf{x}} = \textsf{EvalFX}( F, \textbf{x}, \textbf{B})\).

    5. 5.

      \(\underline{\text {Performs}~\textsf{BGG}^{\mathsf +}~\text {decryption in the exponent:}}\)

      1. (a)

        Let us denote \(\textbf{V}_{i, x_i}\) as \(\textbf{V}_i\) for \(i\in [\ell +1, 2\ell ]\).

      2. (b)

        Computes \([{\textbf{t}}_{\textbf{x}_3}\textbf{V}_i]_T\) for \(i\in [2\ell ]\).

      3. (c)

        Forms \([ {\textbf{t}}_{\textbf{x}_3}\textbf{V}_\textbf{x}]_T =[{\textbf{t}}_{\textbf{x}_3}\textbf{V}_{1}\Vert \ldots \Vert {\textbf{t}}_{\textbf{x}_3}\textbf{V}_{3\ell } ]_T \), \(\textbf{r}= (\textbf{r}_1 \in \mathbb {Z}_q^m , \textbf{r}_2 \in \mathbb {Z}_q^m )\).

      4. (d)

        Then computes

        \(\left[ v'\right] _T := \left[ \left( {\textbf{t}}_{\textbf{x}_3}\textbf{v}_{3\ell +2}^\top - \left( {\textbf{t}}_{\textbf{x}_3}\textbf{V}_{3\ell +1} \textbf{r}_1^\top + {\textbf{t}}_{\textbf{x}_3}\textbf{V}_\textbf{x}\widehat{\textbf{H}}_{F,\textbf{x}}\textbf{r}_2^\top \right) \right) \right] _T\)

    6. 6.

      \(\underline{\text {Recover exponent via brute force if}~F(\textbf{x})=0}\):

      After simplification, for \(F(\textbf{x}) = 0\), we get \(v' = t_{\textbf{x}_1}t_{\textbf{x}_2}({\textbf{t}}_{\textbf{x}_3}\textbf{m}^\top + e')\), where \(e'\) is the combined error. Find \(\eta \in [-B, B] \cup [-B - \lceil q/2 \rceil , B - \lceil q/K \rceil ] \cup [-B + \lceil q/K \rceil , B + \lceil q/2 \rceil ]\) such that \([v_0]_T^\eta = [v']_T\) by brute-force search. If there is no such \(\eta \), output \(\bot \). In the correctness, we show that \(\eta \) can be found in polynomial steps. To speed up the operation, one can employ the baby-step giant-step algorithm.

    7. 7.

      Output 0 if \(\eta \in [-B, B]\) and 1, otherwise.

Parameters and Correctness: We choose the parameters for the 3-\({\textsf{ABE}}\) scheme as follows (pl. refer to the full version [9] for definition of \(\textsf{SampZ}\)):

$$\begin{aligned} m&= n^{1.1} \log q,&k&= \theta (n\ell \log q) ,&q&= 2^{ \varTheta ( \lambda ) } \\ \tau _0&= n\log q \log {m},&\tau&= m^{3.1} \ell \cdot 2^{O(d)}&\tau _0'&= \omega (\sqrt{2n(\ell +1)\log q \log k}), \\ \chi&= \textsf{SampZ}(3\sqrt{n}) ,&\hat{\chi }&= \textsf{SampZ}(6 \sqrt{n} m^2),&B&= \ell m^5 n^{3}k \tau \tau _t\cdot 2^{O(d)}. \end{aligned}$$

We can set \(\tau _t\) to be arbitrary polynomial such that \(\tau _t > \tau _0'\). The parameter n may be chosen as \(n = \lambda ^{c} \) for some constant \(c>1\).

We argue correctness in the full version of the paper [9, Sect. 8].