Membership query removal implies non-trivial cryptographic primitives

Access full-text files




Wright, John

Journal Title

Journal ISSN

Volume Title



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.


LCSH Subject Headings