On White-Box Learning and Public-Key Encryption

Our main results is that the hardness of this problem characterizes the existence of public-key encryption:

Computational depth is typically thought of as measure of “unnaturality” of strings: strings with low computational depth are considered “natural” and those with high computational depth are considered “unnatural”.⁷⁷7The reason why low computational depth captures “natural string” is as follows: random strings are known to have low computational depth; furthermore, known results (c.f. slow growth laws [18]) show (at least under derandomization assumptions) that one needs to have a long running time to even find a string with high computational depth. So strings with high computational depth are rare and “hard to find”, which is why they can be thought of as “unnatural”. Given this interpretation, our characterization of public key encryption is thus in terms of the worst-case hardness of white-box learning for “natural” instances.

As far as we know, this thus yields the first problem whose worst-case hardness not only suffices for public-key encryption (such as e.g., [30]) but also is necessary.

We note that Antunes and Fortnow [3] elegantly used computational depth to connect worst-case hardness of a problem when restricting attention to elements with small computational depth and errorless average-case hardness on sampleable distributions; errorless hardness, however, is not sufficient for cryptographic applications. Nevertheless, inspired by the work of [3], worst-case hardness conditioned on instances with small computational depth was used in [26] (and independently using a variant of this notion in [18]) to characterize one-way functions; additionally, an (interactive) variant of such a notion was also implicitly used in [6] to characterize key exchange protocols. Our techniques are similar to those employed in [26, 6] but instead of applying them to study the hardness of a time-bounded Kolmogorov complexity problem (following [25]), we here instead apply them to study a learning theory problem (namely, white-box learning).

We note that learning theory problems conditioned on small computational depth were recently used in [18] to characterize one-way functions, but our techniques here are more similar to [26, 6]. In particular, [18] does not actually use the standard notion of computational depth but instead define a new alternative variant; in contrast, we here rely on just the standard notion.

Note that in Theorem 1, the equivalence hold for any (sufficiently small) choice of $\mathrm{\Delta }$, as such we directly get as a corollary the equivalence of Exact and Approximate White-box Learning:

While in the $\mathrm{\Delta }$-$\mathrm{𝖶𝖡𝖫𝖾𝖺𝗋𝗇}$ problem, we allow the function we are trying to learn to be any polynomial-size circuit, we may also consider a restricted version of the problem, denoted $\mathrm{\Delta }$-${\mathrm{𝖶𝖡𝖫𝖾𝖺𝗋𝗇}}_q^d$, where we restrict attention to functions that can be computed by a degree $d$ polynomial, and we assume that arithmetic is now over ${\mathbb{Z}}_q$.

We first remark that our main theorem can next be generalized (basically using padding) to show that it suffices to use learning of degree-$n^{ϵ}$ polynomials to characterize PKE:

Additionally, as informally discussed above, we note that the hardness of the LWE problem, implies hardness of the $\mathrm{\Delta }$-${\mathrm{𝖶𝖡𝖫𝖾𝖺𝗋𝗇}}_q^1$ problem (i.e., white-box learning of linear functions.)

Lemma 4 thus shows that white-box learning of linear functions is at least as weak an assumption as LWE. At first sight, one would expect that a converse result may also hold due to known worst-case to average-case reductions for the LWE problem [30, 28, 9] and thus that LWE is equivalent to white-box learning of linear functions. However, the problem with proving the converse direction is that the known worst-case to average-case reductions for LWE only work when the LWE instance defines a lattice where the shortest vector is long compared to amount of noise. Instances sampled from $P$ may not necessarily satisfy this promise, and thus is it not clear how to use an LWE oracle to generally solving white-box learning of linear functions. Thus, it would seem that hardness even of just ${\mathrm{\Delta }\text{-}{\mathrm{𝖶𝖡𝖫𝖾𝖺𝗋𝗇}}_q^1|}_{{\mathrm{𝖢𝖲}}^t}$ is seemingly a weaker (and therefore more general) assumption than LWE. (Of course, it may be that a stronger worst-case to average-case reduction can be established for the LWE problem, in which case equivalence would hold.)

We finally investigate what happens in the regime of “intermediate-degree” polynomials. We remark that using standard linearization techniques, the constant-degree problem is equivalent to the case of degree 1:

Finally, to put our results in context, we consider the standard PAC learning model [35] where the learner only get access to samples: Let $\mathrm{\Delta }$-$\mathrm{𝖡𝖡𝖫𝖾𝖺𝗋𝗇}$ denote identically the same problem as $\mathrm{𝖶𝖡𝖫𝖾𝖺𝗋𝗇}$ with the exception that the learner gets oracle access (i.e., black-box access) to the sampler (as opposed to white-box access to the sampler). This notion is equivalent to the notion of improper $\mathrm{\Delta }$-approximate PAC learning for polynomial-size circuits (and when $\mathrm{\Delta }=0$ to simply improper PAC learning).

As before, let $\mathrm{\Delta }$-${\mathrm{𝖡𝖡𝖫𝖾𝖺𝗋𝗇}|}_{{\mathrm{𝖢𝖲}}^t}$ denote the problem $\mathrm{\Delta }$-$\mathrm{𝖡𝖡𝖫𝖾𝖺𝗋𝗇}$ with the additional promise that $c{d}^t(P,\widehat{C})\le 2\log n$, and let $\mathrm{𝖤𝗑𝖺𝖼𝗍𝖡𝖡𝖫𝖾𝖺𝗋𝗇}$ and ${\mathrm{𝖤𝗑𝖺𝖼𝗍𝖡𝖡𝖫𝖾𝖺𝗋𝗇}|}_{{\mathrm{𝖢𝖲}}^t}$ to denote $\mathrm{\Delta }$-$\mathrm{𝖡𝖡𝖫𝖾𝖺𝗋𝗇}$ and $\mathrm{\Delta }$-${\mathrm{𝖡𝖡𝖫𝖾𝖺𝗋𝗇}|}_{{\mathrm{𝖢𝖲}}^t}$ when $\mathrm{\Delta }(1^n)=0$.

The following theorem can be viewed as the worst-case analog of the classic result of [21, 7] characterizing one-way functions through the hardness of average-case PAC learning.

As mentioned, [18] also recently obtained a worst-case characterization of one-way functions through a learning problem, and using a notion of computational depth. The problems, however, are somewhat different. As opposed to [18], we here consider the standard PAC learning problem (whereas they consider a more general learning problem), and condition on the standard notion of low computational depth (whereas they condition on a new notion of low computational depth that they introduce).⁸⁸8Of course, on a conceptual level, these results are similar; the key point we are trying to make here is that exactly the same learning problem characterizes either one-way functions or PKE, depending on whether the learner gets black-box or white-box access to the sampler.

We remark that our Theorem 6 differs from [21, 7] not only in the worst-case condition, but also generalizes those results in the sense that we handle the hardness of $\mathrm{\Delta }$-approximate learning for any $\mathrm{\Delta }$. As a consequence, we again get an equivalence of approximate and exact black-box learning:

We leave as an intriguing open problem the question of whether white-box learning of polynomial, or even logarithmic-degree polynomials, also can be collapsed down to the case of constant-degree functions (and thus to linear functions); if this were possible, it would show that PKE, in essence, inherently requires the structure of the LWE problem.

Additionally, as discussed above, even when just restricting attention to learning linear functions, our learning problem generalizes LWE. It would appear that despite this, cryptographic applications of LWE (e.g., to obtain fully homomorphic encryption [14, 10]) nevertheless may still be possible from this generalized version; we leave an exploration of this for future work.

Finally, it is an intriguing open problem to relate black-box and white-box learning. By our results, doing so is equivalent to relating public-key and secret-key encryption. We note that relating black-box and white-box learning is interesting even just for the case of linear functions (which by our results is equivalent to $O(1)$-degree polynomials). Indeed, Regev’s construction of a PKE [30] can be thought of a reduction from black-box learning to white-box learning of linear functions for a specific distribution; it is possible that a similar reduction may be applicable more generally.

First, we use the well-known fact that a PKE is simply a two-rounds key-agreement protocol. Moreover, by the Key-agreement Amplification Theorem of Holenstein [19] and an application of the Goldreich-Levin theorem [15], to obtain (full-fledged) PKE, it suffices to obtain a weak form of two-rounds key-agreemnt, which we simply refer to as Weak PKE defined as follows: There exist some $ϵ=1/\mathrm{poly}$ such that agreement between A and B happens with probability $1-ϵ$. Security requires that Eve cannot guess the key (output by Alice) with probability better than $1-20ϵ$.

We will next define the weak PKE protocol. We note that this construction resembles the universal key-agreement construction from [16], but with some crucial difference that enable our security proof. The parties A and B on input $n$ perform the following steps:

• $\mathrm{■}$

  Sample random program: A samples a random length $\lambda \in [2n]$, and a random program $\mathrm{\Pi }$ of length $\lambda$.

• $\mathrm{■}$

  Run random program: Next, A runs the program $\mathrm{\Pi }$ for at most $t(n)$ steps to get an output, and interprets the output as a pair of circuits ${{P:\{0,1\}}^r\to \{0,1\}}^k\times \{0,1\}{}^{\mathrm{\ell }}$ and ${C:\{0,1\}}^k\to \{0,1\}{}^{\mathrm{\ell }}$. (Think of $P$ as the sampler for a white-box learning instance, and of $C$ as a potential solution to the problem.) If the output of $\mathrm{\Pi }$ is not a valid encoding of such a pair, A sets $P=P_0$ and $C=C_0$ for two fixed circuits $P_0,C_0$ that always output $0$.

• $\mathrm{■}$

  Agreement estimation: A estimates the “agreement probability” of $P$ and $C$ (i.e., checking whether $C$ indeed is a good solution): it samples $n^{20}$ random inputs $w_1,\mathrm{\dots },w_{n^{20}}$ for $P$, and computes $(x_i,s_i)=P(w_i)$. It then lets $\widehat{\alpha }={\mathrm{Pr}}_{i\leftarrow [n^{20}]}[C(x_i)=s_i]$. If $\widehat{\alpha }\le 1-n^{-9}$, A reset the pair $(P,C)=(P_0,C_0)$.

• $\mathrm{■}$

  First message: A sends (the “sampler”) $P$ to B.

• $\mathrm{■}$

  Second message: B applies $P$ on a random input $w$, and computes $(x,s)=P(w)$. It then sends $x$ to A.

• $\mathrm{■}$

  Outputs: A outputs $C(x)$ and Bob outputs $s$.

We claim that with probability $1-1/n^8$, Alice and Bob will agree (i.e., the final outputs are the same). Note that if $(P,C)=(P_0,C_0)$, Alice and Bob always agree. Moreover, let $\alpha ={\mathrm{Pr}}_{(x,s)\leftarrow P(U_r)}[C(x)=s]$. Then, the probability of Alice and Bob to agree given that Alice uses $(P,C)$ as the circuits in the protocol, is exactly $\alpha$. We observe that by the Chernoff bound, the probability that $\widehat{\alpha }$ is far from $\alpha$ is small, and thus Alice uses $(P,C)$ only when $\alpha$ is larger than $1-n^{-8}$.

We claim that $\mathrm{𝖤𝗏𝖾}$ that can guess $s$ with probability $1-n^{-7}$ can be used to solve
${\mathrm{𝖤𝗑𝖺𝖼𝗍𝖶𝖡𝖫𝖾𝖺𝗋𝗇}|}_{{\mathrm{𝖢𝖲}}^t}$. In more detail, consider such $\mathrm{𝖤𝗏𝖾}$, and let $P$ be an input for
${\mathrm{𝖤𝗑𝖺𝖼𝗍𝖶𝖡𝖫𝖾𝖺𝗋𝗇}|}_{{\mathrm{𝖢𝖲}}^t}$. The idea is to construct an algorithm $\mathrm{𝖫𝖾𝖺𝗋𝗇𝖾𝗋}$, that on input $P$ outputs a circuit $C$, such that $C(x)$ simply simulates $\mathrm{𝖤𝗏𝖾}$ on the messages $P$ and $x$. $C$ then outputs $\mathrm{𝖤𝗏𝖾}$’s output. For simplicity, in the following we assume that $\mathrm{𝖤𝗏𝖾}$ (and thus $\mathrm{𝖫𝖾𝖺𝗋𝗇𝖾𝗋}$) is deterministic. (We note that this is a non-black-box reduction: We are using the code of Eve to generate $C$ – in particular, we are including the code of Eve into this circuit.⁹⁹9This particular non-black usage of Eve is not inherent. We could have considered a different formalization of the learning theory problem which simply requires the attacker to succeed on a randomly sampled instance. Subsequent parts of the argument, however, will use non-black-box access to Eve more inherently.)

Let $𝐏$ be a random variable distributed according to the same distribution of the first message in the above protocol. By assumption, we have that

It follows by a simple averaging argument that

Namely, $\mathrm{𝖫𝖾𝖺𝗋𝗇𝖾𝗋}$ solves $\mathrm{𝖤𝗑𝖺𝖼𝗍𝖶𝖡𝖫𝖾𝖺𝗋𝗇}$ with probability at least $1-3n^{-7}$ over the distribution of $𝐏$. We next use ideas from [26, 6] to show this implies that $\mathrm{𝖫𝖾𝖺𝗋𝗇𝖾𝗋}$ solves ${\mathrm{𝖤𝗑𝖺𝖼𝗍𝖶𝖡𝖫𝖾𝖺𝗋𝗇}|}_{{\mathrm{𝖢𝖲}}^t}$ in the worst case.

Indeed, assume that $\mathrm{𝖫𝖾𝖺𝗋𝗇𝖾𝗋}$ fails on some instance $P$ of ${\mathrm{𝖤𝗑𝖺𝖼𝗍𝖶𝖡𝖫𝖾𝖺𝗋𝗇}|}_{{\mathrm{𝖢𝖲}}^t}$. By the promise of the problem, there exists a circuit $\widehat{C}$ such that $c{d}^t(P,\widehat{C})\le 2\log n$, and $\widehat{C}$ agrees with $P$ with probability at least $1-n^{-10}$. Let $\mathrm{\ell }={\mathrm{K}}^t(P,\widehat{C})$. Our goal is to show that , which is a contradiction.

Toward this goal, let Let ${𝒮}_{\mathrm{\ell }}$ be the set of all pairs of circuits $(P^{\prime },\widehat{C^{\prime }})$ with ${\mathrm{K}}^t(P^{\prime },\widehat{C^{\prime }})=\mathrm{\ell }$ that agree with probability at least $1-n^{-10}$, and on which $\mathrm{𝖫𝖾𝖺𝗋𝗇𝖾𝗋}$ fails, so that $(P,\widehat{C})\in {𝒮}_{\mathrm{\ell }}$. Fix $(P^{\prime },\widehat{C^{\prime }})\in {𝒮}_{\mathrm{\ell }}$, and let $\mathrm{\Pi }$ be the length $\mathrm{\ell }$ program that outputs $(P^{\prime },\widehat{C^{\prime }})$ in time $t$. Observe that the probability of A to sample $(P^{\prime },\widehat{C^{\prime }})$ in the first step of the above protocol is at least its probability to sample the program $\mathrm{\Pi }$, which is $1/2n\cdot 2^{-\mathrm{\ell }}$. Since $(P^{\prime },\widehat{C^{\prime }})$ agree with high probability, the equality test it the third step of the protocol will pass with high probability, and thus $A$ will send $P^{\prime }$ to B with probability at least $1/4n\cdot 2^{-\mathrm{\ell }}$. In other words,

for every $(P^{\prime },\widehat{C^{\prime }})\in {𝒮}_{\mathrm{\ell }}$, and thus

(here we say that $(P,\cdot )\in {𝒮}_{\mathrm{\ell }}$ if there is some $C$ such that $(P,C)\in {𝒮}_{\mathrm{\ell }}$).

On the other hand, by definition of ${𝒮}_{\mathrm{\ell }}$, $\mathrm{𝖫𝖾𝖺𝗋𝗇𝖾𝗋}$ fails on every $(P^{\prime },\widehat{C^{\prime }})\in {𝒮}_{\mathrm{\ell }}$. Since $\mathrm{𝖫𝖾𝖺𝗋𝗇𝖾𝗋}$ fails with probability at most $3n^{-7}$ on $𝐏$, it must holds that

Combining the above, we get that

We can now use the bound on ${𝒮}_{\mathrm{\ell }}$ to bound the Kolmogorov complexity of $(P,\widehat{C})$. To describe $(P,\widehat{C})$, it is enough to describe the set ${𝒮}_{\mathrm{\ell }}$, and the index of the pair $(P,\widehat{C})$ in this set. That is,

We conclude the proof with the observation that to describe ${𝒮}_{\mathrm{\ell }}$ it is enough to describe $n$ (which can be done using $\log n+O(\log \log n)$ bits), $\mathrm{\ell }$ ($\log n$ bits) and $\mathrm{𝖤𝗏𝖾}$ (that can be described with constant many bits¹⁰¹⁰10This non-black-box usage of Eve (which is taken from [26, 6]) is seemingly inherent to our proof technique. Note that we are here relying on the fact that Eve is a uniform algorithm, but as we discuss in the formal section, the argument can be extended to work also in the non-uniform setting.). Thus, $\mathrm{K}({𝒮}_{\mathrm{\ell }})\le 3\log n$, and we get that

as we wanted to show.

We next show that the existence of PKE implies the hardness of ${\mathrm{𝖤𝗑𝖺𝖼𝗍𝖶𝖡𝖫𝖾𝖺𝗋𝗇}|}_{{\mathrm{𝖢𝖲}}^t}$. We now sketch the proof. Let $\mathrm{𝖦𝖾𝗇}$ be the algorithm the generate pair $(pk,sk)$ of public and secret key, and let $\mathrm{𝖤𝗇𝖼},\mathrm{𝖣𝖾𝖼}$ be the encryption and decryption protocols. For a random pair of keys $(pk,sk)\leftarrow \mathrm{𝖦𝖾𝗇}(r)$, we construct two circuits, $P(w,s)=(x={\mathrm{𝖤𝗇𝖼}}_{pk}(s;w),s)$, and $\widehat{C}(x)={\mathrm{𝖣𝖾𝖼}}_{sk}(x)$.

By the security of the PKE scheme, it follows that with high probability over the randomness of $\mathrm{𝖦𝖾𝗇}$, it is hard to learn the function of $C$, as the circuit $P$ only uses the public key, and the function $C$ computes is the decryption of a random encryption. This already implies that $\mathrm{𝖤𝗑𝖺𝖼𝗍𝖶𝖡𝖫𝖾𝖺𝗋𝗇}$ is hard, but we still need to show that $P$ is inside the promise of the problem ${\mathrm{𝖤𝗑𝖺𝖼𝗍𝖶𝖡𝖫𝖾𝖺𝗋𝗇}|}_{{\mathrm{𝖢𝖲}}^t}$.

It follows by the correctness of the PKE scheme that $\widehat{C}$ computes the function that is sampled by $P$. Thus, to be in the promise of ${\mathrm{𝖤𝗑𝖺𝖼𝗍𝖶𝖡𝖫𝖾𝖺𝗋𝗇}|}_{{\mathrm{𝖢𝖲}}^t}$, we only need that $(P,\widehat{C})$ has small computational depth. This, however, is not necessarily the case. To solve this, we simply pad $\widehat{C}$ with the randomness used by $\mathrm{𝖦𝖾𝗇}$. That is, we let $\widehat{C^{\prime }}$ be a functionally equivalent circuit to $\widehat{C}$, with $r$ encoded to it, where $r$ is such that $\mathrm{𝖦𝖾𝗇}(r)=(pk,sk)$. It follows that when $t$ is large enough, ${\mathrm{K}}^t(P,\widehat{C^{\prime }})\le |r|+O(1)$ (as we can describe them by simply describing the randomness and the algorithm $\mathrm{𝖦𝖾𝗇}$). On the other hand, $\mathrm{K}(P,\widehat{C^{\prime }})\ge \mathrm{K}(r)$ (since $r$ can be obtained from $\widehat{C^{\prime }}$), which is at least $|r|-O(1)$ with high probability. Together, we conclude that with high probability over the randomness of $\mathrm{𝖦𝖾𝗇}$, the circuits $(P,\widehat{C^{\prime }})$ are in the promise of ${\mathrm{𝖤𝗑𝖺𝖼𝗍𝖶𝖡𝖫𝖾𝖺𝗋𝗇}|}_{{\mathrm{𝖢𝖲}}^t}$.

We remark that at a high-level, our construction of a two-message key-agreement protocol shares many similaries with the key-agreement protocol developing in [6], relying on the hardness of an interactive notion of time-bounded Kolmogorov complexity, conditionned on an analog of computational shallowness. They central difference is that the protocol in [6] requires at least 3 rounds due to the use of an equility check protocol to determine whether Alice and Bob managed to agree on a key. In contrast, our protocol does not rely on such an equality check step (and thus it can be executed in only two rounds, which is crucial to get PKE); indeed, we replaced the equality protocol with a step where Alice on her own can determine whether the message she sends will enable agreement to happen. Of course, the reason why we can do this is that we are reducing security from a different problem.

Other features of the protocol are quite similar; this is because we also rely on the worst-case hardness of a problem “conditioning on computationally shallow instances”. Indeed, as described above, our security proof shares many features with those of [25, 6].

Universal constructions of PKE are known (see [16]); that is, constructions having the property that they are secure if (any) PKE exist. We emphasize that while the details of the protocol from [16] are somewhat different, the “agreement estimation” step performed there is very similar to what we do. Furthermore, we can interpret our protocol as an alternative (variant) universal PKE protocol in which Alice chooses a random (key-generation) program $\mathrm{𝖦𝖾𝗇}$ and executes it to get an encryption scheme ${\mathrm{𝖤𝗇𝖼}}_{pk}$ and description scheme ${\mathrm{𝖣𝖾𝖼}}_{sk}$, with the keys $pk,sk$ hardcoded to the scheme.¹¹¹¹11In the protocol of [16], Alice would instead choose random programs for Alice and Bob to run; we do not know how to prove the security of such a protocol under our assumption. Alice then estimates the agreement probability of the encryption, and if it is high enough, she sends the encryption scheme as the public-key, and uses the decryption scheme as the private-key. If PKE exists, with a noticeable probability over the choice of $\mathrm{𝖦𝖾𝗇}$, this scheme will be secure. We emphasize that since we base the security of our protocol (and thus also the above universal one) on the hardness of the white-box learning problem, it enables an approach for measuring the concrete security of the protocol by relating it to the security of the learning theory problem.