## Membership query removal implies non-trivial cryptographic primitives

##### Abstract

Understanding learning and discovering to what extent it can be automated is one of the major
problems in computer science. This is of obvious relevance when trying to create intelligent robots,
for example, and fields as diverse as biology and economics use learning algorithms to help manage
and understand their extremely large data sets. There has even been work devoted to analyzing
computational learning systems in order to gain intuition about natural learning systems: authors
of a '60s textbook on learning machines called perceptrons give voice to their hope that among
their readership are "psychologists and biologists who would like to know how the brain computes
thoughts" [MP69]. More recently, we have seen the development of a mathematical model for
analyzing evolution as a learning process [Val09].
One major approach taken to analyzing learning has been to look at classification problems. As an
example of such a problem, consider the scenario of teaching a computer to tell when an image has
a bird in it. Say you go about doing this by showing the computer a ton of pictures and telling it
which ones have birds in them. After giving it some time to compute, you might hope that it can
now figure out whether or not images that it hasn't seen before have birds in them. But how can
you be sure that this is a fruitful way of teaching image recognition?
Computational learning theory attempts to answer this question in a mathematically rigorous way
by formalizing these classification scenarios in models that de fine exactly the interaction between
the learner and what it's trying to learn and give a metric for evaluating the learner's success. When
learning is so formalized in models, we can begin to answer natural questions about learning, such
as to what extent does asking questions help. Two of these models that we will focus on here are
Leslie Valiant's Probably Approximately Correct (PAC) model of learning and Dana Angluin's exact
learning model.
Researchers have carefully studied the issue of whether giving the learner the ability to ask questions (or to pose membership queries, in learning theory terminology) improves its ability to learn,
and the answer is dependent on the learning model under consideration. In the agnostic learning
model, for instance, a learner which works with membership queries can be converted to one which works without membership queries, although in the distribution-specifi c agnostic setting membership queries do increase the power of the learner [Fel09]. In both the PAC model and the exact
learning model, on the other hand, it has been shown that there are some concepts that can be
learned with membership queries but cannot be learned without. A well known example of such a
class is the class of deterministic nite automatas (DFAs), which were shown to be learnable with
membership queries in [Ang87] but not learnable without membership queries in [KV94] given
suitable assumptions.
Another major development of computer science has been that of modern cryptography. Starting
from certain basic and currently unavoidable assumptions, powerful cryptographic protocols have
been developed which multiple consenting parties can use to engage in secure communication, which
has a wide variety of uses, including electronic commerce. A major part of the cryptographic
research e ffort has been to further understand the assumptions that form the foundation of these
cryptographic protocols, with one eventual aim being perhaps to construct cryptographic protocols
that do not require any assumptions. An example of a protocol that will be used in this paper is
the signature scheme, which allows a user to sign any message they send so that whoever receives it
knows who sent it.
The link between cryptography and learning theory was recognized very early on. The very first
paper on PAC learning rules out learning polynomial-size circuits given cryptographic assumptions
[Val84]. At a high level, a cryptographic protocol proven to be secure has a guarantee attached to it
which prevents a malicious user from breaking the security, no matter how well that user may learn.
So provably-secure cryptography bounds the ability to learn.
One such link was shown by Angluin and Kharitonov in [AK95]. They showed that giving learners
membership queries in the PAC model does not help them for a large number of concepts being
learned if signature schemes exist. In this paper, we investigate whether the converse of this statement can be proven, i.e. whether it can be shown that if making membership queries does not help
learners, then signature schemes exist. We look at severely weakened versions of the converse and
prove a couple of results. On the whole, however, our attempt at converting their result is largely
unsuccessful.