Non-trivial Witness Encryption and Null-iO from Standard Assumptions

A witness encryption (WE) scheme can take any \({{\textsf {NP}}}\) statement as a public-key and use it to encrypt a message. If the statement is true then it is possible to decrypt the message given a corresponding witness, but if the statement is false then the message is computationally hidden. Ideally, the encryption procedure should run in polynomial time, but it is also meaningful to define a weaker notion, which we call non-trivially exponentially efficient WE (XWE), where the encryption run-time is only required to be much smaller than the trivial \(2^{m}\) bound for \({{\textsf {NP}}}\) relations with witness size m. We show how to construct such XWE schemes for all of \({{\textsf {NP}}}\) with encryption run-time \(2^{m/2}\) under the sub-exponential learning with errors (LWE) assumption. For \({{\textsf {NP}}}\) relations that can be verified in \({{\textsf {NC}}^1}\) (e.g., SAT) we can also construct such XWE schemes under the sub-exponential Decisional Bilinear Diffie-Hellman (DBDH) assumption. Although we find the result surprising, it follows via a very simple connection to attribute-based encryption.

We also show how to upgrade the above results to get non-trivially exponentially efficient indistinguishability obfuscation for null circuits (niO), which guarantees that the obfuscations of any two circuits that always output 0 are indistinguishable. In particular, under the LWE assumptions we get a XniO scheme where the obfuscation time is \(2^{n/2}\) for all circuits with input size n. It is known that in the case of indistinguishability obfuscation (iO) for all circuits, non-trivially efficient XiO schemes imply fully efficient iO schemes (Lin et al., PKC ’16) but it remains as a fascinating open problem whether any such connection exists for WE or niO.

Lastly, we explore a potential approach toward constructing fully efficient WE and niO schemes via multi-input ABE.

1. 1.

   One difference is that XiO only restricts the size of the obfuscated programs but not the run-time of the obfuscation procedure, while XWE and XniO also restricts the run-time of the encryption and obfuscation procedures (which then implicitly restricts the size of the ciphertexts and obfuscated programs). This is important since, without restricting the run-time, trivial WE and niO constructions can achieve short ciphertext and obfuscated program sizes.

2. 2.

   Notice that in the RAM model, decryption is very efficient as it requires accessing only one key and one ciphertext.

3. 3.

   The property that in the RAM model our decryption is very efficient is common to all of our results. We only state it here and avoid repeating it in the other results.

4. 4.

   Recall that a scheme with short functional keys has the property that the size of a functional key for a function of size s and depth d is \(\mathsf {poly}(d,\lambda )\) for some fixed polynomial function \(\mathsf {poly}\).

We thank Nir Bitansky for many initial discussions on the topics of this work. We thank Antigoni Polychroniadou and Hoeteck Wee for their helpful comments on a previous version of our work. We also thank the anonymous reviewers for their remarks.

Authors and Affiliations

1. Weizmann Institute of Science, 76100, Rehovot, Israel

   Zvika Brakerski

2. UCLA, Los Angeles, CA, 90095, USA

   Aayush Jain & Alain Passelègue

3. Cornell Tech, New York, NY, 10044, USA

   Ilan Komargodski

4. Northeastern University, Boston, 02115, USA

   Daniel Wichs

Corresponding author

Correspondence to Ilan Komargodski .

Editors and Affiliations

1. University of Catania, Catania, Italy

   Dario Catalano

2. University of Salerno, Fisciano, Italy

   Roberto De Prisco

A Multi-input ABE and Non-trivial Witness Encryption

In this section, we introduce the notion of multi-input attribute based encryption and show that, in the most general setting, it implies witness encryption for \({{\textsf {NP}}}\).

Recall that in a standard ABE scheme, one can encrypt a message b relative to some attribute \(\alpha \) to get \(\mathsf {ct}_{\alpha ,b}\) and independently generate keys for Boolean functions f to get \(\mathsf {sk}_f\). Together, \(\mathsf {ct}_{\alpha ,b}\) and \(\mathsf {sk}_f\) can be used to recover b if \(f(\alpha ) = 1\), and otherwise, b should remain computationally hidden. We extend this notion to the multi-input setting. Here f takes as input a sequence of attributes \(\alpha _1,\dots ,\alpha _k\) for \(k \ge 1\) and the encryption functionality takes an additional parameter \(i\in [k]\) (it ignores b for \(i\ne 1\)). Given ciphertexts \(\mathsf {ct}_{\alpha _1,b},\mathsf {ct}_{\alpha _2,\cdot },\dots ,\mathsf {ct}_{\alpha _k}\) and a key \(\mathsf {sk}_f\) for such a function, one is able to recover b if \(f(\alpha _1,\dots ,\alpha _k)=1\) while it should remain hidden if \(f(\alpha _1,\dots ,\alpha _k)=0\). Details follow.

A k-input ABE scheme is parametrized over an attribute space \(\mathcal {X}=\{\mathcal {X}_{\lambda }\}_{\lambda \in \mathbb {N}}\) and function space \(\{\mathcal {F}_{\lambda }\}_{\lambda \in \mathbb {N}}\), where each function maps \(\mathcal {X}=\{(\mathcal {X}_{\lambda })^k\}_{\lambda \in \mathbb {N}}\) to \(\{ 0,1 \}\). Such a scheme is described by four procedures \((\mathsf {Setup}, \mathsf {KG}, \mathsf {Enc}, \mathsf {Dec})\) with the following syntax:

1. 1.

   \(\mathsf {Setup}(1^\lambda )\) gets as input a security parameter and outputs a master secret key \(\mathsf {msk}\).

2. 2.

   \(\mathsf {KG}(\mathsf {msk}, f)\) gets as input a master secret key \(\mathsf {msk}\) and a function \(f\in \mathcal {F}_\lambda \) and outputs a key \(\mathsf {sk}_f\).

3. 3.

   \(\mathsf {Enc}(\mathsf {msk}, \alpha , b,i)\) gets as input a master secret key \(\mathsf {msk}\), an attribute \(\alpha \in \mathcal {X}_\lambda \) and a message \(b\in \{ 0,1 \}\) and an index \(i\in [k]\), and outputs a ciphertext \(\mathsf {ct}_{\alpha ,b,i}\).

4. 4.

   \(\mathsf {Dec}(\mathsf {sk}_f, \mathsf {ct}_{\alpha _1,b_1,1},\dots ,\mathsf {ct}_{\alpha _k,b_k,k})\) gets as input a key for the function f and a sequence of ciphertext of \((\alpha _1, b_1),\dots ,(\alpha _k, b_k)\) and outputs a string \(b'\).

The correctness and security of such a scheme are provided in the next definition.

Definition 6

A tuple of four procedures \((\mathsf {Setup}, \mathsf {KG}, \mathsf {Enc}, \mathsf {Dec})\) is a k-input \((t,\epsilon )\)-secure ABE scheme if

1. 1.

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

   $$\begin{aligned} \Pr [ \mathsf {Dec}(\mathsf {KG}(\mathsf {msk}, f), \mathsf {Enc}(\mathsf {msk}, \alpha _1, b_1, 1), \dots , \mathsf {Enc}(\mathsf {msk}, \alpha _k, b_k, k) ) = b_1 ] = 1 \end{aligned}$$

   where the probability if over the choice of \(\mathsf {msk}\leftarrow \mathsf {Setup}(1^\lambda )\) and over the internal randomness of \(\mathsf {KG}\) and \(\mathsf {Enc}\). Note that only messages encrypted at index 1 can be recovered, thus every message encrypted at a different index could be set to \(\perp \) in our definition at the cost of a slightly more complex syntax.

2. 2.

   Security: For every polynomial \(p = p(\lambda )\), every \(\vec {\alpha }_1,\dots ,\vec {\alpha }_p\), where \(\vec {\alpha }_i = (\alpha ^{(i)}_1,\dots ,\alpha ^{(i)}_k)\in \mathcal {X}^k\) for \(i\in [p]\), and every \(f_1,\dots ,f_p \in \mathcal {F}\), it holds that if \(f_i(\alpha ^{i_1}_1,\dots ,\alpha ^{i_k}_k) = 0\) for every \(i,i_1,\ldots ,i_k\in [p]\), then

   $$\begin{aligned}&\left\{ \mathsf {KG}(\mathsf {msk}, f_i)\right\} _{i\in [p]}, \left\{ \mathsf {Enc}(\mathsf {msk}, \alpha _j^{(i)}, 0, j)\right\} _{i\in [p],j \in [k]} \approx _{t,\epsilon } \\&\left\{ \mathsf {KG}(\mathsf {msk}, f_i)\right\} _{i\in [p]}, \left\{ \mathsf {Enc}(\mathsf {msk}, \alpha _j^{(i)}, 1, j)\right\} _{i\in [p],j \in [k]}, \end{aligned}$$

   where the randomness is over the choice of \(\mathsf {msk}\leftarrow \mathsf {Setup}(1^\lambda )\) and the internal randomness of \(\mathsf {KG}\) and \(\mathsf {Enc}\).

In the next lemma we show that a general-purpose \(\mathsf {poly}\)-input ABE scheme implies a witness encryption scheme. This is similar to an analogous statement in the functional encryption literature which says that a general purpose multi-input functional encryption scheme implies indistinguishability obfuscation for all circuits [8].

Lemma 1

Let \(L \in \) NP be a language where instances are of size \(n=n(\lambda )\) and witnesses are of size \(m=m(\lambda )\). An m-input ABE scheme for all polynomial-size circuits implies a witness encryption scheme for L.

Proof

Let \(\mathsf {MIABE} = (\mathsf {Setup}, \mathsf {KG}, \mathsf {Enc}, \mathsf {Dec})\) be the m-input ABE scheme. Denote by \(V^{(L)}\) the verification procedure of the \({{\textsf {NP}}}\) language L. This procedure gets as input x and a possible witness w split into m bits \(w_1,\dots ,w_{m}\), and it outputs a bit that specifies whether w is a valid witness attesting to the fact that \(x\in L\). Given an instance \(x\in \{ 0,1 \}^{n}\) and a message \(b\in \{ 0,1 \}\), the witness encryption \(\mathsf {Enc}(1^\lambda , x,b)\) is computed as follows:

1. 1.

   Sample a master secret key for the multi-input ABE scheme \(\mathsf {msk}\leftarrow \mathsf {KG}(1^{\lambda })\).

2. 2.

   Use the ABE scheme to generate a key for the function \(V^{(L)}_x(w_1,\dots ,w_{m}) = V^{(L)}(x,w_1\dots w_{m})\):

   $$\begin{aligned} \mathsf {sk}_f \leftarrow \mathsf {KG}(\mathsf {msk}, V^{(L)}_x). \end{aligned}$$
3. 3.

   For \(\ell \in \{ 0,1 \}\) and \(i \in [m]\), use the ABE scheme to encrypt b under attribute \(\ell \) for the index i:

   $$\begin{aligned} \mathsf {ct}_{\ell ,b,i} \leftarrow \mathsf {Enc}(\mathsf {msk}, \ell , b, i). \end{aligned}$$
4. 4.

   Output \(\mathsf {sk}_f\), \(\{\mathsf {ct}_{\ell ,b,i}\}_{\ell \in \{ 0,1 \}, i\in [m]\}}\).

To decrypt a ciphertext \(\mathsf {ct}= (\mathsf {sk}_f, \{\mathsf {ct}_{\ell ,b,i}\}_{\ell \in \{ 0,1 \}, i\in [m]})\) with respect to a witness \(w = w_1\dots w_{m} \in \{ 0,1 \}^{m} \), we execute the decryption procedure of the ABE scheme as follows:

The correctness and security of the witness encryption scheme follow immediately from the correctness and security of the underlying multi-input ABE scheme. Correctness holds since given a valid witness w for which \(V^{(L)}(x,w)=1\), the ABE decryption procedure will output b. Security holds since for any \(x\notin L\), there is no witness for which \(V^{(L)}\) accepts x and thus \(V^{(L)}_x\) is always 0, which means that no combination of ciphertexts will lead to a successful decryption. The latter, by the security of the underlying ABE scheme implies that b is computationally hidden.

Using Fewer-Input ABE. Variants of the above theorem can be obtained in case we only have an ABE scheme that supports less inputs. Specifically, similarly to the refinement of [2] of the result of [8] mentioned above (see [14, Lemma 4.2] for the precise statement), one can show that a k-input ABE scheme for \(k=k(\lambda )\) implies a witness encryption scheme for languages with instances of size \(n=n(\lambda )\) and witnesses of size \(k\cdot \log n\). This means that a k-input ABE scheme for any \(k=\omega (1)\), is interesting as it could lead to non-trivial constructions of secret sharing schemes for all \({{\textsf {NP}}}\) based on somewhat weaker assumptions than currently known [13].

Reprints and permissions

© 2018 Springer Nature Switzerland AG

Policies and ethics