__
TR09-006 | 19th January 2009 00:00
__

#### On basing ZK != BPP on the hardness of PAC learning

TR09-006
Authors:

David Xiao
Publication: 26th January 2009 05:35

Downloads: 2476

Keywords:

**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.