We study connections between two fundamental questions from computer science theory. (1) Is witness encryption in the sense of Garg et al. (2013) possible for NP? That is, given an instance $x$ of an NP-complete language $L$, can one encrypt a secret message with security contingent on the ability to provide a witness for $x \in L$? (2) Is computational learning (in the sense of Valiant (1984), and Kearns et al. (1994)) hard for NP? That is, is there a polynomial-time reduction from instances of $L$ to instances of learning?

Our main contribution is that certain formulations of NP-hardness of learning characterize the existence of witness encryption for NP. More specifically, we show:

1. witness encryption for a language $L\in$NP is equivalent to a half-Levin reduction from $L$ to the Computational Gap Learning problem (denoted CGL by Applebaum et al. (2008)),

where a half-Levin reduction is the same as a Levin reduction but only required to preserve witnesses in one direction, and CGL formalizes agnostic learning as a decision problem. We show versions of the statement above for witness encryption secure against non-uniform and uniform adversaries. We also show that witness encryption for NP with ciphertexts of logarithmic length, along with a circuit lower bound for E, are together equivalent to NP-hardness of a generalized promise version of MCSP.

We complement the above with a number of unconditional NP-hardness results for agnostic PAC learning. Extending a result of Hirahara (2022) to the standard setting of boolean circuits, we show NP-hardness of "semi-proper" learning. Namely:

2. for some polynomial $s$, it is NP-hard to agnostically learn circuits of size $s(n)$ by circuits of size $s(n)\cdot n^{1/(\log \log n)^{O(1)}}$.

Looking beyond the computational model of standard boolean circuits enables us to prove NP-hardness of improper learning (i.e., without a restriction on the size of hypothesis returned by the learner). We obtain such results for:

3. learning circuits with oracle access to a given randomly sampled string, and
4. learning RAM programs.

In particular, we show that a variant of MINLT of Ko (1991) for RAM programs is NP-hard with parameters corresponding to the setting of improper learning. We view these results as partial progress toward the ultimate goal of showing NP-hardness of learning boolean circuits in an improper setting.

Lastly, we give some consequences of NP-hardness of learning for private- and public-key cryptography. Improving a main result of Applebaum et al. (2008), we show that if improper agnostic PAC learning is NP-hard under a randomized non-adaptive reduction (with some restrictions), then NP?BPP implies the existence of i.o. one-way functions. In contrast, if CGL is NP-hard under a half-Levin reduction, then NP?BPP implies the existence of i.o. public-key encryption.