Abstract:
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.