Learning is a central task in computer science, and there are various
formalisms for capturing the notion. One important model studied in
computational learning theory is the PAC model of Valiant (CACM 1984).
On the other hand, in cryptography the notion of ``learning nothing''
is often modelled by the simulation paradigm: in an interactive
protocol, a party learns nothing if it can produce a transcript of the
protocol by itself that is indistinguishable from what it gets by
interacting with other parties. The most famous example of this
paradigm is zero knowledge proofs, introduced by Goldwasser, Micali,
and Rackoff (SICOMP 1989).

Applebaum, Barak, and Xiao (FOCS 2008) established a connection
between these two different notions of learning by observing that if
there exist non-trivial languages with zero-knowledge proofs (\ie $\ZK
\neq \BPP$), then no polynomial-time algorithm can PAC learn
polynomial-size circuits. In this paper, we consider the reverse
implication: is it true that if learning is hard then zero-knowledge
proofs exist for non-trivial languages? We rule out two classes of
techniques for proving this statement:
1. Relativizing techniques: there exists an oracle $\calO$ relative
to which learning polynomial-size circuits is hard and yet
$\ZK^\calO = \BPP^\calO$.
2. Black-box techniques: if there is a (semi-)black-box proof that
uses the hardness of PAC learning polynomial-size circuits to
construct a zero knowledge proof for some language $L$, then in fact
$L \in \AM \cap \coAM$.
Together, these results rule out all known techniques for proving
that hardness of learning implies $\ZK \neq \BPP$, including partially
non-black-box techniques such as those of Barak (FOCS 2001).
In addition, our technique relies on a new kind of separating oracle
that may be of independent interest.