Witness Encryption and NP-Hardness of Learning

We first discuss a set of results that characterize witness encryption in terms of $\mathrm{𝖭𝖯}$-hardness reductions to PAC learning.

Witness encryption for an $\mathrm{𝖭𝖯}$ language $L$ consists of a pair of algorithms $(\mathrm{𝖤𝗇𝖼},\mathrm{𝖣𝖾𝖼})$ such that, for an $L$-instance $x$ and a secret bit $b\in \{0,1\}$, $\mathrm{𝖤𝗇𝖼}(x,b)$ outputs a ciphertext string $c$ using some randomness. It is guaranteed that, if $x\in L$ and $w$ is a witness for the membership of $x$ under a fixed witness relation for $L$, then $\mathrm{𝖣𝖾𝖼}(c,x,w)$ deterministically recovers the bit $b$. On the other hand, if $x\notin L$, then $\mathrm{𝖤𝗇𝖼}(x,0)$ and $\mathrm{𝖤𝗇𝖼}(x,1)$ are indistinguishable (within a negligible difference) for polynomial-size circuits (if the witness encryption is $𝖯/\mathrm{𝗉𝗈𝗅𝗒}$-secure) or PPT algorithms (if the witness encryption is $\mathrm{𝖡𝖯𝖯}$-secure). See Definition 39.

Our first result characterizes $𝖯/\mathrm{𝗉𝗈𝗅𝗒}$-secure witness encryption in terms of a deterministic many-one reduction to a promise problem known as $\mathrm{𝖢𝖦𝖫}$, introduced in a work of Applebaum et al. [2]. Inputs to $\mathrm{𝖢𝖦𝖫}$ are distributions $ℰ$ over string-label pairs $(x,b)\in {\{0,1\}}^n\times \{0,1\}$, where $ℰ$ is represented by a $\mathrm{𝗉𝗈𝗅𝗒}(n)$-size sampling circuit. For parameters and , a distribution $ℰ$ is a yes-instance of ${\mathrm{𝖢𝖦𝖫}}_{s_1}^{s_2}[\epsilon ]$ if there is a circuit $C$ of size at most $s_1$ such that, for $(x,b)\sim ℰ$, $\mathrm{Pr}[C(x)=b]=1$; $ℰ$ is a no-instance of ${\mathrm{𝖢𝖦𝖫}}_{s_1}^{s_2}[\epsilon ]$ if for every circuit $C^{\prime }$ of size at most $s_2$, for $(x,b)\sim ℰ$, .

Note that a many-one reduction to $\mathrm{𝖢𝖦𝖫}$ is quite a restrictive notion of reducibility to agnostic PAC learning: the reduction only uses its learning oracle to decide if a small circuit exists for the given distribution. As discussed earlier, one can imagine other kinds of reduction to learning that make more robust use of a learner: for example, actually examining the circuits returned by the learning oracle.

We further restrict the definition of a many-one reduction to $\mathrm{𝖢𝖦𝖫}$ by requiring that it be a half-Levin reduction. This is a term that we introduce here for a kind of reduction that is intermediate between a many-one reduction and a Levin reduction. A half-Levin reduction $(R,R_{wit})$ from $L_1$ to $L_2$ is a pair of polynomial-time machines such that $R$ is a many-one reduction from $L_1$ to $L_2$, and $R_{wit}$ transforms witnesses for $x\in L_1$ into witnesses for $R(x)\in L_2$. In contrast to a standard Levin reduction, we do not require a third algorithm transforming $L_2$-witnesses into $L_1$-witnesses. We emphasize that the half-Levin reductions considered in this work are deterministic unless stated otherwise.

We call a reduction to $\mathrm{𝖢𝖦𝖫}$ honest if, on inputs of length $n\in \mathbb{N}$, it outputs a distribution $ℰ$ supported over ${\{0,1\}}^{n^{\mathrm{\Omega }(1)}}\times \{0,1\}$.

We are now ready to state our main result. In general, fixing parameters $s_1,s_2$, and $\epsilon$, we show that a half-Levin reduction from a language $L$ to ${\mathrm{𝖢𝖦𝖫}}_{s_1}^{s_2}[\epsilon ]$ is equivalent to a witness encryption scheme for $L$ with running time roughly $s_1$, security against circuits of size roughly $s_2$, and with advantage parameter roughly $\epsilon$; see Lemmas 52 and 54. For the special case of $𝖯/\mathrm{𝗉𝗈𝗅𝗒}$-secure witness encryption, we get the following.

We also note that the above characterization is related to a very recent result from Liu, Mazor, and Pass, which shows that $𝖯/\mathrm{𝗉𝗈𝗅𝗒}$-secure witness encryption for an $\mathrm{𝖭𝖯}$-language $L$ is equivalent to the existence of a laconic special-honest verifier zero-knowledge argument for $L$ [36]. We refer to that paper for the definition of this kind of protocol, though we mention that the term “laconic” means that the total length of the prover’s messages is bounded by $O(\log n)$. As a corollary of [36] and our Theorem 4 above, we obtain the following.

One may also be interested in the possibility that $\mathrm{𝖭𝖯}$ has witness encryption schemes secure against PPT algorithms but not against polynomial-size circuits. We therefore present a kind of reduction to learning that is equivalent to $\mathrm{𝖡𝖯𝖯}$-secure witness encryption. This kind of reduction is intermediate between a half-Levin reduction to $\mathrm{𝖢𝖦𝖫}$ and the more general kind of reduction described in [2] wherein the reduction may actually inspect the hypotheses returned by the learner and use them in any way.

More specifically, in our case, the reduction makes a single query $ℰ$ to the search version of $\mathrm{𝖢𝖦𝖫}$, getting back a small circuit consistent with $ℰ$ if $ℰ$ is a yes-instance of $\mathrm{𝖢𝖦𝖫}$. We still require the reduction to be half-Levin. Furthermore, we require the reduction to be $\mathrm{𝖡𝖯𝖯}$-black-box;³³3The standard notion of a class-specific black-box reduction from a language $L_1$ to a language $L_2$ was defined by [13] as a way to formalize an intermediate case between treating $L_2$ as an oracle (“black box”) and requiring a source code for an $L_2$ algorithm implemented in some complexity class (“white box”); see Definitions 30 and 31. see Definition 32.

So far, we have only discussed learning in the “polynomial regime”, where the distribution $ℰ$ over pairs $(x,b)$ is in $\mathrm{𝖯𝖲𝖠𝖬𝖯}/\mathrm{𝗉𝗈𝗅𝗒}$. However, the original PAC learning framework of Valiant makes no such restriction: a PAC learner should be able to learn over arbitrary distributions [46]. We thus consider reductions to learning that make further use of this capacity. In particular, imagine a polynomial-time reduction that, on input length $n$, queries a learner for a function on $O(\log n)$-length inputs. In this case, it will be possible to ask the learner to work on inefficiently samplable distributions, and a truth-table of the function in question can be given to the learner explicitly. In this particular setup, the distributions queried represent well-defined functions, which may not be the case in the setup above with $\mathrm{𝖢𝖦𝖫}$. In this sense, we get closer to standard PAC learning rather than agnostic PAC learning.

This notion of learning in the “exponential regime” is closely related to $\mathrm{𝖬𝖢𝖲𝖯}$, which asks, given a truth-table $T$ and a size threshold $s$, whether there exists a circuit of size $s$ consistent with $T$. We generalize the problem to the context of learning by providing, along with $T$, a probability distribution $\mu$ represented as a table. We call this problem “Gap Distributional $\mathrm{𝖬𝖢𝖲𝖯}$”, denoted $\mathrm{𝖦𝖺𝗉𝖣𝗂𝗌𝗍𝖬𝖢𝖲𝖯}$. Specifically, $(T,\mu )$ is a yes-instance of ${\mathrm{𝖦𝖺𝗉𝖣𝗂𝗌𝗍𝖬𝖢𝖲𝖯}}_{s_1}^{s_2}[\epsilon ]$ if there exists a circuit $C$ of size at most $s_1$ such $C$ is consistent with $T$, and $(T,\mu )$ is a no-instance if for every circuit $C^{\prime }$ of size at most $s_2$, the probability over $x\sim \mu$ that $C(x)=T(x)$ is at most $1/2+\epsilon$. Note that this definition naturally generalizes $\mathrm{𝖠𝗏𝖾𝖬𝖢𝖲𝖯}$ as defined in [45] (and in [7], denoted $\mathrm{𝖬𝖠𝖢𝖲𝖯}$), where the definition is the same except the distribution fixed to uniform.

We show that $\mathrm{𝖭𝖯}$-hardness of learning in this sense is equivalent to witness encryption for $\mathrm{𝖭𝖯}$ such that the ciphertexts output by $\mathrm{𝖤𝗇𝖼}$ have only logarithmic length, along with a circuit lower bound for $𝖤$. Below we use $\mathrm{𝖲𝖨𝖹𝖤}[s(n)]$ to denote the class of $n$-input boolean functions computable by circuits of size $s(n)$; for $0\le \alpha \le 1$, we use ${\mathrm{𝖲𝖨𝖹𝖤}}_D^{\alpha }[s(n)]$ to denote the class of $n$-input boolean functions that can be computed by circuits of size $s(n)$ on average, with probability at least $\alpha$ over inputs $x\in {\{0,1\}}^n$ sampled according to the distribution $D$.

Note that we obtain correspondences between the output length of the reduction $R$ and the output length of $\mathrm{𝖤𝗇𝖼}$, the $s_1$ parameter of $\mathrm{𝖦𝖺𝗉𝖣𝗂𝗌𝗍𝖬𝖢𝖲𝖯}$ and the running time of $\mathrm{𝖣𝖾𝖼}$, the $s_2$ parameter of $\mathrm{𝖦𝖺𝗉𝖣𝗂𝗌𝗍𝖬𝖢𝖲𝖯}$ and the security of witness encryption, and the $\epsilon$ parameter of $\mathrm{𝖦𝖺𝗉𝖣𝗂𝗌𝗍𝖬𝖢𝖲𝖯}$ and the advantage parameter of witness encryption.

As discussed in the introduction, $\mathrm{𝖭𝖯}$-hardness of proper agnostic PAC-learning for polynomial-size circuits is known. However, $\mathrm{𝖭𝖯}$-hardness of improper learning is a major open question that remains elusive. In this section, we advance toward $\mathrm{𝖭𝖯}$-hardness of “less proper” agnostic PAC learning for polynomial-size circuits.

First, we show that for polynomials $s_1$ and ${\epsilon }^{-1}$, letting $s_2(n)=s_1(n)\cdot n^{1/{(\log \log n)}^{O(1)}}$, ${\mathrm{𝖢𝖦𝖫}}_{s_1}^{s_2}[\epsilon ]$ is $\mathrm{𝖭𝖯}$-hard under a randomized many-one reduction. In particular,

As a straightforward consequence of Theorem 8, we obtain $\mathrm{𝖭𝖯}$-hardness of agnostic PAC-learning in the semi-proper setting of learning size-$s(n)$ circuits by size-$s(n)\cdot n^{1/{(\log \log n)}^{O(1)}}$ circuits.

This improves on a prior work of Hirahara [16], which contains two main results. The first shows that, for polynomials $s$, it is $\mathrm{𝖭𝖯}$-hard to agnostically learn programs of size $s(n)$ by programs of size $s(n)\cdot n^{1/{(\log \log n)}^{O(1)}}$. This is accomplished by reduction from the “minimum monotone satisfying assignment” problem, $\mathrm{𝖬𝖬𝖲𝖠}$, which is known to be $\mathrm{𝖭𝖯}$-hard to approximate by way of a PCP theorem [8, 9]. We note that Hirahara’s proof makes use of efficient secret sharing schemes, a cryptographic primitive closely related to witness encryption and known to exist unconditionally (with statistical security) for access structures that are monotone formulae [27, 5] (see [4, 11]).

The second main result of [16] shows that ${\mathrm{𝖬𝖢𝖲𝖯}}^{\ast }$, a partial function version of $\mathrm{𝖬𝖢𝖲𝖯}$, is likewise $\mathrm{𝖭𝖯}$-hard. This proof requires even more sophisticated techniques in order to produce a truth-table on logarithmic-length inputs. In particular, Hirahara reduces from a gap version of the “collective minimum (weight) monotone satisfying assignment problem” ($\mathrm{𝖢𝖬𝖬𝖲𝖠}$), which generalizes $\mathrm{𝖬𝖬𝖲𝖠}$. Using the techniques of that proof and padding the inputs to have polynomial length, one can obtain $\mathrm{𝖭𝖯}$-hardness of learning $𝖯/\mathrm{𝗉𝗈𝗅𝗒}$, but with a smaller gap.

However, those ideas do not extend to obtain the larger $s(n)$ vs. $s(n)\cdot n^{1/{(\log \log n)}^{O(1)}}$ gap for circuits rather than programs as in Corollary 9.

Though in the case of $𝖯/\mathrm{𝗉𝗈𝗅𝗒}$ we are unable to obtain $\mathrm{𝖭𝖯}$-hardness with a gap greater than $n^{1/{(\log \log n)}^{O(1)}}$, we show in this section that for some related concept classes, improper learning is $\mathrm{𝖭𝖯}$-hard. We demonstrate such results for learning oracle circuits and learning RAM programs.

In the following, for a fixed $\lambda :\mathbb{N}\to \mathbb{N}$ and distribution family $D={\{D_m\}}_{m\in \mathbb{N}}$, where each $D_m$ is supported over strings of length $2^m$ and samplable uniformly in time $\mathrm{𝗉𝗈𝗅𝗒}(2^m)$, $D\text{-}\mathrm{𝗈𝗋𝖺𝖼𝗅𝖾}\text{-}{\mathrm{𝖢𝖦𝖫}}_{s_1}^{s_2}[\epsilon ,\lambda ]$ is a generalization of ${\mathrm{𝖢𝖦𝖫}}_{s_1}^{s_2}[\epsilon ]$ in which all circuits and samplers take access to an oracle $O\in {\{0,1\}}^{2^{\lambda (n)}}$ randomly sampled from $D_{\lambda (n)}$. $ℰ$ is a yes-instance of $D\text{-}\mathrm{𝗈𝗋𝖺𝖼𝗅𝖾}\text{-}{\mathrm{𝖢𝖦𝖫}}_{s_1}^{s_2}[\epsilon ,\lambda ]$ if there exists a circuit $C$ of size $s_1(n)$ such that for every $O$ in the support of $D_{\lambda (n)}$,

and $ℰ$ is a no-instance of $D\text{-}\mathrm{𝗈𝗋𝖺𝖼𝗅𝖾}\text{-}{\mathrm{𝖢𝖦𝖫}}_{s_1}^{s_2}[\epsilon ,\lambda ]$ if, with probability $1-\epsilon (n)$ over $O\sim D_{\lambda (n)}$, for any circuit $C$ of size $s_2(n)$,

We prove the following $\mathrm{𝖭𝖯}$-hardness of $\mathrm{𝗈𝗋𝖺𝖼𝗅𝖾}\text{-}\mathrm{𝖢𝖦𝖫}$, from which we will derive further corollaries.

Theorem 12 is proved using a framework developed by Huang, Ilango, and Ren for “witness encryption in oracle worlds” [21]. More specifically, drawing on the candidate witness encryption scheme proposed in [11], the authors show that there exist an $\mathrm{𝖭𝖯}$-complete language $L$ and a distribution family $D\in \mathrm{𝖯𝖲𝖠𝖬𝖯}$ such that, with high probability over oracles $O$ sampled randomly from $D$, witness encryption for $L$ exists with respect to $O$. That is, $\mathrm{𝖤𝗇𝖼}$, $\mathrm{𝖣𝖾𝖼}$, and adversaries all get oracle access to $O$.

We may then apply the techniques of one direction of our main equivalence, Theorem 4, to obtain $\mathrm{𝖭𝖯}$-hardness of learning with respect to $O$. Crucially, in [21], an oracle $O$ with truth-table length $n$ gives rise to a witness encryption scheme secure against non-uniform adversaries of size polynomially related to $n$. So, to achieve $\mathrm{𝖭𝖯}$-hardness of $\mathrm{𝗈𝗋𝖺𝖼𝗅𝖾}\text{-}\mathrm{𝖢𝖦𝖫}$ with an arbitrary polynomial gap, one only requires oracle truth-tables of polynomial length.

As a consequence of Theorem 12, we show that agnostic learning is $\mathrm{𝖭𝖯}$-hard in an “oracle-PAC” model that we introduce here, which generalizes standard agnostic PAC learning of $𝖯/\mathrm{𝗉𝗈𝗅𝗒}$. In this model, a learner for $\mathrm{𝖲𝖨𝖹𝖤}[s]$ on input length $n$ is explicitly given the whole truth table of an oracle function $𝒪:{\{0,1\}}^{O(\log n)}\to \{0,1\}$ sampled randomly from some distribution $D\in \mathrm{𝖯𝖲𝖠𝖬𝖯}$. The learner is asked to output an oracle circuit $h$ such that $h^{𝒪}$ approximates the target function almost as well as the best size-$s$ $𝒪$-oracle circuit; see Definition 23.

We stress that the above holds under a standard polynomial-time reduction that does not itself require any oracle.

As a second consequence of the $\mathrm{𝖭𝖯}$-hardness of $\mathrm{𝗈𝗋𝖺𝖼𝗅𝖾}\text{-}\mathrm{𝖢𝖦𝖫}$, we show that it is $\mathrm{𝖭𝖯}$-hard to agnostically learn RAM programs in an improper setting. In particular, we focus on a decision problem based on the problem $\mathrm{𝖬𝖨𝖭𝖫𝖳}$ defined in [31]. In Ko’s definition, the input to $\mathrm{𝖬𝖨𝖭𝖫𝖳}$ consists of pairs ${(x_i,b_i)}_{i\in [m]}\in {({\{0,1\}}^n\times \{0,1\})}^m$ for some $m=\mathrm{𝗉𝗈𝗅𝗒}(n)$ along with size and running time parameters $s,t\in \mathbb{N}$ represented in unary. The input is a yes-instance if and only if there exists a program $M$ of size at most $s$ and running time at most $t$ such that $M(x_i)=b_i$ for all $i\in [m]$. Ko exhibited an oracle relative to which $\mathrm{𝖬𝖨𝖭𝖫𝖳}$ is not $\mathrm{𝖭𝖯}$-hard [31].

Hirahara, using non-relativizing techniques, showed that a certain generalization of $\mathrm{𝖬𝖨𝖭𝖫𝖳}$ (called $\mathrm{𝖦𝖺𝗉𝖫𝖾𝖺𝗋𝗇}$) is in fact $\mathrm{𝖭𝖯}$-hard [16]. In this promise-problem, the pairs $(x_i,b_i)$ are represented implicitly by a sampling circuit (as in the definition of $\mathrm{𝖢𝖦𝖫}$), and there is a gap, eg., in program size between yes-instances and no-instances. It is easy to see that $\mathrm{𝖭𝖯}$-hardness of this problem (Theorem 1.1 in [16]) implies $\mathrm{𝖭𝖯}$-hardness of Ko’s $\mathrm{𝖬𝖨𝖭𝖫𝖳}$.

We formulate our definition of $\mathrm{𝖦𝖺𝗉𝖱𝖠𝖬}\text{-}\mathrm{𝖬𝖨𝖭𝖫𝖳}$ analogously to the definition of $\mathrm{𝖦𝖺𝗉𝖫𝖾𝖺𝗋𝗇}$ in [16] but considering programs that are granted random access to their inputs. Namely, the input to ${\mathrm{𝖦𝖺𝗉}}_{g,\epsilon }\mathrm{𝖱𝖠𝖬}\text{-}\mathrm{𝖬𝖨𝖭𝖫𝖳}$ is a sampler $ℰ$ over pairs $(x,b)$ along with parameters $s,t\in \mathbb{N}$. The input $(ℰ,1^s,1^t)$ is a yes-instance if there exists a program of size at most $s$ and running in time at most $t$ such that ${\mathrm{Pr}}_{(x,b)\sim ℰ}[M^x=b]=1$, and $(ℰ,1^s,1^t)$ is a no-instance if for any program of size at most $g(s)$ and running in time at most $g(t)$, . Here, $M^x$ denotes the program $M$ with random access to its input $x$.

We obtain the following $\mathrm{𝖭𝖯}$-hardness of $\mathrm{𝖦𝖺𝗉𝖱𝖠𝖬}\text{-}\mathrm{𝖬𝖨𝖭𝖫𝖳}$. Note that the parameters we obtain imply $\mathrm{𝖭𝖯}$-hardness of learning RAM programs in an improper setting.

In contrast, [16] considers programs that do not require random access to their inputs; the gap in program size achieved there is small (namely, $s(n)$ vs. $s(n)\cdot n^{1/{(\log \log n)}^{O(1)}}$), though the no-instances extend to time-unbounded programs.

Finally, we prove a few results demonstrating what cryptography is possible assuming worst-case hardness of $\mathrm{𝖭𝖯}$ along with various assumptions concerning witness encryption and $\mathrm{𝖭𝖯}$-hardness of learning.

Assuming a randomized non-adaptive reduction from $\mathrm{𝖲𝖠𝖳}$ to improper agnostic learning as described in [2] (see Definition 28), we show that the worst-case assumption $\mathrm{𝖭𝖯}⊈\mathrm{𝖡𝖯𝖯}$ is sufficient to imply one-way functions secure infinitely often against uniform PPT adversaries. This improves a main result of [2] (Theorem 1 in the introduction), which requires average-case hardness of $\mathrm{𝖭𝖯}$. In terms of Impagliazzo’s five worlds [22], the result of [2] conditionally excludes Pessiland. In contrast, we conditionally exclude both Heuristica and Pessiland.

As discussed in the introduction, Garg et al. show that WE for an $\mathrm{𝖭𝖯}$-complete language along with a one-way function is sufficient for public-key encryption [11]. Combining this result, our main equivalence in Theorem 4, and Theorem 15, we obtain that witness encryption simultaneously excludes Heuristica, Pessiland, and Minicrypt.

We believe that this statement can also be proved by combining prior works [33, 19, 11] (see also [35]), though we have not seen the uniform version stated (ie. the version with the assumption $\mathrm{𝖭𝖯}⊈\mathrm{𝖡𝖯𝖯}$ rather than $\mathrm{𝖭𝖯}⊈𝖯/\mathrm{𝗉𝗈𝗅𝗒}$). In any case, we provide an alternative proof that does not rely on properties of zero-knowledge, such as the “SZK/OWF” characterization from [42].

Theorem 16 and our our main equivalence in Theorem 4 together imply that if learning is $\mathrm{𝖭𝖯}$-hard under a half-Levin reduction to ${\mathrm{𝖢𝖦𝖫}}_{s_1}^{s_2}[\epsilon ]$ working for arbitrary polynomials $s_2$ and ${\epsilon }^{-1}$, one can rule out Minicrypt in addition to Heuristica and Pessiland. Thus, we obtain a stark distinction between the two kinds of reduction to learning defined in [2]. Namely, assuming worst-case hardness of $\mathrm{𝖭𝖯}$, a randomized non-adaptive reduction to agnostic learning over $\mathrm{𝖯𝖲𝖠𝖬𝖯}/\mathrm{𝗉𝗈𝗅𝗒}$ yields one-way functions, whereas a deterministic many-one reduction to $\mathrm{𝖢𝖦𝖫}$, provided it is half-Levin, yields public-key encryption.

We start with an informal overview of the proof of our main equivalence, Theorem 4. In both directions, the constructions employed and the proofs of correctness are straightforward. We first show how to obtain a half-Levin reduction from $L$ to $\mathrm{𝖢𝖦𝖫}$ from a $𝖯/\mathrm{𝗉𝗈𝗅𝗒}$-secure witness encryption scheme $(\mathrm{𝖤𝗇𝖼},\mathrm{𝖣𝖾𝖼})$ for $L$. In particular, given an $L$-instance $z$, the reduction outputs a distribution $ℰ$ as follows.

Sample $b\sim 𝒰$. Let $x:=\mathrm{𝖤𝗇𝖼}(z,b)$. Output $(x,b)$.

Note that we can assume that the output length of $\mathrm{𝖤𝗇𝖼}$ is at least $n^{\mathrm{\Omega }(1)}$ without loss of generality, so the reduction described here is honest.

In the case that $z\in L$ with witness $w$, $ℰ$ is a yes-instance of $\mathrm{𝖢𝖦𝖫}$, since the circuit defined by $\mathrm{𝖣𝖾𝖼}(-,z,w)$ recovers the bit $b$ from $x$ with probability 1 over $ℰ$. This is true by the correctness of $(\mathrm{𝖤𝗇𝖼},\mathrm{𝖣𝖾𝖼})$. Also note that, since $\mathrm{𝖣𝖾𝖼}$ is a uniform polynomial-time algorithm, the circuit $\mathrm{𝖣𝖾𝖼}(-,z,w)$ can be constructed in polynomial time given $z$ and $w$. Thus, our reduction is half-Levin. In the case that $z\notin L$, we observe that if there were a circuit $C$ of polynomial size such that

then by definition of $ℰ$,

violating the security of $\mathrm{𝖤𝗇𝖼}$. So, $ℰ$ must be a no-instance of $\mathrm{𝖢𝖦𝖫}$.

Now we show how to obtain a $𝖯/\mathrm{𝗉𝗈𝗅𝗒}$-secure witness encryption scheme from a half-Levin reduction $(R,R_{wit})$ to $\mathrm{𝖢𝖦𝖫}$. We define a witness encryption scheme as follows. Let $z$ be an instance of $L$, and if $z\in L$, let $w$ be a witness. Let $a$ be a secret bit to encrypt.

$\mathrm{𝖤𝗇𝖼}(z,a)$ computes $ℰ=R(z)$, samples $(x,b)\sim ℰ$ and then outputs $(x,a\oplus b)$.

$\mathrm{𝖣𝖾𝖼}((x,c),z,w)$ computes $A:=R_{wit}(z,w)$ and then outputs $A(x)\oplus c$.

The correctness of $(\mathrm{𝖤𝗇𝖼},\mathrm{𝖣𝖾𝖼})$ follows from the fact that, for $z\in L$, $R_{wit}(z,w)$ is a witness for $ℰ=R(z)$ being a yes-instance of $\mathrm{𝖢𝖦𝖫}$: that is, a circuit $A$ of polynomial size such that

It follows that $A(x)\oplus c=b\oplus (a\oplus b)=a$. The security of $\mathrm{𝖤𝗇𝖼}$ follows from Yao’s argument that a distinguisher implies a next-bit predictor. Specifically, for $(x,b)\sim ℰ$, from a circuit of size $s(n)$ distinguishing $\mathrm{𝖤𝗇𝖼}(z,0)=(x,b)$ from $\mathrm{𝖤𝗇𝖼}(z,1)=(x,1\oplus b)$, we would obtain a circuit of size $O(s(n))$ predicting (with inverse polynomial advantage) $b$ from $x$. By the honesty of the reduction, we have $O(s(n))=\mathrm{𝗉𝗈𝗅𝗒}(|x|)$. This violates the fact that $ℰ$ is a no-instance of ${\mathrm{𝖢𝖦𝖫}}_{s_1}^{s_2}$ for every polynomial $s_2$, a contradiction.

To modify the argument above for the case of $\mathrm{𝖡𝖯𝖯}$-secure witness encryption, we note that, in the first direction discussed, the security of WE is only violated if the circuit $C$ can be constructed uniformly in polynomial time. Therefore, we consider $\mathrm{𝖡𝖯𝖯}$-black-box reductions to search-$\mathrm{𝖢𝖦𝖫}$. That is, roughly, the reduction is only guaranteed to work when its oracle is a PPT algorithm, and we require the oracle to actually construct a small circuit with inverse polynomial advantage over the queried distribution $ℰ$ if one exists. For the other direction, we employ the observation that, from a uniform PPT distinguisher algorithm $A$, one can construct a next-bit predictor $P^A$ uniformly.

For the case of $\mathrm{𝖦𝖺𝗉𝖣𝗂𝗌𝗍𝖬𝖢𝖲𝖯}$ in Theorem 7, a challenge is that an arbitrary witness encryption scheme $(\mathrm{𝖤𝗇𝖼},\mathrm{𝖣𝖾𝖼})$ may not yield a distribution $ℰ$ that represents a well-defined function. On one hand, if $z\in L$, then there is guaranteed to be a unique bit $b_x$ such that $(x,b_x)$ is in the support of $ℰ$, by the correctness of the witness encryption scheme. However, if $z\notin L$, this may not be true. Luckily, since $ℰ$ is supported over logarithmic-length strings, we can check in polynomial time whether each $x$ has a unique label. If not, we use our assumption of a circuit lower bound for $𝖤$ to output a no-instance of $\mathrm{𝖦𝖺𝗉𝖣𝗂𝗌𝗍𝖬𝖢𝖲𝖯}$. In the other direction, from a (deterministic) half-Levin reduction from $\mathrm{𝖲𝖠𝖳}$ to $\mathrm{𝖦𝖺𝗉𝖣𝗂𝗌𝗍𝖬𝖢𝖲𝖯}$, we obtain a circuit lower bound for $𝖤$ by applying the reduction to a trivial no-instance of $\mathrm{𝖲𝖠𝖳}$, as in [29].

Our proof of $\mathrm{𝖭𝖯}$-hardness of $\mathrm{𝖢𝖦𝖫}$ with parameters corresponding to semi-proper learning works within the framework developed in [16]. It differs from Theorem 7.2 in that paper mainly in the “completeness” argument. Referring to the notation in the proof of that theorem and of our Lemma 64, we need to construct a circuit of size not exceeding $O(\theta \lambda )$.

For one thing, in the proof of [16], using ${\mathrm{𝖣𝖯}}_k$ generators to encode the high-complexity truth-tables $f_i$, the number of input gates to the circuit alone would exceed the desired threshold. Therefore, we use Nisan-Wigderson generators rather than ${\mathrm{𝖣𝖯}}_k$ generators to allow for a short random seed. (A similar idea is used elsewhere in [16].)

More importantly, we apply a recent result of Holmgren and Rothblum showing that “multiselection” of $t$ indices from a string of length $m\in \mathbb{N}$ can be done by a circuit of size at most $O(m+t\cdot {\log }^3(m))$ [20]. See Lemma 61. So, we can make $\mathrm{𝗉𝗈𝗅𝗒}(n)$ queries to $\theta$ truth-tables $f_j$, each of length $\lambda$, with total circuit size at most $O(\theta \cdot (\lambda +o(\lambda )))$. This allows us to compute values of the amplified functions ${\widehat{f}}_j$ and recover the secret labels $b$ without exceeding the desired size threshold. Note that Uhlig’s Theorem as in [16] cannot accommodate $\mathrm{𝗉𝗈𝗅𝗒}(n)$ queries.

To obtain Corollary 9, which states that semi-proper agnostic learning is $\mathrm{𝖭𝖯}$-hard, we give a simple randomized reduction from $\mathrm{𝖢𝖦𝖫}$ to learning that works by empirical estimation of the success probability of the hypothesis produced by the learner. See Lemma 33.

To obtain $\mathrm{𝖭𝖯}$-hardness of $\mathrm{𝗈𝗋𝖺𝖼𝗅𝖾}\text{-}\mathrm{𝖢𝖦𝖫}$, we apply an argument analogous to the first direction of our main equivalence, along with the fact that, for some distribution family $D\in \mathrm{𝖯𝖲𝖠𝖬𝖯}$, witness encryption for $\mathrm{𝖭𝖯}$ exists unconditionally (with high probability) with respect to oracles sampled from $D$. This was demonstrated in [21]. More specifically, the authors show the following.

Our idea is to apply the foregoing “oracle witness encryption” along with our main technique for proving that witness encryption implies $\mathrm{𝖭𝖯}$-hardness of $\mathrm{𝖢𝖦𝖫}$. We modify the definition of $\mathrm{𝖢𝖦𝖫}$ accordingly so that all circuits and samplers have access to an oracle randomly sampled from $D$. See Definition 25. Crucially, to achieve $\mathrm{𝖭𝖯}$-hardness of $D\text{-}\mathrm{𝗈𝗋𝖺𝖼𝗅𝖾}\text{-}{\mathrm{𝖢𝖦𝖫}}_{s(n)}^{s{(n)}^c}$ for a constant $c\in \mathbb{N}$, we require witness encryption with security against adversaries of size $s{(n)}^c$, and thus we require an oracle $O$ with truth-table length only $s{(n)}^{c\cdot \mathrm{\ell }}=\mathrm{𝗉𝗈𝗅𝗒}(n)$.

Corollary 13 follows from Theorem 12 analogously to Corollary 9 and Theorem 8, as discussed above: a straightforward reduction from $\mathrm{𝗈𝗋𝖺𝖼𝗅𝖾}\text{-}\mathrm{𝖢𝖦𝖫}$ to oracle-PAC learning.

To prove Corollary 14, we give a randomized reduction from $D\text{-}\mathrm{𝗈𝗋𝖺𝖼𝗅𝖾}\text{-}\mathrm{𝖢𝖦𝖫}$ to the problem $\mathrm{𝖦𝖺𝗉𝖱𝖠𝖬}\text{-}\mathrm{𝖬𝖨𝖭𝖫𝖳}$. Given an instance ${ℰ}^{(-)}$ of $D\text{-}\mathrm{𝗈𝗋𝖺𝖼𝗅𝖾}\text{-}\mathrm{𝖢𝖦𝖫}$, the reduction starts by sampling a random truth-table $O\sim D$. Then, it defines an instance ${ℰ}^{\prime }$ of $\mathrm{𝖦𝖺𝗉𝖱𝖠𝖬}\text{-}\mathrm{𝖬𝖨𝖭𝖫𝖳}$ which always outputs the entire truth-table $O$ along with a string $(x,b)$ sampled according to ${ℰ}^O$; one can think of ${ℰ}^{\prime }$ as sampling pairs $(x^{\prime },b)$ with $x^{\prime }=(x,O)$. Clearly, this results in a non-oracle instance of $\mathrm{𝖦𝖺𝗉𝖱𝖠𝖬}\text{-}\mathrm{𝖬𝖨𝖭𝖫𝖳}$. In the proof of correctness, we also rely on the fact that a program of size and running time at most $s^{\prime }$ can be simulated by a circuit of size $\mathrm{𝗉𝗈𝗅𝗒}(s^{\prime })$ (and vice versa). Since the oracles obtained from [21] require length polynomially greater than the size of adversary they are secure against, we need to consider machines running in time less than the length of their inputs. Given these observations and the definitions of $\mathrm{𝗈𝗋𝖺𝖼𝗅𝖾}\text{-}\mathrm{𝖢𝖦𝖫}$ and $\mathrm{𝖦𝖺𝗉𝖱𝖠𝖬}\text{-}\mathrm{𝖬𝖨𝖭𝖫𝖳}$, the corollary follows easily.

We prove Theorem 15 with an argument from [2] as a starting point.⁴⁴4Note that we include a proof below for the reader’s convenience; see Lemma 72. Let $R$ be a randomized non-adaptive reduction from an $\mathrm{𝖭𝖯}$-complete language $L$ to agnostic learning over $\mathrm{𝖯𝖲𝖠𝖬𝖯}/\mathrm{𝗉𝗈𝗅𝗒}$. Assume that i.o. one-way functions do not exist. Then, for any $D\in \mathrm{𝖯𝖲𝖠𝖬𝖯}$ and auxiliary-input function ${\{f_z\}}_{z\in {\{0,1\}}^{\ast }}$, there is a machine $I$ that distributionally inverts $f_z$ with high probability over auxiliary inputs $z\sim D$. We think of instances $z$ of $L$ as auxiliary inputs for the function $f_z$ that, roughly, simulates $R(z)$ to obtain a sampling circuit $ℰ$ over string/label pairs and then samples from $ℰ$. Applebaum et al. show that there is a polynomial-time-computable hypothesis $h$, using a distributional inverter for $f_z$, having near-maximum agreement over $ℰ$. Running the reduction $R$ and answering oracle queries with hypotheses $h$ defined in this way, we obtain

where “$\mathrm{𝖧𝖾𝗎𝗋}$”, informally, refers to average-case heuristics that may err by incorrectly outputting 1 or 0.

We next use the fact that the inversion of polynomial-time-computable functions is verifiable. That is, if a machine fails to invert on some instance, it can be defined to “realize this” in polynomial time. More concretely, the machine $I$ above can be defined to output $\perp$ on input $z$ if it fails to invert often on some particular $f_z$, using empirical estimation. From this observation, we further obtain

where $\mathrm{𝖠𝗏𝗀}$ refers to heuristics that do not err but may output $\perp$ rather than 1 or 0 with inverse polynomial probability. Lastly, we apply a recent result of [12], which, from $\mathrm{𝖣𝗂𝗌𝗍𝖭𝖯}\subseteq \mathrm{𝖠𝗏𝗀𝖡𝖯𝖯}$, yields worst-case easiness of agnostic PAC learning over distributions in $\mathrm{𝖯𝖲𝖠𝖬𝖯}/\mathrm{𝗉𝗈𝗅𝗒}$. We then run the reduction $R$ for a second time, answering oracle queries with the worst-case agnostic learner guaranteed by [12], to obtain $\mathrm{𝖭𝖯}\subseteq \mathrm{𝖡𝖯𝖯}$.

To obtain Theorem 16, start by assuming the existence of witness encryption for an $\mathrm{𝖭𝖯}$-complete language. Then, apply the characterization given by Theorem 4 to obtain a half-Levin reduction from $\mathrm{𝖭𝖯}$ to $\mathrm{𝖢𝖦𝖫}$. Since $\mathrm{𝖢𝖦𝖫}$ reduces to agnostic PAC learning, we may apply Theorem 15 as described above to exclude Heuristica and Pessiland. To summarize, informally,

where ${\le }_{hl}$ refers to a half-Levin reduction and ${\le }_{tt}$ refers to a randomized non-adaptive (ie. “truth-table”) reduction. Furthermore, Garg et al. show that witness encryption for $\mathrm{𝖭𝖯}$, together with the existence of a one-way function, yields public-key encryption [11]. This, together with the above, conditionally yields public-key encryption. To summarize,

Theorem 17 is immediate from the reasoning above together with another application of the characterization in Theorem 4. That is,